概述

从本文你可以学习到:

  1. 什么时候会使用 HashMap ?他有什么特点?
  2. 你知道 HashMap 的工作原理吗?
  3. 你知道 get 和 put 的原理吗?equals()hashCode() 的都有什么作用?
  4. 你知道 hash 的实现吗?为什么要这样实现?
  5. 如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量,怎么办?
  6. 为什么 HashMap 的容量是 2 的 n 次幂的形式?

在说明这些问题的同时, 我从 JDK7 —— JDK8 的 HashMap 的变化来说明开发人员对这个数据结构的优化,重点放在了 put() 函数resize() 函数,还结合了《码出高效》这本书指出了 HashMap 在并发情况下表现出来的问题。

注意:源码可能与 JDK 中实际代码略有不同, 这里面 JDK7 版以《码出高效》为准,JDK8 版本以网络版本为准,意在说明某个函数功能, 便于理解。

两个重要参数说起

在HashMap中有两个很重要的参数,容量(Capacity)和负载因子 (Load factor) 。

Capacity 就是 bucket 的大小,Load factor就是 bucket 填满程度的最大比例。如果对迭代性能要求很高的话,不要把 capacity 设置过大,也不要把 load factor 设置过小。当 bucket 中的 entries 的数目大于 capacity *load factor 时,就需要调整 bucket 的大小为当前的2倍。

put函数的实现

put函数大致的思路为:

  1. 对key的 hashCode() 做 hash ,然后再计算 index ;
  2. 如果没碰撞直接放到 bucket 里;
  3. 如果碰撞了,以链表的形式存在 buckets 后;
  4. 如果碰撞导致链表过长 (大于等于 TREEIFY_THRESHOLD ),就把链表转换成红黑树;
  5. 如果节点已经存在就替换 old value (保证 key 的唯一性);
  6. 如果 bucket 满了 (超过 load factor * current capacity),就要 resize。

具体代码的实现如下:

