【Java容器源码】HashMap（二）添加元素及树化源码分析

快来打我* 2022-10-31 00:46 186阅读 0赞

> HashMap 系列：
> 
>  *  [【Java容器源码】HashMap（一）底层结构分析][Java_HashMap]
>  *  [【Java容器源码】HashMap（二）添加元素及树化源码分析][Java_HashMap 1]
>  *  [【Java容器源码】HashMap（三）扩容源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（四）获取 value 及迭代器源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（五）源码分析&死锁问题（JDK7）][Java_HashMap_JDK7]
>  *  [【Java容器源码】关于HashMap的几个问题][Java_HashMap 3]

## 1.向 Hash 表中添加元素 ##

### put() ###

public V put(K key, V value) {
        
            	// 传入hash值的目的在于，定位目标桶
                return putVal(hash(key), key, value, false, true);
        }

### hash() ###

计算每个Node的hash值，这个hash值是确定哈希桶的依据

*  那为什么不直接拿key作为分桶依据，而是要hash值？因为不是所有的key都是Integer
 *  那得到这个hash值后，怎么计算槽点？具体的槽点 = (length-1) % hash = hash % (length-1)

// jdk8比jdk7引入了红黑树，所以hash方法进行了简化
    static final int hash(Object key) {
        
            int h;
        	// null = 0
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }

从代码中看出，要注意以下两点：

1.  如果某个类型要作为 hashmap 的key，必须要有 hashcode 方法
2.  将 hashCode 值再右移16位是为了让算出来的 hash 更分散，以减少哈希冲突

> 注：由 key 为 null 的 hash=0 可以看出，HashMap 允许添加 key 为 null 的 Entry。但是，HashTable 是不允许有 key 为 null 的元素的。

### putVal() ###

在看 putVal 之前首先要清楚一件事，整个 HashMap 所有 key 唯一，即当添加一个已经有的 key 时，要么覆盖旧 value，要么直接添加失败。

大致过程如下：

1.  判断数组有无初始化，若无先初始化  
    注：跟ArrayList一样，不是一开始就初始化好数组，而是在第一次添加元素再初始化
2.  执行新增逻辑
    
     *  无hash冲突：即当前位置为空，创建node后直接增加
        
         *  在方法最后modCount++，记录hashmap数组发生变化
         *  if (++size > threshold) resize(); 判断是否要扩容
         *  最后返回 null
     *  有hash冲突：首先找到（hash&&key相同的节点或队尾节点）位置e，然后追加或判断后覆盖旧值
        
         *  情况一：数组上的这个节点的与要新增节点key与hash相同
         *  情况二：红黑树，使用红黑树的方式新增
         *  情况三：链表，依次遍历，binCount记录链表长度，判断有无hash与key相同的节点e
            
             *  e != null 若onlyIfAbsent=false（覆盖旧值） ,返回 oldValue
             *  e == null （追加到队尾），然后 if (binCount >= TREEIFY\_THRESHOLD - 1) 判断是否需要链表转红黑树
            
              
            注：当要添加的 key 不存在时（即不存在 oldVal），才会 size++，然后判断是否需要扩容

// 入参 hash：通过 hash 算法计算出来的值。用于定位目标桶
    // 入参 onlyIfAbsent：absent缺席，表示只在key不存在时添加，默认为 false（key已存在时覆盖）
    // 返回的是oldValue，若不存在相同key就返回null
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
        // n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果数组为空，使用 resize 方法初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        //---------------------------新增逻辑--------------------------------------------
        // 计算数组下标，实际上就是 hash %（n-1）
        // 并判断如果当前索引位置是空的，直接生成新的节点在当前索引位置上
        if ((p = tab[i = (n - 1) & hash]) == null)
        	// 创建新 node
            tab[i] = newNode(hash, key, value, null); 
        // 如果当前索引位置有值的处理方法，即我们常说的如何解决 hash 冲突
        else {
        
            // e 当前节点的临时变量
            Node<K,V> e; K k;
            // 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量
            // 注：这里是先判断key的hash值，因为hash不同key一定不同，
            //     然后再判断key，这里还要==key 是因为key可能是缓存池的包装类
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是红黑树，使用红黑树的方式新增
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 是个链表，把新节点放到链表的尾端
            else {
        
                // 自旋，链表头开始遍历
                // 注：这个binCount还有记录链表长度的作用
                for (int binCount = 0; ; ++binCount) {
        
                    // p.next == null 表明此时已经遍历到了链表最后
                    if ((e = p.next) == null) {
        
                        // 把新节点放到链表的尾部 
                        p.next = newNode(hash, key, value, null);
                        // 当链表的长度大于等于 8 时，链表转红黑树
                        // 注：在treeifyBin方法中还要判断size是否大于64，若小于64不会树化会扩容
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 链表遍历过程中，发现有元素和新增的元素相等，结束循环
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 更改循环的当前元素，使 p 在遍历过程中，一直往后移动。
                    p = e;
                }
            }
            
            // 说明链表中存在与key相同的节点
            if (e != null) {
        
                V oldValue = e.value;
                // 当 onlyIfAbsent 为 false 时，才会覆盖值 
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                // 返回老值
                return oldValue;
            }
        }
        
        //---------------------------------------------------------------------------------
        // 记录 HashMap 的数据结构发生了变化
        ++modCount;
        // 如果 HashMap 的实际大小大于扩容的门槛，开始扩容
        // 注：这里的逻辑是先增加再扩容，因为不一定是新增还有可能是覆盖
        if (++size > threshold)
            resize();
        
        // 对于LinkedListMap判断是否执行LRU条件之一（默认true）
        afterNodeInsertion(evict);
        return null;
    }

