Java基础:JDK8 HashMap源码及数据结构分析
HashMap 是 Java 中非常重要的集合类型,其具有快速存储,快速查找(时间复杂度非常低,非效非常高),自动扩容等特点,在实际开发中经常用到。
关于 HashMap 特性,底层原理也是面试中被问到概率极高的问题,因为 HashMap 涉及到好几个基本数据结构及相关算法知识,如组数,链表,二叉树及变种,Hash算法等。所以有必要对其深入理解。
哈希表
HashMap 使用了基本的数据结构,先了解下有助于理解。详细可能考 数据结构与算法(一):数组、链表、哈希表。
哈希表(Hash Table):,提供键(Key) 和值(Value)映射关系。只要给出 key ,就可以高效查找到映射的 Value,时间复杂度接近于 Ο(1),在哈希表中添加,删除,查找等操作,性能非常高 。
哈希表在本质上也是一个数组,通过 哈希函数 将 Key 的哈希值转换为数组的索引,使 key:hashcode -> index
建立映射关系。
例如一个长度为 8 的数组,key 为 001121,使用取模运算,转换为数组下标 index = hashcode("001121") % Array.length = 1420036703 / 8 = 7
。
哈希冲突
通过哈希函数得出的元素在数组中的索引位已被占用, 就出现了哈希冲突。将哈希值转换为有限的数组索引,很大概率出现哈希冲突的问题。解决此问题通常有两种方式:一种是开放 寻址法,一种是 链表法(数组+链表)。
HashMap 用到了链表法,数组中的每一个元素不仅是一个 Entry
对象,还可能是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时,只需插入到对应的链表中即可。
链表法缺点:如果链表越来越长,则链表查找的性能就会越来越差,在 HashMap 中执行插入和查询操作的时间复杂度就提高到了 O(n)。(HashMap 是遍历到链表尾节插入)。
JDK 7 的 HashMap 的数据结构是基于 哈希表+链表。
JDK 8 对 HashMap 的数据结构进行了优化,引入了 红黑树,即采用了 哈希表+链表 / 红黑树 的数据结构,当链表长度超过 8 时,则将链表树化,这样就避免了超长链表的缺点,红黑树的查询插入的时间复杂度是 O(logn),提高了性能。
HashMap
相关特性
Java 语言中,要了解某一功能特性,最好的方式是阅读源码上的注释,JDK 源码的注释是非常严谨和规范的。这一点值的学习。
HashMap 是基于 哈希表 的 Map 接口的实现,提供所有可选的 Map 操作。
- 允许 Key 为 null 值和 Value 为 null 值。
- 不同步,非线程安全。
- 不保证有序(如插入顺序),也不保证恒定时间顺序不变(若扩容的话则会重新分布)。
假设哈希函数将元素适当地分布在存储桶(Buckets)之间,为基本的 get/put
操作提供了稳定的性能。迭代 Collection 视图所需的时间与 HashMap 实例的容量(capacity:桶的数量)及其大小(键/值映射的元素数量)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。
源码分析
类继承
1 | public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { |
HashMap 继承自父类(AbstractMap
),实现了Map
、Cloneable
、Serializable
接口。
- Map 接口定义了一组通用的操作。
- Cloneable 接口表示可以进行拷贝,在HashMap中,实现的是浅层次拷贝,即拷贝的是对象的引用,而不是对象本身,被拷贝对象的改变会影响被拷贝的对象。
- Serializable 接口表示 HashMap 实现了序列化,设置了序列化版本号。即
HashMap
对象会保存至本地,之后可以恢复。
构造方法
HashMap 实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中存储桶的数量,初始容量只是创建哈希表时的容量。
size(个数):Map 中 Key-Value 元素的个数。
Capacity(容量):是哈希表中存储桶(Buckets)的数量,初始容量(initialCapacity)只是创建哈希表时的容量,默认是
16
,最大容量是1073741824
。loadFactor(负载因子):是在哈希表的容量自动扩容之前,衡量哈希表满表的系数,默认是
0.75f
。当哈希表中的元数个数超过了负载因子和当前容量的乘积时,则认为满表并对哈希表进行重置(即,内部数据结构被重建),使得新哈希表的存储桶数大约是之前桶数的两倍。
默认负载因子(0.75f)在时间和空间成本之间提供了一个较好的权衡。较高的值会减少空间开销,但会增加查找成本。
设置初始容量,应考虑 Map 中预期的元数个数及其负载因子,以最大程序地减少重新哈希操作的次数。
如果设置了初始容量且大于最大容量除以负载因子的值,则不会发生任何重新哈希操作。附加参考load factor in HashMap。
threshold(扩容前阀值):
threshold = capacity * loadFactor
,当size
大于threshold
时会执行resize
扩容操作。
成员变量:
1 | /** |
HashMap 构造方法:
1 | /** |
public HashMap(int initialCapacity, float loadFactor)
在此构造方法中设置了
threshold
的值, 这个值是扩容前的阀值,当 HashMap 的size
大于threshold
时,就执行resize()
,也就是扩容。扩容操作是在调用
putVal
方法添加元素时触发的,源码如下:1
2
3
4
5
6
7final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//...........省略........
if (++size > threshold)
//size 大于 threshold,执行扩容
resize();
//...........省略........
}构造方法中
this.threshold = tableSizeFor(initialCapacity)
不易理解,若写成this.threshold = tableSizeFor(initialCapacity) * this.loadFactor
,就更易理解threshold = capacity * loadFactor
的定义。注意,此构造方法中并没有对
table
这个成员变量初始化,而是被推迟到第一次执行put
方法时赋值,初始化table
会调用resize()
方法,在resize
方法中对threshold
进行重新赋值。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
47transient Node<K,V>[] table;
public V put(K key, V value) {
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;
if ((tab = table) == null || (n = tab.length) == 0)
//第一次执行 put 方法时进入,调用 resize 方法
n = (tab = resize()).length;
//.......省略......
}
final Node<K,V>[] resize() {
//第一次执行put, table == null
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap=0
int oldThr = threshold;//实例传入的容量
int newCap, newThr = 0;
if (oldCap > 0) {
//.....省略.....
}
else if (oldThr > 0)
// 初始化容量,threshold 初始值也是初始容量
newCap = oldThr;
else {
// 若没有赋值,则使用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
//小于允许的最大容量,返回 ft = (float)newCap * loadFactor; newCap = oldThr = threshold;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//重新给 threshold 赋值
threshold = newThr;
//创建容量为 newCap 的 newTab
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//.......省略.......
return newTab;
}static final int tableSizeFor(int cap)
该方法返回一个大于等于且最接近
cap
的 2 的幂次方整数。如给定 9,返回 2 的 4 次方 16,以给threshold
赋初始值。在构建 HashMap 实例时会给 threshold 赋初始值,调用
tableSizeFor
方法得到的,此值实际也是 HashMap 的初始容量。1
2
3
4
5
6
7
8
9
10
11
12/**
* 返回一个大于等于且最接近 cap 的2的幂次方整数。如给定9,返回2的4次方16。
*/
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;
}从上代码可以看出,HashMap 的容量必定是
2
的幂数(即Node<K,V>[] table
和newTab
的容量必定是 2 的幂数),就是如果构建实例时传入了的容量值不是2
的幂数,例如给定 9,则容量实际是 16,即在的创建实例传入的容量可能不是 HashMap 实际的容量,实际容量是调用tableSizeFor
方法计算得出,是最接近 cap 的 2 的幂次方整数,等于或大于指定的的容量值。方法执行逻辑分析:
第一行代码
int n = cap - 1
是为了防止cap
已经是 2 的幂时,执行完后面逻辑后返回的值是cap
的 2 倍,因为cap
已经是 2 的幂,就已经满足条件了,2倍就存在浪费了。。将
n
转为二进制执行>>>
无符号右移,高位直接补 0,再执行或|
运行,然后赋值。可将n |= n>>>1
翻译为n = n | (n>>>1)
。此算法的核心是让某些二进制位全部都变为 1。
Hash算法
HashMap 底层的数据结构是 数组+链表/红黑树,主干是数组。
get / put
方法通过对 key 进行 hash 运算,再通过算法将 hash 值转换为数组索引, 实际是建立一个 key -> index
的映射关系,这样在每次根据 Key 查找时,就可以计算出对应的数组索引,就可以直接找到对应的 key-value
对象,时间复杂度是 O(1)
。
HashMap 的 get/put
都是先对 Key
执行hash
后再做业务操作,源码如下。
1 | public V get(Object key) { |
key.hashCode()
得到散列值为 32位有符号 int
整数,取值范围从 -2,147,483,648
到 2,147,483,647
,前后加起来大概 40亿的映射空间,如果直接用来做为数组索引,不一定有这么大连续的内存,且太浪费没必要。HashMap 的初始容量才 16,Key 的 hash 值是不能直接拿来用的,需要通过一定算法映射成数组索引来找到在哈希表中的位置。
HashMap 中的 hash
方法是先调用 hashCode() 方法取得 hash 值,再将 hash 值无符号右移 16 位,正好是 32位的一半,高位全补 0,再与原 hash 值做异或^
运算(高半区与低半区做异或运算),对低位进行了**扰动
**,混合了原始哈希码的高位和低位,异或后的值的高区 16 位 与原始 hash 值相比没有变化,低区的 16 位发生了变化,增加了低位的随机性,使该 hashCode 映射成数组下标时可以更均匀。
哈希表数组索引计算:
从 HashMap 的
get / put
源码中可以看到计算数组index
方式是:index =(n - 1) & hash
n
是哈希表的容量,是 2 的 幂次方,是数组table
的长度。hash
是对 key 执行 hashCode 再将高16位 与 低16位做异或运算后的值。
写个测试例子,看看
(n - 1) & hash
这个算法计算出来的索引。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void arrayIndex() {
int n = 16;
//假如有20个元素,数组容量是16, key 分别是 0-19, 使用索引算法计算出结果
for (int i = 0; i < 20; i++) {
int key = i;
int keyHash = new Integer(key).hashCode();
int val = keyHash >>> 16;
int hash = keyHash ^ val;
int index = ((n - 1) & hash);
//int index = hash % n;
System.out.print(index + ", ");
}
System.out.println();
}
//输出结果:
// & 与运算 :0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3,
// % 取余运算:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3,从上输出结果可以看出,计算索引的**
&
与运算** 与 求余运算 得出的结果一致的,超过数组容量计算出的索引位存在冲突。计算索引算法解析:
(n - 1) & hash
:(数组长度-1)正好相当于一个 低位掩码,低位全是 1,&
与操作时的结果是将散列值的高位全部归零,只保留低位值,这个值一定是小于n
的,就满足数组索引取值范围,所以用来做数组下标。效果等同于hash % n
,但计算机的位运算 比 算术运算 高效的多。1
2
3
410100101 11000100 00100101
00000000 00000000 00001111
-----------------------------------------
00000000 00000000 00000101 // & 与运算,高位全归零,只保留低位值如果直接使用 key 的 hash 进行
&
与运算,就算 hash 分布再松散,要是只取最后几位的话,冲突就会很严重。如果散列本身做得不好,分布上成等差数列的漏洞,恰好使最后几个低位呈现规律性重复,就极其糟糕。
这时扰动函数的价值就体现出来了,将高半区与低半区进行异或运算,使高半位充分参与 Hash 运算。看下面这个图。
为什么数组长度必须是2的幂:
从上面内容可知,数组长度
n
是 2 的幂,n - 1
转二进制后,低位全是 1,而扩容后的容量是原来的 2 倍,扩容后的容量二进制表示正好是在n -1
的二进制全为1的前一位加1,即扩容后只有一位差,也就是多出了最左位的 1。这样在通过
(n - 1) & hash
的时候,只要 hash 对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致。
put方法
HashMap 通过 put 方法插入元素,Key 和 Value 可以为 null。put
方法调用了 putVal
方法来插入元素。
HashMap 的主干是一个 Node<K,V>
类型的 Entry
数组,Entry 是 HashMap 的基本组成单元,每一个 Entry 包含一个key-value键值对(其实就是一个保存了两个对象之间映射关系的一种集合)。
HashMap 的插入操作分两步:先进行查找,如果 key 已经存在,则覆盖 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
* 第一次使用时初始化, 必要会调用大小。分配时, 长度一定是 2 的幂次方
* 实际存储 key-value 数组, key和value被封装成了 Node
* JDK 1.8 之前存放链表的表头,1.8中引入红黑树,链表树化后,就是树的根
*/
transient Node<K,V>[] table;
/**
* map 中 key-value 元素个数
*/
transient int size;
/**
* HashMap 结构被修改的次数
*/
transient int modCount;
/**
* threshold = capacity * loadFactor
* 扩容前的阀值
*/
int threshold;
/**
* 扩容因子
*/
final float loadFactor;
/**
* JDK 1.8 对Hash冲突可能导致超长链表做了优化,引入了红黑树。
* 当链表中节点个数大于 TREEIFY_THRESHOLD, 就会将链表树化,以提高查询效率。
* 链表转为树的阀值。此值必须大于2,且至少等于8,
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 非树化的阀值。对于已经是树形的桶,会做一个split操作
* 若剩下的元素个数小于 UNTREEIFY_THRESHOLD, 则将其非树化,重新转回链表结构
* 此值应小于 UNTREEIFY_THRESHOLD, 且最大值为 6
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 树化的最小 table 容量,如果没达到容量但节点又太多,则使用扩容
* 当一个链表中的元素个数大于树化阀值并请求 treeifyBin 操作
* 值至少为 4 * TREEIFY_THRESHOLD 的值, 以避免 resize 和 树化阀值之间的冲突
*/
static final int MIN_TREEIFY_CAPACITY = 64;Node<K, V>源码:是 HashMap 的内部静态类
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
41static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;//链表元素
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final String toString() { return key + "=" + value; }
//重写了 hashCode() 方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//判断两个node是否相等,若key和value都相等,返回true。可以与自身比较为true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}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
77public V put(K key, V value) {
//调用 putVal, 传入了 key 的 hash 值
return putVal(hash(key), key, value, false, true);
}
/**
* Map.put 和相关方法的实现
*/
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, 调用 resize() 扩容初始化 table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//确定传入Key的hashd在数组中对应的下标 i, p 在这里被赋值
if ((p = tab[i = (n - 1) & hash]) == null)
//槽位如果为 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))))
//若该位置上的第一个元素p与传入的元素信息匹配,则将使用 p 给 e 赋值
e = p;
else if (p instanceof TreeNode)
//如果 p 是树形节点, 一棵红黑树的根节点,调用 putTreeVal 执行操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//走到这里,说明 p 是个链表头,则遍历链表, binCount 表示链表节点数
for (int binCount = 0; ; ++binCount) {
// e 指向 p 的下一个节点
if ((e = p.next) == null) {
//如果为 null,即链尾,新建节点并插入
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果节点数已达到树化阀值,则将链表树化
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果在链表中匹配到 Key,跳出循环
break;
//用于遍历桶中的链表,
p = e;
}
}
if (e != null) { // existing mapping for key
//走到这里,说明找到了与 key 相匹配的节点 e
//暂存有节点当前的值为 oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//如果 onlyIfAbsent=true,则已存在的值不被覆盖,随非旧值为 null
//onlyIfAbsent=false, 则用新值覆盖旧值
e.value = value;
//钩子方法,HashMap中是个空方法,但是在其子类LinkedHashMap中会被Override
//通知子类:节点e被访问过了
afterNodeAccess(e);
//返回已被覆盖的节点e的oldValue
return oldValue;
}
}
/*******执行到这里,说明没有匹配的 Key,是新节点插入******/
//结构修改计数 +1,创建迭代器后结构被并发修改,引发 fail-fast
++modCount;
//插入元数后, size+1, 如果已大于扩容的阀值
if (++size > threshold)
// 如果 size 大于扩容阀值,则调用 resize()执行扩容
resize();
//钩子方法,通知子类有新节点插入
afterNodeInsertion(evict);
//新节点插入,无旧值可返回,返回null
return null;
}
插入操作的大致流程:
先通过 Key 的 hash 定位到 table 数组中的一个桶位。
如果桶位没有被占用,则新建节点插入,记录结构修改数,判断是否扩容,结束。
如果桶被占用,则与第一个元素(节点)进行匹配,若成功,则无需后续的树判断和链表遍历操作,直接覆盖;否则的话则判断节点类型。
如果桶的第一个节点 p 是 TreeNode 类型,则表示桶中存在的是一棵红黑树,则调用
putTreeVal
方法来处理。否则,该桶中就是一个链表,则对有进行遍历。若遍历链表的某个节点匹配到了 e,就跳出循环执行覆盖;否则循环直到链表尾节点(必为 null),新建节点,挂在链表尾节点上,自己成为新的链表尾。
在链表插入新节点时,还会判断链表的长度是否达到树化的阀值,如果大于阀值,则调用
treeifyBin
方法来树化。每插入一个新元素,size 会加 1,最后根据 size 是否大于扩容阀值,如果大于阀值,则调用
resize
执行扩容操作。
get方法
了解了 HashMap 的 Hash 算法和 put 方法的逻辑,get 方法就更容易理解了。
1 | /** |
链表树化
如果数组桶位是个链表,在向链表插入元素后,会判断链表的长度是否大于树化阀值,如果大于,则调用 treeifyBin
方法将链表树化。树化过程是创建树和向树中插入节点。
TreeNode<K,V>:树形节点
1
2
3
4
5
6
7
8
9
10
11static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//.....省略方法.....
}treeifyBin 源码
如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化
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/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 将链表转化为红黑树
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
//判断, 给 n 赋值,tab 的容量
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { //这里给数组索引index赋值
//走进来,定位到hash对应的桶位,赋值给 e
//定义两个树形节点指针,分别指向链表头,尾节点
TreeNode<K,V> hd = null, tl = null;
do {
//将 Node 类型节点替换为 TreeNode 类型的 p
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//若为 null,则将 p 赋值给 hd
hd = p;
else {
//将tl赋值为p的前节点
p.prev = tl;
//将p赋值为tl的下一节点
tl.next = p;
}
//尾指针后移
tl = p;
//如果有子节点则继续循环
} while ((e = e.next) != null);
//将链表头节点插入table的index位置
if ((tab[index] = hd) != null)
//通过 treeify 方法将链表树化
hd.treeify(tab);
}
}treeify树化
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/**
* Forms tree of the nodes linked from this node.
* @return root of tree
* 将链表树化
*/
final void treeify(Node<K,V>[] tab) {
//声明根节点 root
TreeNode<K,V> root = null;
//声明变量 x,next,从调用节点 this 开始遍历
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//下一节点
next = (TreeNode<K,V>)x.next;
//当前x节点的左右子树置为空
x.left = x.right = null;
if (root == null) {
x.parent = null; //根节点的父节点为 null
x.red = false; //红黑树根结点为黑色
//若 root 为空,则将 x 赋值为根节点 root
root = x;
}
//否则,将当前节点插入到已有的树中
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
//第二层循环执行对一个节点的插入操作
//从根结点开始循环寻找适合 x 的位置,并完成插入
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
//若 x.hash 小于p的,则往p的左子树中继续寻找
dir = -1;
else if (ph < h)
//否则在右子树中寻找
dir = 1;
else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//若两节点hash值相等,且key不可比,则利用System.identityHashCode方法来决定一个方向
dir = tieBreakOrder(k, pk);
//将当前节点p暂存为xp
TreeNode<K,V> xp = p;
//根据上面算出的 dir 值选择将 p 向下左子树或右子树移
//若为空,说明找到合适位置执行插入,否则继续循环
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//将 parent 指针指向 xp
x.parent = xp;
if (dir <= 0) //根据dir决定x是作为xp的左孩子还是右孩子
xp.left = x;
else
xp.right = x;
//每次插入新节点后都需要做平衡操作(满足红黑树性质)
root = balanceInsertion(root, x);
break; //插入完成,跳出循环
}
}
}
}
//对红黑树的平衡调整可能会更换根节点,
//通过moveRootToFront方法确保table[index]中的节点与插入前相同
moveRootToFront(tab, root);
}
resize扩容
HashMap 在调用 put 方法添加元素后,发现元素总数(size)大于了阀值(threshold),就会执行扩容操作。
阀值(threshold) = 容量(capacity ) * 负载因子(loadFactor),默认的负载因子是 0.75f,可理解为当一个 Map 填满了 75% 的 Bucket 时,就会调用 resize
方法进行扩容。
putVal()源码:
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { |
resize()源码:
1 | /** |
非线程安全
HashMap 使用同步,是非线程安全的。如果多个线程同时访问,且至少有一个线程修改了其结构,则必须在外部进行同步。(结构修改:指添加或删除一个或多个元素的任何操作;仅更改键的值不是结构修改)。
如果无法在外部进行同步,则应使用如下方式来包装 Map,最好是在创建实例时完成此操作。
1 | Map m = Collections.synchronizedMap(new HashMap(...)) |
HashMap 的所有 集合视图 方法返回的迭代器都是快速失败(fail-fast
)的,如果在创建迭代器后的任何时间结构被修改,除了迭代器自己的 remove
方法外,该迭代器都将抛出 ConcurrentModificationException
异常。因此,面对并发修改,迭代器会快速干净地失败,防止任何风险,迭代器的快速失败行为仅应用于检测错误。
HashMap是非线程安全的,其主要体现:
- 在 JDK 1.7 中,在多线程环境下,扩容时会造成环形链或数据丢失。
- 在 JDK 1.8 中,在多线程环境下,会发生数据覆盖的情况。
具体分析可参考 HashMap 为什么线程不安全?。
与HashTable区别
HashMap | HashTable | |
---|---|---|
线程安全 | 非线程案全, 性能相对高些。 |
线程安全,方法上使用synchronized ,比较粗暴 |
NULL值 | 允许 Key / Value 为 Null, Key 为 Null 时存在 table 数组第一个节点上。 判断键是否存在使用 containsKey() 方法 |
不允许 Key 为Null |
继承关系 | 继承自 AbstractMap | 继承自 Dictionary |
初始容量与负载因子 | 初始容量:16 负载因子:0.75f |
初始容量:11 负载因子:0.75f |
扩容方式 | 原容量的2倍:newCap = oldCap << 1 | 原容量的2倍+1: newCapacity = (oldCapacity << 1) + 1 |
底层结构 | JDK 7 :数组 + 链表 JDK 8 :数组 + 链表 / 红黑树 |
数组 + 链表 |
哈希算法 | hash = (h = key.hashCode()) ^ (h >>> 16) index = (n - 1) & hash |
hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; |
与HashSet区别
HashSet 不是 Key / Value 结构,仅仅是存储不重复的元素。
HashSet 的内部实现是 HashMap,HashSet 里面的元素填充到 HashMap 的 Key,HashMap 的 Vaule 使用同一个 Object 对象填充。
因此 HashSet 也是非线程安全的,HashSet 可以理解为 HashMap 的简化版。
HashSet 构造方法
1 | public HashSet() { |
HashSet add方法
1 | private static final Object PRESENT = new Object(); |
数据结构图
JDK 1.7
HashMap 数据结构图
JDK 1.8
HashMap 数据结构图
put 方法逻辑图
相关参考
- 解析HashMap的tableSizeFor方法。
- 源码分析系列文章-HashMap
- 深入理解HashMap系列
- 美团:Java 8系列之重新认识HashMap
- 一文读懂 JDK8 HashMap
- HashMap中的hash算法总结
- HashMap中的hash算法中的几个疑问
- JDK 源码中 HashMap 的 Hash 方法原理
- HashMap死循环分析的修正版
- 重新认识JDK1.8 中不一样的HashMap:提供了 JDK1.7 VS JDK1.8 性能比较。
- 红黑树在HashMap中的应用:说明了红黑树的操作
- Java集合之 JDK7 HashMap:演示了容量为何为2的幂,重写 equals和 hashCode 方法
- HashMap分析之红黑树树化过程:描述了红黑树及树操作
- 关于 HashMap 1.8 的重大更新:对比了Jdk1.7与Jdk1.8的区别,脑图,流程图。
- HashMap 数组+链表+红黑树:比较多,但也比较杂,排版不好
- Jdk1.7 HashMap底层实现和原理:描述了链表的几种形式,补充了 1.8 的区别
- Jdk 1.8 扩容后的元素新位置为原位置+原数组长度:解释了
newTab[j + oldCap] = hiHead
- HashMap之put方法流程解读:详细描述 put 方法。
- 了解数据结构:Array、HashMap、List:描述了多数据结构的插入、查找、删除的时间复杂度比较
- 掌握 HashMap 看这一篇文章就够了:Jdk 1.7 和 1.8 较全面的比较分析
- 彻底理解HashMap的元素插入原理:图较多,比较清晰
- HashMap是如何工作的?:哈希冲突的解决方法,在维基百科中,总结出了四大类
- What is the significance of load factor in HashMap?
Java基础:JDK8 HashMap源码及数据结构分析
http://blog.gxitsky.com/2020/01/28/Java-jdk-14-hashmap-sourcecode/