HashMap源码分析：put(K key, V value)

爱被打了一巴掌 2023-10-05 09:57 35阅读 0赞

> HashMap的put方法的重点主要有**key的hash值的计算、hash冲突的解决办法、红黑树的结构、红黑树如何保持树平衡（烧脑）、红黑树链表相互转化的条件**等。接下来将在分析put方法的过程中逐个分析这几类重点。

（1）put方法。**key的hash值的计算**。特点：允许key为空，当key为null时，默认key的hash值为0：

public 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);
        }
    
        public native int hashCode();//JVM赋值

（2）putVal(hash(key), key, value, false, true);

下面是putVal的方法：

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value     //是否替换已存在的key对应的value值；是，则不替换；否则替换
     * @param evict if false, the table is in creation mode.        //是否处于创建模式，false，代表处于创建模式
     * @return previous value, or null if none                      //返回值：如果之前值不为空，则返回当前key所对应的之前的value值；否则返回null
     */ 
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    			   boolean evict) {
    	Node<K,V>[] tab; Node<K,V> p; int n, i;                     //tab存储当前table值，即当前map对象；p：当前数据存储；n:table表的大小；i:下标，即当前数据要存储的位置
    	if ((tab = table) == null || (n = tab.length) == 0)         //判断当前map是否为空，为空则为当前map扩容创建一个table;并为当前变量tab赋值当前table,为当前n赋值变量tab.length
    		n = (tab = resize()).length;
    	if ((p = tab[i = (n - 1) & hash]) == null)                  //判断当前位置是否已有node占用，没有的话则新建；        
    //(n-1)&hash值为了保证每次设置的index下标位置是均匀的。因为n是2的幂次方，hash为2的幂次方，这样n-1的话即所有位置都为1，与hash与操作就得到了hash值，是有规律的。         
    		tab[i] = newNode(hash, key, value, null);
    	else {		                                                //如果当前的位置已有元素占用
    		Node<K,V> e; K k;
    		if (p.hash == hash &&
    			((k = p.key) == key || (key != null && key.equals(k))))   
     //如果被占用的位置的元素和添加的元素hash值与key值相同，则直接覆盖 
    			e = p;                                        
    		else if (p instanceof TreeNode)                        //如果当前p对应的node的类型是红黑树，则将当前当前key、value值传入并存入红黑树中
    			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    		else {
    			for (int binCount = 0; ; ++binCount) {             //开启循环，找到存放当前key、value位置
    				if ((e = p.next) == null) {                    //如果当前p对应的下个节点为空，则直接将当前key、value存入表中
    					p.next = newNode(hash, key, value, null);
    					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st   //树化
    						treeifyBin(tab, hash);      
    					break;
    				}
    				if (e.hash == hash &&
    					((k = e.key) == key || (key != null && key.equals(k)))) //如果e即p的下个指针对应的节点与当前存储的key值相同，则跳出循环，不做任何操作
    					break;
    				p = e;                                                      //上面条件都不符合的话，则将下个指针赋值给当前p节点，继续for循环，重复上面的操作 
    			}
    		}
    		if (e != null) { // existing mapping for key                        //是否允许替换旧值
    			V oldValue = e.value;
    			if (!onlyIfAbsent || oldValue == null)
    				e.value = value;
    			afterNodeAccess(e);
    			return oldValue;
    		}
    	}
    	++modCount;                                       //用于统计当前hashmap被修改的次数
    	if (++size > threshold)                           //判断当前table大小是否已超出，超出则扩容
    		resize();
    	afterNodeInsertion(evict);                        //是否删除最老的元素，
    	return null;
    }

**hash冲突的解决办法：**

① 如果被占用的位置的元素和添加的元素hash值与key值相同，则直接覆盖

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;

② 如果当前是链表中的node，与其他node的hash值冲突，则会存储在冲突的node节点的下一个节点

for (int binCount = 0; ; ++binCount) {
    	if ((e = p.next) == null) {
    		p.next = newNode(hash, key, value, null);
    	}
    	p = e;
    }

③ 如果当前是红黑树中的node，则会根据**任一节点左、右子树的高度，相差不得超过两倍的规则左旋或者右旋达到树平衡**，

