HashMap 源码

基础知识

位运算符

  • 位与 &

1 & 1 = 1 ,其余都是 0

1
2
3
4
5
sample :
0011
1010
0010
即 `3 & 10 = 2`
  • 位或 |

0 & 0 = 0 ,其余都是 1

1
2
3
4
5
sample :
0011
1010
1011
即 `3 & 10 = 11`
  • 位异或 ^

相同为 0, 不同为1

1
2
3
4
5
sample :
*0011
1010
1001
即 `3 & 10 = 9`
  • ~

按位取反

1
2
3
4
sample :
0011
1100
即 `~3 = -4`

Tips

& 是都得为1才能得到1 ,| 是只要有1就为1,^ 是相同则为 1。

  • 原码
    第一位是符号位,1 是负数,0是正数
1
2
1000,1000 是 -8
0000,1000 是 +8

因此可用的范围只是后七位,即8进制的数值范围是 [1111 1111,0111 1111],用十进制表示是 -(2^7 -1) ~ (2^7 -1 ) 即 [-127,127]

  • 反码

正数的反码是其原码本身
负数的反码是在符号位不变,其余的按位取反

1
2
+10:[0000 1010]原 == [0000 1010]反
-10:[1000 1010]原 == [1111 0101]反
  • 补码

正数的补码是其原码本身
负数的补码是符号位不变,其余的按位取反,再加一。即

[负数的补码] = [负数的反码] + 1;

1
2
+10:[0000 1010]原 == [0000 1010]反 == [0000 1010]补
-10:[1000 1010]原 == [1111 0101]反 == [1111 0110]补
  • 左移 <<

逻辑左移 N 位,空缺部分补 0

1
2
1 << 3 == 8;
即 0001 => 1000
  • 无符号右移 >>>

逻辑右移 N 位,空缺部分补 0

1
2
8 >>> 3 == 1;
即 1000 => 0001
  • 有符号右移 >>

左边的空出的所有位数根据移位前原来的内容,原来为0就补0,原来为1就补1

注意负数是使用补码进行计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
-8 >>> 3 (-8 无符号右移 3 位)
-8 ==
[1000,0000,0000,0000,0000,0000,0000,1000]原
[1111,1111,1111,1111,1111,1111,1111,0111]反
[1111,1111,1111,1111,1111,1111,1111,1000]补
右移三位(高位补充0) =>
[0001,1111,1111,1111,1111,1111,1111,1111]补
[0001,1111,1111,1111,1111,1111,1111,1111]反
[0001,1111,1111,1111,1111,1111,1111,1111]原
== 2^29 -1
-8 >> 3 (-8 有符号右移 3 位)
-8 ==
[1000,0000,0000,0000,0000,0000,0000,1000]原
[1111,1111,1111,1111,1111,1111,1111,0111]反
[1111,1111,1111,1111,1111,1111,1111,1000]补
右移三位(根据原内容补充) =>
[1111,1111,1111,1111,1111,1111,1111,1111]补
[1111,1111,1111,1111,1111,1111,1111,1110]反
[1000,0000,0000,0000,0000,0000,0000,0001]原
== -1

Tips

对于正数 x 来说,
左移 n 位<<相当于 x * 2^n
右移 n 位>>相当于 x mod 2^n,取余
无符号右移 n 位 >>>相当于 x mod 2^n,取余

对负数 y 来说,
左移 n 位<<相当于 y * 2^n
右移 n 位>>相当于

HashMap 的基本原理

源码解读

全局变量

  • DEFAULT_INITIAL_CAPACITY
