从零开始学习 Java：简单易懂的入门指南之HashMap及TreeMap源码解读（二十四）

学习 java 哈希算法开发语言算法数据结构链表 2023-09-14 18:09:52 889人浏览八月长安

摘要

HashMap及TreeMap源码解读 HashMap源码TreeMap源码 HashMap源码 1.看源码之前需要了解的一些内容node[] table 哈希表结构中数组的名字DEF

HashMap及TreeMap源码解读

HashMap源码
TreeMap源码

HashMap源码

1.看源码之前需要了解的一些内容node<K,V>[] table   哈希表结构中数组的名字DEFAULT_INITIAL_CAPACITY：   数组默认长度16DEFAULT_LOAD_FACTOR：        默认加载因子0.75HashMap里面每一个对象包含以下内容：1.1 链表中的键值对对象    包含：  int hash;         //键的哈希值            final K key;      //键            V value;          //值            Node<K,V> next;   //下一个节点的地址值1.2 红黑树中的键值对对象包含：int hash;         //键的哈希值            final K key;      //键            V value;          //值            TreeNode<K,V> parent;  //父节点的地址值TreeNode<K,V> left;//左子节点的地址值TreeNode<K,V> right;//右子节点的地址值boolean red;//节点的颜色2.添加元素HashMap<String,Integer> hm = new HashMap<>();hm.put("aaa" , 111);hm.put("bbb" , 222);hm.put("ccc" , 333);hm.put("DDD" , 444);hm.put("eee" , 555);添加元素的时候至少考虑三种情况：2.1数组位置为null2.2数组位置不为null，键不重复，挂在下面形成链表或者红黑树2.3数组位置不为null，键重复，元素覆盖//参数一：键//参数二：值//返回值：被覆盖元素的值，如果没有覆盖，返回nullpublic V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理//简单理解：返回值就是返回键的哈希值static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}//参数一：键的哈希值//参数二：键//参数三：值//参数四：如果键重复了是否保留//   true，表示老元素的值保留，不会覆盖//   false，表示老元素的值不保留，会进行覆盖final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {    //定义一个局部变量，用来记录哈希表中数组的地址值。        Node<K,V>[] tab;//临时的第三方变量，用来记录键值对对象的地址值        Node<K,V> p;        //表示当前数组的长度int n;//表示索引        int i;//把哈希表中数组的地址值，赋值给局部变量tabtab = table;        if (tab == null || (n = tab.length) == 0){//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件//如果没有达到扩容条件，底层不会做任何操作//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中tab = resize();//表示把当前数组的长度赋值给n            n = tab.length;        }//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置i = (n - 1) & hash;//index//获取数组中对应元素的数据p = tab[i];        if (p == null){//底层会创建一个键值对对象，直接放到数组当中            tab[i] = newNode(hash, key, value, null);        }else {            Node<K,V> e;            K k;//等号的左边：数组中键值对的哈希值//等号的右边：当前要添加键值对的哈希值//如果键不一样，此时返回false//如果键一样，返回trueboolean b1 = p.hash == hash;            if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){                e = p;            } else if (p instanceof TreeNode){//判断数组中获取出来的键值对是不是红黑树中的节点//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);            } else {//如果从数组中获取出来的键值对不是红黑树中的节点//表示此时下面挂的是链表                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {//此时就会创建一个新的节点，挂在下面形成链表                        p.next = newNode(hash, key, value, null);//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin//treeifyBin方法的底层还会继续判断//判断数组的长度是否大于等于64//如果同时满足这两个条件，就会把这个链表转成红黑树                        if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);                        break;                    }//e：  0x0044  ddd  444//要添加的元素： 0x0055   ddd   555//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){ break;}                    p = e;                }            }//如果e为null，表示当前不需要覆盖任何元素//如果e不为null，表示当前的键是一样的，值会被覆盖//e:0x0044  ddd  555//要添加的元素： 0x0055   ddd   555            if (e != null) {                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null){//等号的右边：当前要添加的值//等号的左边：0x0044的值e.value = value;}                afterNodeAccess(e);                return oldValue;            }        }        //threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12        if (++size > threshold){ resize();}        //表示当前没有覆盖任何元素，返回null        return null;    }

TreeMap源码

