java中的基于jdk1.8的hashmap的get方法、put方法和resize扩容方法源码浅析

冷不防 2022-01-29 06:34 192阅读 0赞

HashMap类成员变量释义，代码如下：

static final int DEFAULT_INITIAL_CAPACITY = 16;//默认初始容量大小16
    	static final int MAXIMUM_CAPACITY = 1073741824;//hashmap最大容量是2的30次方
    	static final float DEFAULT_LOAD_FACTOR = 0.75F;//默认加载因子
    	static final int TREEIFY_THRESHOLD = 8;//当同一个槽位的链表的长度大于8时，转成红黑树，查询效率更高
    	static final int UNTREEIFY_THRESHOLD = 6;//树大小为6，就转回链表
    	static final int MIN_TREEIFY_CAPACITY = 64;//数容量最小64
    	transient Node<K, V>[] table;//哈希桶数组，真正存放键值对的数据结构
    	transient Set<Map.Entry<K, V>> entrySet;
    	transient int size;//表示保存的键值对数量
    	transient int modCount;//HashMap被改变的次数,扩容的次数
    	int threshold;//阈值，当size大小大于这个数进行扩容,threshold = 容量*加载因子
    	final float loadFactor;//加载因子实际大小

put方法，代码如下：

public V put(K paramK, V paramV) {//onlyIfAbsent表示是否替换原值
    //参数evict我们可以忽略它，它主要用来区别通过put添加还是创建时初始化数据的
    		return (V) putVal(hash(paramK), paramK, paramV, false, true);
    	}

final V putVal(int paramInt, K paramK, V paramV, boolean paramBoolean1, boolean paramBoolean2) {
    		Node[] arrayOfNode;
    		int i;
    //如果表table不存在或者空表，进行初始化一个表出来，
    		if (((arrayOfNode = table) == null) || ((i = arrayOfNode.length) == 0)) {
    //resize()不仅用来调整大小，还用来进行初始化配置
    			i = (arrayOfNode = resize()).length;
    		}
    		int j;
    		Object localObject1;
    //判断在(j = i - 1 & paramInt)位置是否有元素，没有则进行直接创建node节点进行保存键值对
    		if ((localObject1 = arrayOfNode[(j = i - 1 & paramInt)]) == null) {
    			arrayOfNode[j] = newNode(paramInt, paramK, paramV, null);
    		} else {//如果在(j = i - 1 & paramInt)位置有值
    			Object localObject3;
    			Object localObject2;//把带插入的元素赋值localObject2，用来查看是不是待插入的元素已经有了，有就替换
    //当前元素hash值和参数paramInt相等，并且当前元素key值和参数paramK相等，表示要插入的元素就是当前元素，说明要插入的已经存在，则进行当前元素值替换，即修改当前元素value值
    			if ((hash == paramInt)
    					&& (((localObject3 = key) == paramK) || ((paramK != null) && (paramK.equals(localObject3))))) {
    				localObject2 = localObject1;//要插入的元素就是localObject1，localObject1已经存在，把它赋值给localObject2，方便后面进行value值修改
    			} else if ((localObject1 instanceof TreeNode)) {// localObject1是一个树节点
    				localObject2 = ((TreeNode) localObject1).putTreeVal(this, arrayOfNode, paramInt, paramK, paramV); // 把节点添加到树中
    			} else {// 是链表结构，要把待插入元素挂在链尾
    				for (int k = 0;; k++) {//循环链表
    					if ((localObject2 = next) == null) {//当前节点下一个节点为空，即当前节点是该链表的最后一个元素
    						next = newNode(paramInt, paramK, paramV, null);//创建一个新节点挂在当前节点的后面
    						if (k < 7) {//当前链表大小小于７时，跳出循环
    							break;
    						}
    						treeifyBin(arrayOfNode, paramInt);//当前链表大小大于等于７时，树化
    						break;
    					}
    					if ((hash == paramInt) && (((localObject3 = key) == paramK)
    							|| ((paramK != null) && (paramK.equals(localObject3))))) {// 找到了对应元素，就可以停止了
    						break;
    					}
    					localObject1 = localObject2;// 继续向后
    				}
    			}
    			if (localObject2 != null) { // localObject2就是被替换出来的元素，这时候就是修改元素值
    				Object localObject4 = value;
    				if ((!paramBoolean1) || (localObject4 == null)) {
    					value = paramV;
    				}
    				afterNodeAccess((Node) localObject2);
    				return (V) localObject4;
    			}
    		}
    		modCount += 1;
    		if (++size > threshold) {// size太大，达到了容量和加载因子的乘积，需要扩容
    			resize();
    		}
    		afterNodeInsertion(paramBoolean2);// 默认也是空实现，允许我们插入完成后做一些操作
    		return null;
    	}

下面是get方法源码解析