1
2
3
4
5
6
7
/**
* The default initial capacity - MUST be a power of two.
* 默认初始化容量,必须是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;//JDK7
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //即16 JDK8
  • MAXIMUM_CAPACITY
1
2
3
4
5
6
7
8
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 最大的容量,必须是2的幂,并且在 [2,2^30]之间
* int 型的最大值为 2^31 -1 ,但 HashMap 的容量必须是 2 的幂,所以最大值只能是 2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
  • DEFAULT_LOAD_FACTOR
1
2
3
4
5
/**
* The load factor used when none specified in constructor.
* 默认的负载因子值,用来计算扩容的临界值,0.75f
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
  • EMPTY_TABLE
1
2
3
4
5
/**
* An empty table instance to share when the table is not inflated.
* 当 table 还没扩容时的实例,即一个空的table
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
  • table ;HashMap 中的存放键值对的单链表数组
1
2
3
4
5
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* 可以随时调整的 table,长度必须是2的幂
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
  • size
1
2
3
4
5
/**
* The number of key-value mappings contained in this map.
* 这个 map 中键值对的数量
*/
transient int size;
  • threshold
1
2
3
4
5
6
7
8
9
/**
* The next size value at which to resize (capacity * load factor).
* 下一次进行扩容的值,即阈值,等于最大容量 * 负载因子
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
//如果 table 是空的时候,即 table == EMPTY_TABLE , threshold 的值就是 table 扩容时的初始容量
int threshold;
  • loadFactor
1
2
3
4
5
6
7
8
9
/**
* The load factor for the hash table.
* hash table 的负载因子
* @serial
*/
// Android-Note: We always use a load factor of 0.75 and ignore any explicitly
// selected values.
//Android-Note: 使用 0.75 这个固定的值,忽略其他明确的值
final float loadFactor = DEFAULT_LOAD_FACTOR;
  • modCount
1
2
HashMap 的结构被修改的次数
结构修改指的是那些 HashMap 中映射数量或者是其内部结构(比如 rehash)的修改

构造函数

好了,现在开始来看构造函数

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
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}

在构造函数中,接收两个参数,一个是初始容量(initialCapacity),一个是负载因子(loadFactor)

从代码中可见,前面都是在进行判断这两个值的合法性,比如初始容量必须大于等于0,如果大于可容纳的最大容量,则赋值为最大值MAXIMUM_CAPACITY(2^30) ,如果小于默认的容量,则赋值为最小容量。
负载因子的必须大于0,并且是个浮点数(Float)

最后一步将初始容量赋值给 threshold
init() 方法是个空方法,忽略不计

put 方法

向 HashMap 中添加一个键值对,并返回 value

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
public V put(K key, V value) {
//当 table 是空的时候,对 table 进行扩容
if (table == EMPTY_TABLE) {
inflateTable(threshold);//①
}
//如果key 是 null,则放入 value并返回旧的值
if (key == null)
return putForNullKey(value);//②
//key 不为 null,计算 key 的 hash 值
int hash =
sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通过 key 的 hash 值和数组 table 的长度计算出这个`键值对`应在数组中的索引值
int i = indexFor(hash, table.length);//③
//获取到当前索引值存放的链表,并进行循环
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果该链表上有一个键值对 e ,并且这个键值对 e 的 hash 值和新放入的键值对的hash相同,并且key值也相同,则将新的 value 替换旧的 value,并返回旧的 value 值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//否则,即当前链表上没有 key 值以及 hash 值相同的键值对,则 modCount 自增
modCount++;
//新增一个键值对
addEntry(hash, key, value, i);//④
//返回 null
return null;
}

① 先看 inflateTable(int toSize) 方法

  • 先计算 table 的容量
  • 再计算新的阈值
  • 创建 table 对象,即 HashMapEntry 数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 扩容 table ,toSize 是要扩大到的容量
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
//计算 table 的容量,因为必须是2的幂,所以通过 roundUpToPowerOf2() 方法计算出大于等于 toSize 值的 2的幂
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
//再计算新的阈值,即 table 容量 * 负载因子,如果超过了最大的容量,则将阈值设置为 table 最大值 + 1
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
// 新建一个 HashMapEntry 对象,即 table
table = new HashMapEntry[capacity];
}