这个后面具体分析。

else if (p instanceof TreeNode){
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    }

**链表长度超过8且table长度超过64时转化为红黑树**

for (int binCount = 0; ; ++binCount) {
    	···
    //当值超过8时，转为红黑树
    	if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    			treeifyBin(tab, hash);
    		break;
    	}
        ···
    }
    
    
    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
    	int n, index; Node<K,V> e;
    	//如果tab的长度不够64，则扩容，不会转化为红黑树
    	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    		resize();
    	else if ((e = tab[index = (n - 1) & hash]) != null) {
    		···
    	}
    }

关于putVal()中的afterNodeInsertion(evict）这个方法，我在打debugger时，发现这个方法在使用时并没有做操作，觉得很奇 怪，后来百度了一下，原来这个方法是需要重写才能使用，可以看一下这两篇博客加深理解：  
[LinkedHashMap，源码解读就是这么简单][LinkedHashMap]

[LRU算法以及缓存][LRU]

**JDK1.8的HashMap的put方法原理总结**：  
(1) 构成：HashMap是由数组+链表+红黑树组成的。链表单位是Node,node是由hash、key、value、next组成。红黑树的实体是 TreeNode（parent、left、right、prev，red）。当链表长度超过8且tab的长度大于等于64时，链表才会转化为红黑树；当链表长度超过8但是tab的长度小于64时，只是扩容稀释链表但不转化为红黑树；当红黑树长度小于6时，转化为链表。  
(2) 初始化：初始化容量threshold为16(tableSizeFor(initialCapacity)获得)，默认扩容倍数为0.75  
(3) 存储：首先使用hash(key)生成key的hash值，如果hash值冲突则与冲突的node节点比较，相同则替换，不同则存储在冲突的 node节点的下个指针的位置。

--------------------

红黑树结构以及转化

首先分析链表长度超过8时的情况：

putVal()中的treeifyBin(tab, hash)树化方法

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
       treeifyBin(tab, hash);

由代码可见，当链表长度超过8时，则进入treeifyBin方法：

/**
         * Replaces all linked nodes in bin at index for given hash unless
         * table is too small, in which case resizes instead.
         */
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  //当map为空或者当map的整个长度没有超过最小容积64时，则扩容，不树化
                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);							//do-while循环体,将当前链表转化为TreeNode结构
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);                                    //将TreeNode中的数据进行左右子树平衡
            }
        }

treeify方法：

/**
             * Forms tree of the nodes linked from this node.
             * @return root of tree
             */
            final void treeify(Node<K,V>[] tab) {
                TreeNode<K,V> root = null;
                for (TreeNode<K,V> x = this, next; x != null; x = next) {
                    next = (TreeNode<K,V>)x.next;
                    x.left = x.right = null;
                    if (root == null) {
                        x.parent = null;
                        x.red = false;
                        root = x;
                    }
                    else {
                        K k = x.key;
                        int h = x.hash;
                        Class<?> kc = null;
                        for (TreeNode<K,V> p = root;;) {
                            int dir, ph;
                            K pk = p.key;
                            if ((ph = p.hash) > h)
                                dir = -1;
                            else if (ph < h)
                                dir = 1;
                            else if ((kc == null &&
                                      (kc = comparableClassFor(k)) == null) ||
                                     (dir = compareComparables(kc, k, pk)) == 0)
                                dir = tieBreakOrder(k, pk);
    
                            TreeNode<K,V> xp = p;
                            //判断对应的子树节点是否为null
                            if ((p = (dir <= 0) ? p.left : p.right) == null) {
                                x.parent = xp;
                                if (dir <= 0)
                                    xp.left = x;
                                else
                                    xp.right = x;
                                root = balanceInsertion(root, x);
                                break;
                            }
                        }
                    }
                }
                moveRootToFront(tab, root);
            }

这个方法主要是将当前节点与父节点通过hash值判断出当前节点时左子树还是右子树，若当前hash值小于父节点，则dir<=0放在左子树，若当前hash值大于父节点，则dir>0放在右子树。判断完成之后，通过balanceInsertion(root,x)平衡当前树形，在balanceInsertion(root,x)方法中，设置节点的颜色，通过rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p)方法平衡左子树，通过rotateRight(TreeNode<K,V> root, TreeNode<K,V> p)方法平衡右子树。最后，将树化后的树体重新插入到整个table当中。