public V get(Object paramObject) {
    		Node localNode;
    		return (localNode = getNode(hash(paramObject), paramObject)) == null ? null : value;
    	}

final Node<K, V> getNode(int paramInt, Object paramObject) {
    		Node[] arrayOfNode;
    		int i;
    		Node localNode1;
    //如果table表有值，并且在(i - 1 & paramInt)位置有值则把值赋值给localNode1
    		if (((arrayOfNode = table) != null) && ((i = arrayOfNode.length) > 0)
    				&& ((localNode1 = arrayOfNode[(i - 1 & paramInt)]) != null)) {
    			Object localObject;
    //如果当前元素hash和参数paramInt相等，且当前元素key值和参数paramObject相等，则当前元素就是我们要找的元素，该元素就是上面赋值的localNode1，直接返回
    			if ((hash == paramInt) && (((localObject = key) == paramObject)
    					|| ((paramObject != null) && (paramObject.equals(localObject))))) {
    				return localNode1;
    			}
    			Node localNode2;
    //到这一步，说明上面没有找到hash值和key值都相等的节点node，如果当前元素有下一个节点，赋值给localNode2
    			if ((localNode2 = next) != null) {
    				if ((localNode1 instanceof TreeNode)) {//如果上一个节点localNode1是红黑树类型，从红黑树取出元素节点
    					return ((TreeNode) localNode1).getTreeNode(paramInt, paramObject);
    				}
    //不是红黑数，代码执行下面循环，是链表结构
    				do {
    					if ((hash == paramInt) && (((localObject = key) == paramObject)
    							|| ((paramObject != null) && (paramObject.equals(localObject))))) {//如果hash值和key值都相同，则是我们要找的元素节点，返回
    						return localNode2;
    					}
    				} while ((localNode2 = next) != null);//继续查找下一个节点
    			}
    		}
    		return null;
    	}

扩容resize方法如下：

final Node<K, V>[] resize() {
    		Node[] arrayOfNode1 = table;//把当前旧表赋值给arrayOfNode1
    		int i = arrayOfNode1 == null ? 0 : arrayOfNode1.length;
    		int j = threshold;
    		int m = 0;
    		int k;
    		if (i > 0) {
    			if (i >= 1073741824) {//如果table长度大于hashmap最大容量值MAXIMUM_CAPACITY，则不进行扩容了，直接扩大阈值，从而可以尽量存放更多键值对
    				threshold = Integer.MAX_VALUE;
    				return arrayOfNode1;
    			}
    			if (((k = i << 1) < 1073741824) && (i >= 16)) {//如果table扩大两倍小于容量最大值，且table表长度大于16
    				m = j << 1;//阈值扩大两倍赋值m
    			}
    		} else if (j > 0) {//如果table表长度等于０，且阈值大于０，把阈值赋值给table表作为table表的大小
    			k = j;
    		} else {//如果table表长度等于０，且阈值等于０，则table表大小和阈值使用默认值16和12
    			k = 16;
    			m = 12;
    		}
    		if (m == 0) {//如果table表长度等于０，且阈值大于０，重新给阈值计算值
    			float f = k * loadFactor;
    			m = (k < 1073741824) && (f < 1.07374182E9F) ? (int) f : Integer.MAX_VALUE;
    		}
    		threshold = m;
    //根据扩大的k值创建一个新的更大空node节点数组
    		Node[] arrayOfNode2 = (Node[]) new Node[k];
    		table = arrayOfNode2;//新node数组赋值table
    		if (arrayOfNode1 != null) {//如果旧node节点数组不为空
    			for (int n = 0; n < i; n++) {//循环遍历旧数组
    				Object localObject1;
    				if ((localObject1 = arrayOfNode1[n]) != null) {
    					arrayOfNode1[n] = null;//把每一个遍历的节点清空，方便回收
    					if (next == null) {//当前元素节点是最后一个，因为next为空
    						arrayOfNode2[(hash & k - 1)] = localObject1;把当前元素localObject1放在新数组的(hash & k - 1)位置上
    					} else if ((localObject1 instanceof TreeNode)) {//如果是红黑树，放在红黑树中
    						((TreeNode) localObject1).split(this, arrayOfNode2, n, i);
    					} else {//如果是链表
    						Object localObject2 = null;
    						Object localObject3 = null;
    						Object localObject4 = null;
    						Object localObject5 = null;
    						Node localNode;
    						do {
    							localNode = next;
    							if ((hash & i) == 0) {
    								if (localObject3 == null) {
    									localObject2 = localObject1;
    								} else {
    									next = ((Node) localObject1);
    								}
    								localObject3 = localObject1;
    							} else {
    								if (localObject5 == null) {
    									localObject4 = localObject1;
    								} else {
    									next = ((Node) localObject1);
    								}
    								localObject5 = localObject1;
    							}
    						} while ((localObject1 = localNode) != null);
    						if (localObject3 != null) {
    							next = null;
    							arrayOfNode2[n] = localObject2;
    						}
    						if (localObject5 != null) {
    							next = null;
    							arrayOfNode2[(n + i)] = localObject4;
    						}
    					}
    				}
    			}
    		}
    		return arrayOfNode2;
    	}