② 再接着看 putForNullKey(V value) 方法

可见 HashMap 是可以存入键值(key) 为 null 的键值对的,并且会将 key = null 的键值对放到数组的第一位,即 table[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
//取出数组中索引为 0 的链表,进行循环,
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
//如果链表中有 key 为 null 的键值对,即该 HashMap 中有 key 为 null 的键值对,则将新值替换旧值,并返回旧值。
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果原来链表中没有 key 为 null 的键值对,将 modCount 自增
modCount++;
//并向链表中添加一个键值对
addEntry(0, null, value, 0);
//返回 null
return null;
}

③ 再看计算索引的方法 indexFor(int hash, int length)
hash -> hash 值
length -> 数组长度

1
2
3
4
5
6
7
8
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
//即相当于 h % length,取余数
return h & (length-1);
}

④ 接着看 addEntry(int hash, K key, V value, int bucketIndex) 方法
这个方法有四个入参分别是

入参 意义
hash key 的 hash 值
key key(键)
value value(值)
bucketIndex 该键值对应该放在 table 中的索引
1
2
3
4
5
6
7
8
9
10
11
12
13
void addEntry(int hash, K key, V value, int bucketIndex) {
//判断当前的键值对数量是否超过阈值
if ((size >= threshold) && (null != table[bucketIndex])) {
//当前的键值对数量大于阈值,且该键值对应放入的索引位置的链表不为空(即发生了 hash 碰撞),则进行扩容操作,扩容2倍
resize(2 * table.length);//⑤
//重新计算 hash 值
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
//重新计算在扩容后的 table 中的索引
bucketIndex = indexFor(hash, table.length);
}
//创建新的节点
createEntry(hash, key, value, bucketIndex);//⑥
}

⑤ 下面看 resize(int newCapacity) 扩容的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void resize(int newCapacity) {
//创建一个局部变量存放原来的 table 的引用
HashMapEntry[] oldTable = table;
//算出旧 table 的长度,即旧 table 的容量
int oldCapacity = oldTable.length;
//如果之前的容量已经达到最大了,修改阈值为最大值并返回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//容量还没达到最大,新建一个 table (链表数组),长度为新的容量(newCapacity)
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
//转移新的键值对,将原来的键值对转移到新的 table 中
transfer(newTable);//⑦
//将新的 table(newTable) 的引用赋值给 table
table = newTable;
//计算新的阈值,即(新的容量 * 负载因子)或者是(最大容量 + 1)的最小值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer() 转移到新 table 的方法

注意,这份方法在转移键值对到新的table中时,会将链表的顺序给倒序了,插入时插到链表的最前面
即原来链表是 [A] -> [B] -> [C],转移到新的链表后变成 [C] -> [B] -> [A] {假设扩容后这三个键值对的 hash 索引还相同}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void transfer(HashMapEntry[] newTable) {
//计算新的 table 的容量
int newCapacity = newTable.length;
//对旧的 table 数组进行循环
for (HashMapEntry<K,V> e : table) {
//下面对链表进行循环
while(null != e) {
HashMapEntry<K,V> next = e.next;
//计算当前节点在新 table 中的索引值
int i = indexFor(e.hash, newCapacity);
//取新的 table 中第i个位置的链表中第一个键值对,赋值给 e.next
e.next = newTable[i];//①
//将当前的 键值对 放入新 table 的第一个位置
newTable[i] = e;//②
//将原来的链表上的下一个节点赋值给 e
e = next;
}
}
}

图解
HashMap_transfe

在 for 循环时,e 指向旧 table 数组中的某条链表

  • 第一次循环时,e 指向该链表的第一个键值对,next 指向 e.next 即第二个键值对

    PS.我们假设转移前后我们的这两个键值对的 hash 值计算出来的索引仍然相同

  • 将新 table 数组第 i 个位置的链表接到 e 的后面,再把 e 放到 newTable[i] 的位置

  • 将 next 赋值给 e ,继续循环,直到链表循环结束

createEntry(int hash, K key, V value, int bucketIndex) 创建新的键值对

新插入的键值对会插入到链表最前面

1
2
3
4
5
6
7
8
9
void createEntry(int hash, K key, V value, int bucketIndex) {
//将该键值对对应的索引的位置的键值对table[bucketIndex] 的引用赋值给局部变量 e
HashMapEntry<K,V> e = table[bucketIndex];
//新建一个键值对,即新放入的 hash,key,value,该键值对的 next 是原来的在这个索引位置的键值对
//可见插入键值对时会插入到链表的最前面
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);⑦
//对 size 自增,即键值对数量 + 1
size++;
}

