🔍基于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. 扩容原理

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
final Node<K,V>[] resize() {
// 使用局部变量持有table
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;
}
else if (oldThr > 0) // 使用扩容阈值初始化容量
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
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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)首先得到新的容量值和新的扩容阈值,默认都是原来大小的两倍。

(2)然后根据新容量创建新的数组。

(3)最后把元素从旧数组中迁移到新数组中。

JDK1.7中,迁移数据的时候所有元素都重新计算了hash,并根据新的hash重新计算数组中的位置

JDK1.8中,这个过程进行了优化:

如果当前节点是单独节点(后面没有接着链表),则根据该节点的hash值与新容量减一的值按位与得到新的地址

如果当前节点后面带有链表,则根据每个节点的hash值与旧数组容量进行按位与的结果进行划分

  • 如果得到的值为0,这些元素会被分配回原来的位置
  • 如果得到的结果不为0,则分配到新位置,新位置的下标为当前位置下标加上旧数组容量

还有一种情况是当前节点是树节点,那么会调用一个专门的拆分方法进行拆分

HashMap支持动态扩容,但是不支持动态缩容。

动态缩容就需要写在remove方法中,这样可能会导致remove方法的时间复杂度从O(1)上升为O(N)