上述扩容代码释义：

上述的最后else分支做的就是将原指定槽位的所有节点移到新的数组中。原则是在移动当前节点的时候，防止下一个节点丢失，要记录下一个节点；

Node<K,V> loHead = null, loTail = null;//低位链表的头、尾指针

Node<K,V> hiHead = null, hiTail = null;//高位链表的头、尾指针

也就是将原来的一条链表拆成两条链表，低位链表的数据将会到新数组的当前下标位置（原来下标多少，新下标就是多少），高位链表的数据将会到新数组的当前下标+当前数组长度的位置（原来下标多少，新下标就是多少+当前数组长度）。

计算新的槽位下标是看当前hash与旧数组长度相与，结果为0的话那么新槽位下标还是当前的下标，如果非零，那么新槽位下标是当前下标+当前数组长度。举个?：hash为1，当前数组长度为8，1&8 为 0，所以下一个槽位就是1；hash为9，当前数组长度为8，9&8 不为 0，所以下一个槽位就是1+8 = 9。

为什么可以这样，难道说原来在一个槽位的所有数据在新数组中就最多只能分到两个槽位吗？事实证明，是的！

看看HashMap的put操作：

算法1.计算hash：(h = key.hashCode()) ^ (h >>> 16)，自己与自己的高16位异或

算法2.计算槽位：(tab.length - 1) & hash，hash与数组长度-1相与

可以看出第一步采用的是死算法，计算的结果为固定结果，对长度不同的数组插入位置不会造成影响，这里忽略。造成影响的是第二个步骤：通过算出的固定结果与不同长度的数组相与的结果会有差异，这就会造成不同的数据在不同长度的数组中保存的下标会不同。

观察一下，上述分槽用的算法是当前hash与长度相与，如果为0，那么新槽位不变。否则新槽位为原来数组长度+当前下标；让事实验证一下：

1. key1算出来的hash为1（0001），当前数组长度为8，计算槽位：

通过算法2：1&7 ==> 001&111 ==> 1,所以在1号槽位

扩容后当前数组长度为16，重新计算：

通过算法2：1&15 ==> 0001&1111 ==> 1,所以在1号槽位

2. key2算出来的hash为9（1001），当前数组长度为8，计算槽位：

通过算法2：1&7 ==> 1001&111 ==> 1,所以在1号槽位

扩容后当前数组长度为16，重新计算：

通过算法2：1&15 ==> 1001&1111 ==> 1001,所以在9号槽位。

结果显示还确实是这样，分析一下：从计算槽位的算法可以看出，能在一个槽位的所有数据，它们hash低k位都是相等的，k为当前数组长度-1的二进制位数。比如：hash为1的key1和hash为9的key2在数组长度为8中是一个槽，那么key1和key9的hash的低3位（数组长度为8，8-1=7，7二进制有3位）都是一样的。

那么当数组扩容，长度会加倍。那么重新计算方式唯一会造成差异的就是hash的倒数第k+1位。

因为原来是hash&(111)7，k为3，那么现在算法是hash&(1111)15,k为4了。

所以造成差异的就是看倒数第k+1位是不是0，如果是0，那么第二次计算的结果不会变化：如001&111和001&1111与是一样的结果，所以新槽位不会变，但9就不同了，1001&111 和 1001&1111结果会差个值，那个值就是倒数第k+1位所代表的十进制值（倒数第k+1=4，对应二进制1000，十进制8），也就是原来的数组长度，新槽位就为当前槽位+原来数组值。

参考：[https://blog.csdn.net/u013494765/article/details/77837338][https_blog.csdn.net_u013494765_article_details_77837338]

参考：https://www.cnblogs.com/skywang12345/p/3310835.html

参考：https://blog.csdn.net/AJ1101/article/details/79413939

参考：https://blog.csdn.net/weixin\_42340670/article/details/80503369

参考　：https://blog.csdn.net/the\_one\_and\_only/article/details/81665098  
参考：　https://blog.csdn.net/AJ1101/article/details/79413939

参考：　[https://blog.csdn.net/u010412719/article/details/52049347][https_blog.csdn.net_u010412719_article_details_52049347]（关于jdk老版本取值死循环问题）

[https_blog.csdn.net_u013494765_article_details_77837338]: https://blog.csdn.net/u013494765/article/details/77837338
[https_blog.csdn.net_u010412719_article_details_52049347]: https://blog.csdn.net/u010412719/article/details/52049347