1.TreeMap中每一个节点的内部属性K key;//键V value;//值Entry<K,V> left;//左子节点Entry<K,V> right;//右子节点Entry<K,V> parent;//父节点boolean color;//节点的颜色2.TreeMap类中中要知道的一些成员变量public class TreeMap<K,V>{       //比较器对象    private final Comparator<? super K> comparator;//根节点    private transient Entry<K,V> root;//集合的长度    private transient int size = 0;   3.空参构造//空参构造就是没有传递比较器对象 public TreeMap() {        comparator = null;    }4.带参构造//带参构造就是传递了比较器对象。public TreeMap(Comparator<? super K> comparator) {        this.comparator = comparator;    }5.添加元素public V put(K key, V value) {        return put(key, value, true);    }参数一：键参数二：值参数三：当键重复的时候，是否需要覆盖值true：覆盖false：不覆盖private V put(K key, V value, boolean replaceOld) {//获取根节点的地址值，赋值给局部变量t        Entry<K,V> t = root;//判断根节点是否为null//如果为null，表示当前是第一次添加，会把当前要添加的元素，当做根节点//如果不为null，表示当前不是第一次添加，跳过这个判断继续执行下面的代码        if (t == null) {//方法的底层，会创建一个Entry对象，把他当做根节点            addEntryToEmptyMap(key, value);//表示此时没有覆盖任何的元素            return null;        }//表示两个元素的键比较之后的结果        int cmp;//表示当前要添加节点的父节点        Entry<K,V> parent;//表示当前的比较规则//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器        Comparator<? super K> cpr = comparator;//表示判断当前是否有比较器对象//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准        if (cpr != null) {            do {                parent = t;                cmp = cpr.compare(key, t.key);                if (cmp < 0)                    t = t.left;                else if (cmp > 0)                    t = t.right;                else {                    V oldValue = t.value;                    if (replaceOld || oldValue == null) {                        t.value = value;                    }                    return oldValue;                }            } while (t != null);        } else {//把键进行强转，强转成Comparable类型的//要求：键必须要实现Comparable接口，如果没有实现这个接口//此时在强转的时候，就会报错。            Comparable<? super K> k = (Comparable<? super K>) key;            do {//把根节点当做当前节点的父节点                parent = t;//调用compareTo方法，比较根节点和当前要添加节点的大小关系                cmp = k.compareTo(t.key);                if (cmp < 0)//如果比较的结果为负数//那么继续到根节点的左边去找                    t = t.left;                else if (cmp > 0)//如果比较的结果为正数//那么继续到根节点的右边去找                    t = t.right;                else {//如果比较的结果为0，会覆盖                    V oldValue = t.value;                    if (replaceOld || oldValue == null) {                        t.value = value;                    }                    return oldValue;                }            } while (t != null);        }//就会把当前节点按照指定的规则进行添加        addEntry(key, value, parent, cmp < 0);        return null;    } private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {        Entry<K,V> e = new Entry<>(key, value, parent);        if (addToLeft)            parent.left = e;        else            parent.right = e;//添加完毕之后，需要按照红黑树的规则进行调整        fixAfterInsertion(e);        size++;        modCount++;    }private void fixAfterInsertion(Entry<K,V> x) {//因为红黑树的节点默认就是红色的        x.color = RED;//按照红黑规则进行调整//parentOf:获取x的父节点//parentOf(parentOf(x)):获取x的爷爷节点//leftOf:获取左子节点        while (x != null && x != root && x.parent.color == RED) {//判断当前节点的父节点是爷爷节点的左子节点还是右子节点//目的：为了获取当前节点的叔叔节点            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//表示当前节点的父节点是爷爷节点的左子节点//那么下面就可以用rightOf获取到当前节点的叔叔节点                Entry<K,V> y = rightOf(parentOf(parentOf(x)));                if (colorOf(y) == RED) {//叔叔节点为红色的处理方案//把父节点设置为黑色                    setColor(parentOf(x), BLACK);//把叔叔节点设置为黑色                    setColor(y, BLACK);//把爷爷节点设置为红色                    setColor(parentOf(parentOf(x)), RED);//把爷爷节点设置为当前节点                    x = parentOf(parentOf(x));                } else {//叔叔节点为黑色的处理方案//表示判断当前节点是否为父节点的右子节点                    if (x == rightOf(parentOf(x))) {//表示当前节点是父节点的右子节点                        x = parentOf(x);//左旋                        rotateLeft(x);                    }                    setColor(parentOf(x), BLACK);                    setColor(parentOf(parentOf(x)), RED);                    rotateRight(parentOf(parentOf(x)));                }            } else {//表示当前节点的父节点是爷爷节点的右子节点//那么下面就可以用leftOf获取到当前节点的叔叔节点                Entry<K,V> y = leftOf(parentOf(parentOf(x)));                if (colorOf(y) == RED) {                    setColor(parentOf(x), BLACK);                    setColor(y, BLACK);                    setColor(parentOf(parentOf(x)), RED);                    x = parentOf(parentOf(x));                } else {                    if (x == leftOf(parentOf(x))) {                        x = parentOf(x);                        rotateRight(x);                    }                    setColor(parentOf(x), BLACK);                    setColor(parentOf(parentOf(x)), RED);                    rotateLeft(parentOf(parentOf(x)));                }            }        }//把根节点设置为黑色        root.color = BLACK;    }

Tip:

1.TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？
此时是不需要重写的。

2.HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？
不需要的。
因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的

3.TreeMap和HashMap谁的效率更高？
如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高
但是这种情况出现的几率非常的少。
一般而言，还是HashMap的效率要更高。

4.你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？
此时putIfAbsent本身不重要。
传递一个思想：
代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。
那么该逻辑一定会有B面。
习惯：
boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值
int类型的变量控制，一般至少有三面，因为int可以取多个值。