HashMapEntry 构造方法,可见传入的第四个参数 n 会被放到这个新的 entry 的 next ,即放到第四个参数在链表位置上的前面。

1
2
3
4
5
6
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

remove 方法

从 HashMap 中通过 key 移除某个键值对,当这个键值对存在时,返回该 key 对应的 value,若不存在,则返回 null

1
2
3
4
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}

往下看 removeEntryForKey(key) 方法

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
37
38
39
40
41
42
43
44
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
//若该 HashMap 的长度为 0 ,说明没有键值对,直接返回 null
return null;
}
//获取该 key 对应的 hash 值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//获取该 hash 值所对应的索引
int i = indexFor(hash, table.length);
//获取该索引处的链表
HashMapEntry<K,V> prev = table[i];
//将该链表赋值给 e
HashMapEntry<K,V> e = prev;
//对链表进行循环,当链表上的节点 e 不为 null 时
while (e != null) {
将链表的下一个节点赋值给 next
HashMapEntry<K,V> next = e.next;
Object k;
//当该节点的 hash 值和所要删除的 key 的 hash 值相同,并且 key 值相同,或者 key 不为 null,则找到了所要删除的键值对
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//自增修改次数
modCount++;
//将 HashMap 键值对数量减一
size--;
if (prev == e)
//如果 prev == e ,即刚好链表中的第一个节点就是所要查找的节点,则直接将链表的 next 指向第二个节点,就把该节点删除了
table[i] = next;
else
//否则将 e 节点的下一个节点赋值给,prev 的下个节点,即将 prev 的 next 指向 e.next
prev.next = next;
e.recordRemoval(this);
//返回删除的节点 e
return e;
}
prev = e;
e = next;
}
//返回 e ,这里已经循环链表完毕,e 为 null
return e;
}
  • 当第一个节点就是所要查询的节点时候
    Screen Shot 2018-04-09 at 18.03.52

此时 prev == e,则直接将 e.next(即 next)直接赋值给 table[i],则把 node a 直接删除了

  • 从链表中不能查到该节点

Screen Shot 2018-04-09 at 18.16.32

prev 和 e 是链表对象,每次循环后 e 会先往链表下走,直到查找到满足条件的节点,如果都不满足,则 e == null 此时会退出循环,并返回 e ,即返回 null。

  • 从链表中能查到该节点

Screen Shot 2018-04-09 at 18.22.04

若找到了满足条件的节点 node b(即 e),则将 prev.next = e.next ,等效于将 node b 从链表中删除了