JDK7 的 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
public V put(K key, V value) {
int hash = hash(key);
int i = indexFor(hash, table.length);
//此循环通过 hashCode 返回值找到对应的数组下标位置
//如果 equals 结果为真,则覆盖原值, 如果都为 false ,则添加元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key的 hash 是相同的,那么在进行如下判断
//key 是同一个对象或者 equals 返回为真, 则覆盖原来的Value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
//如果元素的个数达到 threshold 的扩容阈值且数组下标位置已经存在元素,则进行扩容
if ((size++ >= threshold) && (null != table[bucketIndex])){
//扩容 2 倍, size 是实际存放元素的个数,而 length 是数组的容量大小(capacity)
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

//插入元素时,应该插入在头部,而不是尾部
void createEntry(int hash. K key, V value, int bucketIndex){
//不管原来的数组对应的下标是否为 null ,都作为 Entry 的 BucketIndex 的 next值
Entry<K,V> e = table[bucketIndex]; (***)
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}

关于并发的问题
如上源码, 在 createEntry() 方法中,新添加的元素直接放在 slot 槽( slot 哈希槽,table[i] 这个位置)使新添加的元素在下一次提取后可以更快的被访问到。 如果两个线程同时执行 (***) 处时, 那么一个线程的赋值就会被另一个覆盖掉, 这是对象丢失的原因之一。 我们构造一个 HashMap 集合,把所有元素放置在同一个哈希桶内, 达到扩容条件后,观察一下 resize() 方法是如何进行数据迁移的。示例代码和图可参考《码出高效》P204。

JDK8 的 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
public V put(K key, V value) {
// 对 key 的 hashCode() 做 hash
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// tab 为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算 index,并对 null 做处理,这里观察到 index 的计算 i = (n - 1) & hash
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
// 这个位置有节点,且与新节点相同,进行覆盖
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 这个位置有节点,且节点类型为 TreeNode
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // 检测是否该从链表变成树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过 load factor*current capacity,resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

可以看出,JDK 7 是先对 size++ 进行检查, 如果超过阈值, 则扩容,最后把节点放入 table。
而 JDK 8 相反,先把节点放入, 放入后的 size 若超出, 则扩容。

hash 与 hashCode()

在 get 和 put 的过程中,计算下标时,先对 hashCode 进行 hash 操作,然后再通过 hash 值进一步计算下标,如下图所示:

hash计算下标
hash计算下标

关于 hash 函数 与 hashCode 的关系,这里,为了避免碰撞,JDK7 进行了四次扰动,JDK8 简化了这个操作,只是高低位做了异或,但核心思想都是增强 hash 中各位的相关性,减少碰撞。

JDK7 中的 hash

1
2
3
4
5
6
7
8
9
10
11
12
final int hash(Object k) {
int h = hashSeed;
//如果 key 是字符串类型,就使用 stringHash32 来生成 hash 值
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//一次散列
h ^= k.hashCode();
//二次散列
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK8 中的 hash

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

扩容(超级重要!)

JDK7 的扩容分析

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
void resize(int newCapacity) {
//创建一个扩容后的新数组
Entry[] newTable = new Entry[newCapacity];
//将当前数组中的键值对存入新数组
//JDK8 移除 hashSeed 计算, 因为计算时会用到 Random.nextInt(), 存在性能问题
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//用新数组替换旧数组
table = newTable;
//注意,MAX 时 1<<30, 如果 1<<31 则成 Integer 的最小值:-2147483648
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
//外部传入参数时,指定新表大小为:2*oldTable.length
int newCapacity = newTable.length;
//遍历现有数组中的每一个单链表的头 entry
for (Entry<K,V> e : table) {
//如果此 slot 上存在元素,则进行遍历, 直到 e==null,退出循环
while(null != e) {
Entry<K,V> next = e.next;
//当前元素总是直接放在数组下标的 slot 上,而不是放在链表最后
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//根据新的数组长度,重新计算此 entry 所在下标i
int i = indexFor(e.hash, newCapacity);
//把原来 slot 上的元素作为元素的下一个
e.next = newTable[i];
//新迁移过来的节点直接放置在 slot 位置上
newTable[i] = e;
//继续向下遍历
e = next;
}
}
}

关于并发的问题
如果 resize 完成, 执行了 table = newTable ,则后续的元素就可以在新表上进行插入操作。如果多个线程同时执行了 resize ,每个线程又都会 new Entry[newCapcity] 这是线程内的局部数组对象,线程之间是不可见的。迁移完成后,resize 的线程会赋值给 table 线程共享变量,从而覆盖其他线程的操作,因此在“新表”中进行插入操作的对象会被无情抛弃。总结一下, HashMap 在高并发场景中, 新增对象丢失原因是:

  • 并发赋值时被覆盖。
  • 已遍历区间新增元素会丢失。
  • “新表被覆盖”。
  • 迁移丢失。在迁移过程中, 有并发时, next 被提前置成 null。

JDK8 的扩容分析

例如我们从 16 扩展为 32 时,具体的变化如下所示:

resize引起的hash
resize引起的hash

因此元素在重新计算 hash 之后,因为 n 变为 2 倍,那么 n-1 的 mask 范围在高位多 1bit (红色),因此新的 index就会发生这样的变化:
index
index

因此,我们在扩充 HashMap 的时候,不需要重新计算 hash ,只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了,是0的话索引没变,是 1 的话索引变成 “原索引 + oldCap”。可以看看下图为 16 扩充为 32 的 resize 示意图:
resize
resize

这个设计确实非常的巧妙,既省去了重新计算 hash 值的时间,而且同时,由于新增的 1bit 是 0 还是 1 可以认为是随机的,因此 resize 的过程,均匀的把之前的冲突的节点分散到新的 bucket 了

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
final Node<K,V>[] resize() {
//oldTab 为当前表的哈希桶
Node<K,V>[] oldTab = table;
//当前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length
//当前的阈值
int oldThr = threshold;
//初始化新的容量和阈值为 0
int newCap, newThr = 0;
//如果当前容量大于 0
if (oldCap > 0) {
//超过最大值就不再扩充了,就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//没超过最大值,就扩充为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧的容量大于等于默认初始容量 16, 那么新的阈值也等于旧的阈值的两倍
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;//此时新表的容量为默认的容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值为默认容量 16 * 默认加载因子 0.75f = 12
}
if (newThr == 0) {//如果新的阈值是 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) {
//把每个 bucket 都移动到新的 buckets 中
for (int j = 0; j < oldCap; ++j) {
//取出当前的节点 e
Node<K,V> e;
//如果当前桶中有元素,则将链表赋值给 e
if ((e = oldTab[j]) != null) {
//将原哈希桶置空以便 GC
oldTab[j] = null;
//如果当前链表中就一个元素,(没有发生哈希碰撞)
if (e.next == null)
//直接将这个元素放置在新的哈希桶里。
//注意这里取下标是用哈希值与桶的长度-1。由于桶的长度是2的n次方,这么做其实是等于一个模运算。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果发生过哈希碰撞 ,而且是节点数超过8个,转化成了红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果发生过哈希碰撞,节点数小于 8 个。则要根据链表上每个节点的哈希值,依次放入新哈希桶对应下标位置。
else { // preserve order
//因为扩容是容量翻倍,所以原链表上的每个节点,现在可能存放在原来的下标,即 low 位, 或者扩容后的下标,即 high 位。 high 位 = low 位 + 原哈希桶容量
//低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
//高位链表的头节点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//临时节点 存放 e 的下一个节点
do {
next = e.next;
//这里又是一个利用位运算 代替常规运算的高效点:利用哈希值与旧的容量,可以得到哈希值去模后,是大于等于 oldCap 还是小于 oldCap,等于 0 代表小于 oldCap,应该存放在低位,否则存放在高位
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);
//将低位链表存放在原 index 处,
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位链表存放在新 index 处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

此段代码来源:CSDN博客,采取了一些删改,注释太多太影响阅读。。

JDK 7 与 JDK 8 中关于 HashMap的对比

  1. JDK 8 为红黑树 + 链表 + 数组的形式,当桶内元素大于 8 时,便会树化
  2. hash 值的计算方式不同 (jdk 8 简化);
  3. 1.7 table 在创建 hashmap 时分配空间,而 1.8 在 put 的时候分配,如果 table 为空,则为 table 分配空间;
  4. 在发生冲突,插入链中时,7 是头插法,8 是尾插法
  5. 在 resize 操作中,7 需要重新进行 index 的计算,而 8 不需要,通过判断相应的位是 0 还是 1,要么依旧是原 index,要么是 oldCap + 原 index

总结

我们现在可以回答开始的几个问题,加深对 HashMap 的理解:

  1. 什么时候会使用 HashMap?他有什么特点?
    是基于 Map 接口的实现,存储键值对时,它可以接收 null 的键值,是非同步的,HashMap 存储着 Entry(hash, key, value, next) 对象。
  2. 你知道 HashMap 的工作原理吗?
    通过 hash 的方法,通过 put 和 get 存储和获取对象。存储对象时,我们将 K / V 传给 put 方法时,它调用 hashCode 计算 hash 从而得到 bucket 位置,进一步存储,HashMap 会根据当前 bucket 的占用情况自动调整容量 (超过 Load Facotr 则 resize 为原来的 2 倍)。获取对象时,我们将 K 传给 get ,它调用 hashCodeO() 计算 hash 从而得到 bucket 位置,并进一步调用 equals() 方法确定键值对。如果发生碰撞的时候,Hashmap 通过链表将产生碰撞冲突的元素组织起来,在 Java 8 中,如果一个 bucket 中碰撞冲突的元素超过某个限制 (默认是 8 ),则使用红黑树来替换链表,从而提高速度。
  3. 你知道 get 和 put 的原理吗?equals() 和 hashCode() 的都有什么作用?
    通过对 key 的 hashCode() 进行 hashing,并计算下标 ( (n-1) & hash ),从而获得 buckets 的位置。如果产生碰撞,则利用 key.equals() 方法去链表或树中去查找对应的节点
  4. 你知道hash的实现吗?为什么要这样实现?
    在 Java 1.8 的实现中,是通过 hashCode() 的高 16 位异或低 16 位实现的:(h =k.hashCode()) ^ (h >>> 16) ,主要是从速度、功效、质量来考虑的,这么做可以在 bucket 的 n 比较小的时候,也能保证考虑到高低 bit 都参与到 hash 的计算中,同时不会有太大的开销。
  5. 如果 HashMap 的大小超过了负载因子 ( load factor ) 定义的容量,怎么办?
    如果超过了负载因子 (默认0.75),则会重新 resize 一个原来长度两倍的 HashMap,并且重新调用 hash 方法。
  6. 为什么 capcity 是 2 的幂?
    因为 算 index 时用的是(n-1) & hash,这样就能保证 n-1 是全为 1 的二进制数,如果不全为 1 的话,存在某一位为 0,那么 0,1与 0 与的结果都是 0,这样便有可能将两个 hash 不同的值最终装入同一个桶中,造成冲突。所以必须是 2 的幂。

更多数据结构

请访问我的博客-数据结构分类