|
1
2
3
4
|
/** * The default initial capacity - MUST be a power of two.（默认初始容量——必须是2的n次幂。） */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16（16 = 2^4） |
|
1
2
3
|
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } |
|
01
02
03
04
05
06
07
08
09
10
|
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);//tableSizeFor(initialCapacity)方法是重点！！！ } |
|
01
02
03
04
05
06
07
08
09
10
11
12
|
/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } |
|
1
2
3
4
5
6
7
8
|
public HashMap(int initialCapacity, float loadFactor) { …… int capacity = 1; while (capacity < initialCapacity) { capacity <<= 1; } ……} |
|
01
02
03
04
05
06
07
08
09
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
37
38
39
40
41
42
43
44
|
final Node<K,V>[] resize() { //扩容 //---------------- -------------------------- 1.计算新容量（新桶） newCap 和新阈值 newThr。 --------------------------------- Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length;//看容量是否已初始化 int oldThr = threshold;//下次扩容要达到的阈值。threshold(阈值) = capacity * loadFactor。 int newCap, newThr = 0; if (oldCap > 0) {//容量已初始化过了：检查容量和阈值是否达到上限《========== if (oldCap >= MAXIMUM_CAPACITY) {//oldCap >= 2^30，已达到扩容上限，停止扩容 threshold = Integer.MAX_VALUE; return oldTab; } // newCap < 2^30 && oldCap > 16，还能再扩容：2倍扩容 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // 扩容：阈值*2。（注意：阈值是有可能越界的） } //容量未初始化 && 阈值 > 0。 //【啥时会满足层判断：使用HashMap(int initialCapacity, float loadFactor)或 HashMap(int initialCapacity)构造函数实例化HashMap时，threshold才会有值。】 else if (oldThr > 0) newCap = oldThr;//初始容量设为阈值 else { //容量未初始化 && 阈值 <= 0 ： //【啥时会满足这层判断：①使用无参构造函数实例化HashMap时；②在“if (oldCap > 0)”判断层newThr溢出了。】 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) {//什么情况下才会进入这个判断框:前面执行了else if (oldThr > 0)，并没有为newThr赋值，就会进入这个判断框。 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //------------------------------------------------------2.扩容：------------------------------------------------------------------ @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//扩容 table = newTab; //--------------------------------------------- 3.将键值对节点重新放到新的桶数组里。------------------------------------------------ ……//此处源码见下文“二、2.” return newTab; } |
|
01
02
03
04
05
06
07
08
09
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
final Node<K,V>[] resize() { //扩容方法 //---------------- -------------------------- 1.计算新容量（新桶） newCap 和新阈值 newThr： ------------------------------------------- …… //此处源码见前文“一、3.” //---------------------------------------------------------2.扩容：------------------------------------------------------------------ …… //此处源码见前文“一、3.” //--------------------------------------------- 3.将键值对节点重新放到新的桶数组里：------------------------------------------------ if (oldTab != null) {//容量已经初始化过了： for (int j = 0; j < oldCap; ++j) {//一个桶一个桶去遍历，j 用于记录oldCap中当前桶的位置 Node<K,V> e; if ((e = oldTab[j]) != null) {//当前桶上有节点，就赋值给e节点 oldTab[j] = null;//把该节点置为null（现在这个桶上什么都没有了） if (e.next == null)//e节点后没有节点了：在新容器上重新计算e节点的放置位置《===== ①桶上只有一个节点 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode)//e节点后面是红黑树：先将红黑树拆成2个子链表，再将子链表的头节点放到新容器中《===== ②桶上是红黑树 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { //遍历链表，并将链表节点按原顺序进行分组《===== ③桶上是链表 next = e.next; if ((e.hash & oldCap) == 0) {//“定位值等于0”的为一组： if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else {//“定位值不等于0”的为一组： if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //将分好的子链表放到newCap中： if (loTail != null) { loTail.next = null; newTab[j] = loHead;//原链表在oldCap的什么位置，“定位值等于0”的子链表的头节点就放到newCap的什么位置 } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; //“定位值不等于0”的子节点的头节点在newCap的位置 = 原链表在oldCap中的位置 + oldCap } } } } } return newTab; } |
原文：https://www.cnblogs.com/zhuxiaopijingjing/p/12334349.html