Java面试题07-HashMap的扩容原理

HashMap的底层结构在1.7和1.8是不同的。
1.7及以前是由数组加链表实现的，
1.8以后是由数组加链表加红黑树实现的。

1.7的HashMap扩容过程

1.7及以前的HashMap扩容的一个过程其实就是将原数组进行一个复制，然后将数组上的链表的元素也进行一个复制，全部复制到新的数组上，然后指向新的数组。

详细过程：
1、先生成新数组
2、遍历老数组中的每个位置上的链表的每个元素
3、取每个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标
4、将元素添加到新数组中去
5、将所有元素转移完了之后，新数组赋值给HashMap的table属性

// 扩容的方法
void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if(oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}
	Entry[] newTable = new Entry[newCapacity];
	//转移元素
	transfer(newTable, initHashSeedAsNeeded(newCapacity));
	table = newTable;
	threshold = (int)Math.min(newCapacity * loadFactor,MAXIMUM_CAPACITY + 1);
}

//转移元素的方法
void transfer(Entry[] newTable,boolean rehash) {
	int newCapacity = newTable.length;
	//双层循环
	//首先遍历数组
	//然后对数组元素进行一个判断
	//如果存在链表结构，重新去计算一个新的hash值
	//放到新的数组中
	for(Entry<K,V> e : table){
		while(null != e) {
			Entry<K,V> next = e.next;
			if(rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			}
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i];
			nextTable[i] = e;
			e = next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.8及以后的HashMap扩容过程

1.8及以后的HashMap底层的扩容机制其实和1.7差不多，只是区别在于如果判断过程中发现某个元素下是红黑树的结构，就需要对这个树进行一个重新计算并且转移。

红黑树在转移的过程中有可能是会被拆分的，原因是每个节点元素重新计算的hash值有可能会不一样，如果一样的话则还是在原来的位置，如果不同的话就是在新的位置，所以HashMap扩容后的元素存储的地址可能会发生变化。

这里源码过多，不再给出。

详细过程：
1、先生成新数组
2、遍历老数组中的每个位置上的链表或者红黑树
3、如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去
4、如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标问题
（1）统计每个下标位置的元素个数
（2）如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置
（3）如果该位置下的元素个数没有超过8，那么则生成一个链表，并将链表的头节点条件到新数组的对应位置
5、所有元素转移完了之后，将新数组赋值给hashMap对象的table属性