🔍基于JDK1.8的HashMap源码分析。

1. 基本知识


  • HashMap始于JDK 1.5,作者是大师Doug Lea
  • HashMap提供所有可选的映射操作,并允许使用null键和null值。
  • HashMap由数组+链表+红黑树组成,链表的时间复杂度为O(n),红黑树的时间复杂度为O(logn)。
  • HashMap并非线程安全,当存在多个线程同时写入HashMap时,会导致数据覆盖和环。

2. 基本属性

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
/** 默认初始化容量 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/** 最大容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/** 默认负载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** 树化阈值 */
static final int TREEIFY_THRESHOLD = 8;

/** 链化阈值 */
static final int UNTREEIFY_THRESHOLD = 6;

/** 最小的树化容量 */
static final int MIN_TREEIFY_CAPACITY = 64;

/** 哈希桶数组,第一次put时初始化,长度为2的次幂 */
transient Node<K,V>[] table;

/** 存储键值对集合 */
transient Set<Map.Entry<K,V>> entrySet;

/** 键值对数量 */
transient int size;

/** 修改次数 */
transient int modCount;

/** 树化阈值 */
int threshold;

/** 负载因子 */
final float loadFactor;

3. 构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 带初始化容量和负载因子的构造
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);
}

// 带初始化容量的构造
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 无参构造
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

可以看到,在构造方法中,并没有进行任何的初始化,只是进行了一些简单的赋值处理。

4. hash方法

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash计算方法:调用hashcode()进行位运算,将hashcode右移16位取得hashcode的高16位,与原hashcode的低16位进行异或运算。

index计算方法:将hash值与数组长度-1进行与运算得到数组下标,计算公式index = hash & (table.length - 1)

5. tableSizeFor方法

1
2
3
4
5
6
7
8
9
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;
}

返回一个大于等于给定目标容量的最小2的幂次方。

如果n = 0,则初始化结果为1。

第一次:n |= n >>> 1

右移1位:000001xxxxxx -> 0000001xxxxx

或运算:n = 0000011xxxxx

第二次:n |= n >>> 2

右移2位:000011xxxxx -> 000000011xxx

或运算:n = 000001111xxx

右移1位做或运算后,最高位有2个1;

右移2位做或运算后,最高位有4个1;

右移4位做或运算后,最高位有8个1;

右移8位做或运算后,最高位有16个1;

右移16位做或运算后,最高位有32个1。

int占32bit,最多就32个1,这时候已经大于MAXIMUM_CAPACITY(1 << 30 = 2147483647 / 2),所以取值到了MAXIMUM_CAPACITY

那么为什么必须为2的整数次幂呢?

为了提高计算与存储效率,同时减少哈希碰撞的几率。

确定数组下标采用的算法是 hash & (n - 1),n为哈希桶数组的大小。n为2的整数次幂,n - 1的二进制形式为000..11111,这个二进制值与任何值进行与运算的结果都在指定区间[0, n-1]。

正例:n = 8,n - 1 = 7,二进制0111,任何与0111进行与运算的结果都会映射到[0,7],即落入给定的8个哈希桶中,存储空间利用率100%。

反例:n = 7,n - 1 = 6,二进制0110,任何与0110进行与运算的结果都会映射到{0, 2, 4, 6}四个桶中,而不是[0, 6]区间,存储空间利用率只有 4 / 7 * 100%。

6. put方法