Java 8 中的 put 方法

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
* 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
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前 table 为 null 或者数组长度为 0
if ((tab = table) == null || (n = tab.length) == 0)
//扩容,并将扩容后的数组赋值给 tab ,n 则为当前数组的长度
n = (tab = resize()).length;
//下面的 `(n - 1) & hash]` 就是 Java 7 中计算索引的方法
//如果计算出的索引处要插入的地方为 null ,则直接新增一个 Node 键值对
//此时将 tab[index] 赋值给了 p ,即 p = tab[index]
if ((p = tab[i = (n - 1) & hash]) == null)
//如果走到这里,可以说明该键值对的 key 在原先的 HashMap 中是不存在的
tab[i] = newNode(hash, key, value, null);
else {
//要插入的索引处已经有 Node 了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//假如该索引处的 Node p 的 hash 值和新放入的键值对的hash相同,并且key值也相同
//将 p 赋值给 e
e = p;
else if (p instanceof TreeNode)
//key 不相同的话,并且 p 是红黑树的一个节点,则直接插入红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//key 不相同,并且不为红黑树,即链表
for (int binCount = 0; ; ++binCount) {
//进行循环
//如果 p 的下个节点为空(即 p 是最后一个节点)
if ((e = p.next) == null) {
//将该需要插入的节点插到链表尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果链表长度超过 8 ,则转为红黑树
treeifyBin(tab, hash);
//跳出循环
break;
}
//如果 p 的下个节点 e 不为空,且 e 的 hash 值等于插入的节点的 hash 并且 key 相同,即 e 就等于需要插入的节点,则直接跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//将链表的下个节点 `e` 在循环中赋值给 `p`
p = e;
}
}
if (e != null) { // existing mapping for key
//如果 e 不为空,即原来的 table 中存在相同的 key ,e 为旧的 node
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//替换掉旧值
e.value = value;
afterNodeAccess(e);
//返回 key 对应的旧值
return oldValue;
}
}
//如果 HashMap 中不存在该 key,会走到这里
//mod 次数自增
++modCount;
//如果键值对数量大于阈值,则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

总结下思路

  1. 在插入时,计算出 key 值对应的 hash 值,接着计算 hash 值对应的索引
  2. 判断该索引处是否为空
    2.1 如果为空,则直接插入该键值对
    2.2 如果不为空,说明该索引处已经存在『链表』或者『红黑树』了
    2.2.1 如果『链表』的第一个节点或者『红黑树』的根节点的 key 值等于要插入的 key 并且 hash 值相同,则进行替换
    2.2.2 否则,如果是『红黑树』,则进行插入
    2.2.3 否则,如果是『链表』,则进行循环链表插入(如果链表长度超过 8,则转换为红黑树)
    2.2.4 经过 2.2.1 - 2.2.3 之后,如果原来中有相同的 key ,则直接 return 旧值
    2.3 原 HashMap 中没有插入的 key,则键值对数量自增,判断扩容,return null