## 2.向红黑树中添加元素 ##

### putTreeVal() ###

1.  首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：
    
    1.  如果节点没有实现 Comparable 接口，使用 equals 进行判断；
    2.  如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断。
2.  新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；
3.  自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；
4.  把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；
5.  进行着色和旋转，结束。

// 入参 h：key 的hash值
    final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
        
        Class<?> kc = null;
        boolean searched = false;
        // 找到根节点
        TreeNode<K,V> root = (parent != null) ? root() : this;
        // 自旋
        for (TreeNode<K,V> p = root;;) {
        
            int dir, ph; K pk;
            // p hash 值大于 h，说明 p 在 h 的右边
            if ((ph = p.hash) > h)
                dir = -1;
            // p hash 值小于 h，说明 p 在 h 的左边
            else if (ph < h)
                dir = 1;
            // 要放进去key在当前树中已经存在了(equals来判断)
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            // 自己实现的Comparable的话，不能用hashcode比较了，需要用compareTo
            else if ((kc == null &&
                      //得到key的Class类型，如果key没有实现Comparable就是null
                      (kc = comparableClassFor(k)) == null) ||
                      //当前节点pk和入参k不等
                     (dir = compareComparables(kc, k, pk)) == 0) {
        
                if (!searched) {
        
                    TreeNode<K,V> q, ch;
                    searched = true;
                    if (((ch = p.left) != null &&
                         (q = ch.find(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                         (q = ch.find(h, k, kc)) != null))
                        return q;
                }
                dir = tieBreakOrder(k, pk);
            }
    
            TreeNode<K,V> xp = p;
            // 找到和当前hashcode值相近的节点(当前节点的左右子节点其中一个为空即可)
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
        
                Node<K,V> xpn = xp.next;
                // 生成新的节点
                TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                // 把新节点放在当前子节点为空的位置上
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                // 当前节点和新节点建立父子，前后关系
                xp.next = x;
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((TreeNode<K,V>)xpn).prev = x;
                // balanceInsertion 对红黑树进行着色或旋转，以达到更多的查找效率，着色或旋转的几种场景如下
                //  着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色；		   	
                // 如果父亲是红色，那么必须通过重新着色或者旋转的方法，再次达到红黑树的5个约束条件
                // 旋转： 父亲是红色，叔叔是黑色时，进行旋转
                // 如果当前节点是父亲的右节点，则进行左旋
                // 如果当前节点是父亲的左节点，则进行右旋
              
                // moveRootToFront 方法是把算出来的root放到根节点上
                moveRootToFront(tab, balanceInsertion(root, x));
                return null;
            }
        }
    }

红黑树的 5 个原则：

*  节点是红色或黑色
 *  根是黑色
 *  所有叶子都是黑色
 *  从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
 *  从每个叶子到根的所有路径上不能有两个连续的红色节点

## 3.链表树化 ##

### treeifyBin() ###

链表转化为红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
                int n, index; Node<K,V> e;
            	// 如果当前hash表的长度小于64，不会树化而是进行扩容
                if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                    resize();
                else if ((e = tab[index = (n - 1) & hash]) != null) {
        
                    TreeNode<K,V> hd = null, tl = null;
                    do {
        
                        TreeNode<K,V> p = replacementTreeNode(e, null);
                        if (tl == null)
                            hd = p;
                        else {
        
                            p.prev = tl;
                            tl.next = p;
                        }
                        tl = p;
                    } while ((e = e.next) != null);
                    if ((tab[index] = hd) != null)
                        hd.treeify(tab);
                }
            }

1）转换条件

*  表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树
 *  当数组大小小于 64 时，只会触发扩容，不会转化成红黑树

2）链表长度阈值为什么是8？

链表查询的时间复杂度是O (n)，红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要的占用空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。

在考虑设计 8 这个值的时候，参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：

* 0:    0.60653066
      * 1:    0.30326533
      * 2:    0.07581633
      * 3:    0.01263606
      * 4:    0.00157952
      * 5:    0.00015795
      * 6:    0.00001316
      * 7:    0.00000094
      * 8:    0.00000006

意思是，当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一，所以说正常情况下，链表的长度不可能到达 8 ，而一旦到达 8 时，肯定是 hash 算法出了问题，所以在这种情况下，为了让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写代码，使用 HashMap 时，几乎不会碰到链表转化成红黑树的情况，毕竟概念只有千万分之一。

[Java_HashMap]: https://blog.csdn.net/weixin_43935927/article/details/108501752
[Java_HashMap 1]: https://blog.csdn.net/weixin_43935927/article/details/113884949
[Java_HashMap 2]: https://blog.csdn.net/weixin_43935927/article/details/113886585
[Java_HashMap_JDK7]: https://blog.csdn.net/weixin_43935927/article/details/108502329
[Java_HashMap 3]: https://blog.csdn.net/weixin_43935927/article/details/108733304