1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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
/**
* @param hash 根据键计算的hash
* @param key 键
* @param value 值
* @param onlyIfAbsent true只是在值为空的时候存储数据,false都存储数据
* @param evict 不关心
* @return 返回被覆盖的值,如果没有覆盖则返回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;
// 第一次put值的时候会触发resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 找到具体的数组下标
// 如果此位置没有值,那么直接初始化一下Node并放置在这个位置即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果数组该位置有值
else {
Node<K,V> e; K k;
// 首先,判断该位置的第一个数据和要插入的数据,key是不是相等
// 如果是,取出这个结点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该结点是代表红黑树的结点,调用红黑树的插值方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果该结点是代表链表的结点,则插入到链表的最后面
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD = 8,
// 如果新插入的值是链表中的第8个会触发树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在该链表中找到了相等的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 使用新结点覆盖旧结点
p = e;
}
}
// e != null 说明存在旧值的key与要插入的key相等
// 进行值覆盖,然后返回旧值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果HashMap由于新插入这个值导致size查过阈值,则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

过程总结:

(1)第一次put的时候,会触发resize方法,经典懒加载,数组初始化。

(2)计算数组长度和hash的与运算结果得到key在数组中的具体下标,从而得到数组该位置的第一节点。

(3)如果第一节点为空,那么直接新建一个节点并放在这个位置即可。

(4)如果第一节点非空, 那么判断第一节点key和当前key是否相等。

(5)如果相等,则取出这个节点。

(6)如果不相等,则判断这个节点的类型是红黑树节点还是链表节点。

(7)如果是红黑树节点,则调用红黑树的插值方法。

(8)如果是链表节点,则遍历整个链表,如果存在相同key,则取出这个节点并break,否则直接插入到链表最后面,如果链表长度超过树化阈值8,那么进行树化操作。

(9)判断取出的节点是否为空,非空则进行值覆盖,然后返回旧值。

(10)如果因为新插入值导致size超过阈值,则进行扩容,并返回null。

7. get方法

1
2
3
4
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.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
/**
* @param hash 根据键计算的hash
* @param key 键
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断第一个节点是不是就查找的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 判断节点是否为红黑树节点
if (first instanceof TreeNode)
// 调用红黑树的获取值的方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 节点为链表节点,直接遍历链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

过程总结:

(1)计算key的hash,根据hash值找到数组下标:hash & (length - 1)。

(2)判断该位置的第一个元素是否为所查找的,如果是直接返回。

(3)判断该元素类型是否为红黑树节点,如果是则调用红黑树的方法获取结点。

(4)到这里说明元素是链表节点,直接遍历链表,寻找key相同的结点。

(5)最后,表示没有找到,直接返回null。

8. 负载因子

负载因子 = 填入哈希表中元素数量 / 哈希桶的长度,负载因子决定HashMap的数据密度。

扩容阈值 = 哈希表当前容量 * 负载因子,负载因子决定HashMap的扩容阈值。

  • 负载因子过大,产生数据碰撞的几率越高,数组中的链表也会越长,会造成查询和插入的比较增次数多。『降低空间开销,提高查找成本。』
  • 负载因子过小,触发扩容的几率越高,产生数据碰撞的几率越小,查询和插入的比较次数少。『降低时间开销,提高空间成本。』
  • 因此在负载因子的选择上,要做到时间和空间的折中。

举例:

loadFactor = 1时,hash数组中的16个值全部填充的时候才会扩容,造成链表或者红黑树的长度变大,hash碰撞的次数变多;

loadFactor = 0.5时,hash数组中的值填充一半开始扩容,造成空间利用率降低。

关于负载因子0.75的证明

通过预测桶是否为空,桶空与非空的概率为0.5

s表示哈希桶的长度,n表示已添加的元素个数,负载因子loadFactor = n / s

对于每个元素,桶非空的概率为1/s,桶空的概率为1 - 1/s

根据二项式定理,桶空的概率:

1
2
P(0) = C(n, 0) * [(1 / s) ^ 0] * [(1 - 1 / s) ^ (n - 0)] 
=> P(0) = (1 - 1 / s) ^ n

令这个概率值等于 1/2,那么:

1
(1 - 1 / s) ^ n = 1 / 2

然后进行极限变换求值:

1
2
3
4
5
6
(1 - 1 / s) ^ n
= [1 + 1/ (-s)] ^ [(-s) * (- n / s)]
= 1 / 2
当s -> +∞时,[1 + 1 / (-s)] ^ (-s) -> e
即 e ^ (- n / s) = 1 / 2
两边同时取对数,n / s = ln 2

从而,loadFactor = ln2 = 0.69314718056

个人猜测,负载因子在[ln2, 0.75]这个区间内都可以保证良好的性能。

9. 树化阈值

在理想情况下,使用随机哈希码,节点出现的频率在哈希桶中遵循泊松分布,同时给出了桶中元素个数(链表长度)和命中概率的对照表:

  • 0: 0.60653066
  • 1: 0.30326533
  • 2: 0.07581633
  • 3: 0.01263606
  • 4: 0.00157952
  • 5: 0.00015795
  • 6: 0.00001316
  • 7: 0.00000094
  • 8: 0.00000006
  • more: 小于千万分之一

从上可以看出当桶中元素长度达到8的时候,每个碰撞位置的链表长度为8的概率为一千万分之六,超过8的概率小于一千万分之一。

也就是说,当哈希码分布均匀时,同一个位置上出现8个元素的概率为千万分之六,侧面说明如果链表长度达到了8,key的hashcode()出现了问题,这个时候需要红黑树来保证性能。

10. 扩容原理

JDK1.7扩容

源码分析

扩容,创建新的哈希桶数组,进行数据迁移。源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;

// 创建新的table
Entry[] newTable = new Entry[newCapacity];
// 判断新的table中的元素是否需要重新求hash值,源码在下面
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;//数组扩容赋值给table
// 计算新的扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

数据迁移,将旧元素重新计算hash值然后放入到新的table里面。源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历桶
for (Entry<K,V> e : table) {
// 采用头插法
while(null != e) {
// 记录当前节点的下一个节点
Entry<K,V> next = e.next; // sign A
// 重新计算哈希
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 新的哈希值对应的数组下标
int i = indexFor(e.hash, newCapacity);
// 插入新的节点
e.next = newTable[i];
newTable[i] = e;
// 迭代
e = next;
}
}
}

总结:

  1. 创建新的数组newTable;
  2. 遍历桶,将table中的节点全部重新计算hash值,采用头插法插入到newTable中;
  3. 将newTable赋值给table;
  4. 重新计算扩容阈值 = 新的容量 * 负载因子。

并发问题

原始情况


死链情况

两个线程:线程A和线程B

(1)假设线程A执行到sign A,情况如下:


(2)此时,穿插线程B执行,执行完了整个迁移过程,结果如下:


(3)线程A继续执行,使用头插法插入5节点,那么就会导致5节点和6节点相互引用导致链表成环:


数据丢失

两个线程:线程A和线程B

(1)假设线程A执行到sign A,情况如下:


(2)此时,穿插线程B,执行完了整个迁移过程,结果如下:


(3)线程A继续执行,使用头插法插入5节点,然后继续插入next节点,由于6节点的next为null,会导致7节点丢失:


最后扩容结束,由于线程B先执行了table = newTable,线程A后执行,那么A丢失的newTable最终成为真正的哈希桶,丢失数据。

JDK1.8扩容

源码分析

扩容,创建新数组,数据迁移采用尾插法。源码如下:

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
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 创建新的哈希桶数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 遍历原始数组下标
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果原始数组下标对应位置有元素
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 当前节点是个独狼
if (e.next == null)
// 直接计算新数组中的位置
newTab[e.hash & (newCap - 1)] = e;
// 当前节点为红黑树节点
else if (e instanceof TreeNode)
// 单独处理,进行节点拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 当前节点为链表节点
else { // preserve order
// 根据hash值和原始数组长度重新计算索引值
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 如果索引值为0,那么新数组下标等于原数组下标
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果索引值不为0,新数组下标为原数组下标+原数组长度
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

总结:

  1. 先判断当前table是否进行过初始化,如果没有则初始化默认值,已经初始化则扩容为原来的2倍。
  2. 扩容后对原始table进行遍历,将数据迁移到新的table中:
    1. 如果当前位置节点是个独狼,那么直接重新计算数组下标并放在新的table中;
    2. 如果当前位置节点为红黑树节点,那么需要单独处理,进行重新拆分操作;
    3. 如果当前节点节点为链表节点,那么根据哈希值和原数组长度重新计算索引值,索引值为0则新数组下标与原数组下标相同,否则新数组下标为原数组下标+原数组长度。

并发问题

采用尾插法可以防止在多线程情况下链表成环的产生,但是依然非线程安全。

1
2
3
4
5
6
7
8
9
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// ...
}

putVal的第六行代码中判断是否出现哈希碰撞,如果线程A和线程B都在进行put操作,并且hash函数计算出的插入下标是相同的的,当线程A执行完后被挂起,而线程B在该下标处插入了元素,完成了正常的插入,这样数据就悄无声息的覆盖掉了,从而线程不安全。

JDK1.8中由头插法改为尾插法的变更原因:

  1. 可以保证节点的有序性。(根据缓存的时间局部性原则,可以减少查找次数。)
  2. 防止多线程下链表成环。

另外,JDK1.8中不需要为每个节点重新计算哈希,只需要根据原来的哈希值和原数组长度进行与运算得到新的索引值。