平衡树balanceInsertion(root,x)分析，

首先，平衡树的规则：

*  每个节点或为黑，或为红，根节点为黑色
 *  如果一个节点是红色，则它的儿子是黑色
 *  从任一个节点到其叶子的所有简单路径都包含相同数目的黑色节点
 *  每个红色节点的两个子节点，一定都是黑色（叶子节点包含NULL）

代码分析：

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                        TreeNode<K,V> x) {
                x.red = true;//因为是插入的节点，所以默认设置当前节点为红色；
                for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                    //xp:x的父节点；xpp:xp的父节点；xppl:xp的父节点的左子树；xppr:xp的父节点的右子树；
                    //若当前为根节点，则设置节点颜色为黑色，并且返回当前节点
                    if ((xp = x.parent) == null) {
                        x.red = false;
                        return x;
                    }
                    //如果xp的颜色为黑色或者xp为顶级节点，则不需要平衡
                    else if (!xp.red || (xpp = xp.parent) == null)
                        return root;
                    //xpp为父节点，xp=xppl=xpp的左节点，xppr为xpp的右子节点，x为xp的子节点
                    if (xp == (xppl = xpp.left)) {
                        //此时的x节点为红色，xp节点也为红色，红色节点不能相邻，需要改变节点颜色
                        if ((xppr = xpp.right) != null && xppr.red) {
                            xppr.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            //若xp为xpp的右子节点，x为xp的右子节点，则左旋
                            if (x == xp.right) {
                                root = rotateLeft(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            //若x是xp的左子节点，xp不是空
                            if (xp != null) {
                                xp.red = false;
                                //xpp不为空，则右旋
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateRight(root, xpp);
                                }
                            }
                        }
                    }
                    else {//xpp的左子节点为空时
                        if (xppl != null && xppl.red) {
                            //改变xpp的左子节点的颜色
                            xppl.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            //x是xp的左子节点，进行右旋
                            if (x == xp.left) {
                                root = rotateRight(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            if (xp != null) {
                                xp.red = false;
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateLeft(root, xpp);
                                }
                            }
                        }
                    }
        
                }
            }

左旋右旋方法通过举例的方式说明一下（看的脑子快炸了终于弄懂，才画出来下面这幅图，希望各位能看懂，有问题的话欢迎指正）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70][]

除了将链表树化之外，也存在一种情况，将节点插入树形中。

else if (p instanceof TreeNode)
          e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

putTreeVal()有些长，就不放源码了，直接说一下思路吧：

和链表转化为树的思路差不多，都是先判断dir的值来摆放各个节点的位置，是左子树还是右子树，摆放完成之后，进行平衡树节点（平衡树示例见上面红黑树结构图），平衡完树节点，将root节点摆放至最顶级节点。

[LinkedHashMap]: https://xiaozhuanlan.com/topic/8702165439
[LRU]: https://www.dazhuanlan.com/2019/12/27/5e04f0ec7f769/?__cf_chl_jschl_tk__=7aa66c76c15123bae9c0db9b1ef175abe467028a-1600132169-0-ATDTpKxUKJmcmo3NMEUjgVfdz8X6JG8y-C1vWlus90_PFRtY39Db5vkdEMPKxPmNW7Pgyo_9IfBIW5eR0P07yGfSEaOPKfV0P8a8NCW4x5AfEg4tQIvE0tdBPVvx2eFq2A88yMeaKQkRQVp-SCGgsYx6WCE05lEiKevq8gkz1T97Bi5dxTjoos-aveMsbiRG6F3CE_AsmtZNZ5ykxLIYyQG5e1jencS3FLQhjTAZ7w_VYh0HTUnz_kiLvkISCs5Ni9MQooSwc80VCSfBhBz07WqNStXY0nwmu3D9BwgARiWax4VCpMQke_AIowvLBD-5bg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020101414525093.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NBVF9jd2Rz,size_16,color_FFFFFF,t_70