Java 8 中的 resize() 方法

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
//获取旧的数组引用
Node<K,V>[] oldTab = table;
//计算旧数据的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取旧阈值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果旧数组长度大于等于最大容量,则直接返回旧数组
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新数据容量 = 旧数据容量左移一位,即 * 2
//如果新数组容量小于最大值,且旧数组容量大于等于默认长度(16)
//同时将阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 如果原来的 threshold 大于0则将容量设为原来的 threshold
// 在第一次带参数初始化时候会有这种情况
newCap = oldThr;
} else {
// 在默认无参数初始化会有这种情况
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16 * 0.75 = 12
}
if (newThr == 0) {
//如果新的阈值为 0
//计算新的阈值
float ft = (float)newCap * loadFactor;
//如果新的容量小于最大容量且新的阈值也小于最大容量
//则新的阈值等于 ft ,否则设置为 Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新的阈值赋值给 threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新数组赋值给 table
table = newTab;
//进行扩容复制
if (oldTab != null) {
//旧数组不为 null ,进行循环
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 将当前索引处的第一个节点赋值给 e
if ((e = oldTab[j]) != null) {
//将旧数组的引用置为 null
oldTab[j] = null;
if (e.next == null)
//如果当前索引处只有一个节点,则直接计算在新数组中的索引并赋值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果 e 是红黑树,则调用红黑树的方法进行处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//处理链表长度为 1 ~ 8 的情况
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) {
//!!这里 e.hash & oldCap 不是计算索引,计算索引应该是 e.hash & (oldCap -1)
//如果节点 e 的 hash 值和 oldCap 计算出来值为 0 ,说明在扩容后该节点的索引相同,不需要移动索引
if (loTail == null)
//第一次才会走入这个地方
//如果低位尾部节点为 null,将 e 赋值给头部节点,即链表第一个节点
loHead = e;
else
//否则(即第二次以后),将 e 赋值给尾部节点的 next,即 loTail.next
loTail.next = e;
//再将 e 赋值给尾部节点 loTail,
loTail = e;
}
else {
//否则,该节点需要移动索引位置到新的索引去
//方法同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);// 将 next 赋值给 e,直到没有 next ,即链表循环完毕
if (loTail != null) {
//如果低位的尾节点不为 null ,则将其 next 置为 null
loTail.next = null;
//并将低位的头节点放到该低位索引处
newTab[j] = loHead;
}
if (hiTail != null) {
//如果高位的尾节点不为 null ,则将其 next 置为 null
hiTail.next = null;
//并将高位的头节点放到该高位索引处
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

这里重点看一下处理链表长度为 1~ 8 的情况

首先我们知道,对于一个键值对节点,其索引的计算方式为 index = hash(key) & (n - 1)

假设现在有两个节点 Node ANode B ,其 key 的 hash 值分别为 hash(a)、hash(b),n = 16

计算其索引过程如下

n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash(a) 1111 1111 1111 1111 0000 1111 0000 0101
hash(b) 1111 1111 1111 1111 0000 1111 0001 0101

计算索引 index = hash(key) & (n - 1)

index(a) 0000 0000 0000 0000 0000 0000 0000 0101 == 5
index(b) 0000 0000 0000 0000 0000 0000 0000 0101 == 5

Node ANode B 计算出来的索引相同,则放在同一个链表中,当进行扩容时,数组的长度会变为原来长度的两倍
即 n = n * 2;
扩容后要重新计算索引

n - 1 0000 0000 0000 0000 0000 0000 0001 1111
hash(a) 1111 1111 1111 1111 0000 1111 0000 0101
hash(b) 1111 1111 1111 1111 0000 1111 0001 0101
计算索引 index = hash(key) & (n - 1)

index(a) 0000 0000 0000 0000 0000 0000 0000 0101 = 5
index(b) 0000 0000 0000 0000 0000 0000 0001 0101 = 21 = 5 + 16

由此可见,当同一个链表中的节点在进行重新索引时,并不需要重新通过 index = hash(key) & (n - 1) 方法计算索引,同一个链表中的节点在扩容后要么还在当前索引index处,要么在 index + oldCap处。

所以当扩容时重新计算索引,可以不需要重新计算 hash 值,节省了计算 hash 的时间,并且只需要看原来的 hash 值新增的那个高位的值是 1 还是 0 即可⑨,如果是 1 ,则新的索引为 index = index + olcCap,否则 index 不变

⑨计算方法

e.hash & oldCap 判断是否为 0

Screen Shot 2018-04-24 at 09.58.14

更简单来说,

  • 第一次:

    e -> A,next -> B,
    loHead -> e(A) ,loTail -> e(A)
    e -> next(B)

  • 第二次:

    e -> B,next -> C,loTail -> A
    loTail.next -> e(B)
    此时 loHead 和 loTail 指向同一个内存地址,所以 loHead.next = e(B)
    loTail -> e(B),e -> next(C)

  • 第三次:

    e -> C,next -> null,loTail -> B
    loTail.next -> e(C)
    则此时 B.next 指向了 C ,而 loHead.next 指向的也是 B ,即 loTail,所以此时 loHead.next.next -> C
    loTail -> e(C),e -> next(null)

  • 结束循环
    loHead = A -> B -> C

通过上面的分析也可以看出,Java 8 在扩容过程中,链表的顺序是不变的,链表在扩容后还保持原来的顺序,而 Java 7 是倒序的