Java集合源码之HashMap
简介
HashMap是一个哈希表,线程不安全,key
唯一,value
可重复,允许key
和value
为null。遍历时是无序的。
底层结构是基于链表散列,也就是数组+链表。数组也被称为哈希桶,桶里面就装着链表,链表中的每个节点,就是哈希表中的每个元素。
在JDK8中,当链表长度达到8的时候,就会转为红黑树。
它实现了Map<K, V>, Cloneable, Serializable
接口。
接下来我们就来看下源码:
属性
1 | // 序列化ID,用于序列化和反序列化 |
这些可能现在看起来还很迷,可能都不知道有些变量到底是拿来干嘛的。不急,我们继续往后面看。
构造方法
1 | // 构造一个指定初始容量和构造因子的HashMap |
分析3.1 HashMap # tableSizeFor(int cap)
1 | /** |
这个方法有点纠结,你光看代码确实看不出来个啥,但是如果你在纸上顺便找几个例子写写就懂了。
他的用途,总结起来就是:找到大于或等于cap的最小2的幂。
这里借用一下一位大佬的图:
这个图就是第一个例子。cap=536870913,经过运算之后,n+1=1073741824。
分析3.2 HashMap # putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
1 | final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { |
分析3.3 HashMap # 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
113final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 旧数组也就是旧哈希桶的容量,如果oldTab为空就为0,否则为oldTab长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的阈值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果旧哈希桶容量大于0
if (oldCap > 0) {
// 如果旧哈希桶容量大于限定的最大值
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值就设置为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则新的容量是旧的容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
// 旧的容量为默认初始化容量也就是16
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;
// 新的阈值默认为默认负载因子 * 默认初始容量 = 16 * 0.7 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的阈值是0,对应的是 当前表是空的,但是有阈值的情况
if (newThr == 0) {
// 根据新表容量 和 加载因子 求出新的阈值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新阈值
threshold = newThr;
// 创建新的哈希桶
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) {
// 把旧哈希桶中的该位置为空,方便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
// 由于现在容量加倍了,按照哈希表的算法,之前在这个哈希桶里面的现在不一定属于该哈希桶了
// 比如,之前哈希长度是4,有一个元素为5
// 未扩容前,他应该在5%4=1这个桶里面
// 但是现在扩容了,哈希长度变成了8,那么他现在就应该在5%8=5这个桶里面了
// 而且新桶的位置就是老位置1加上oldCap4,也就是j + oldCap = 1 + 4 = 5
// 代表扩容后还应该在老桶里面的元素
Node<K,V> loHead = null, loTail = null;
// 代表扩容后应该在新桶里面的元素
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
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);
// 遍历两个链表,把lo放到原来的位置上,并把hi放入新位置也就是j+oldCap
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结来说就是:
- 扩容
- 如果之前的哈希表有值,而且元素的个数大于限定的哈希表最大容量的话,那就把新的哈希表的阈值设置为Integer.MAX_VALUE也就是int的最大值,并直接返回旧和哈希表
- 如果之前的哈希表有值,而且元素个数没有大于哈希表最大容量,而且个数的两倍还小于限定的哈希表最大容量、元素个数大于默认的初始容量也就是16的话,就设置新的阈值为旧的阈值的2倍
- 如果之前的哈希表的空的,但是阈值是存在值的,也就相当于你初始化时指定了容量和阈值然后构造的哈希表,此时就直接让新的容量指定为旧的阈值
- 如果之前哈希表是空的,阈值也不大于0,也就相当于采用了无参构造,这时就直接让新容量为默认的初始容量也就是16,让新的阈值为默认负载因子默认初始容量 = 16 0.7 = 12
- 如果新的阈值是0的话,也就是在之前的4个判断中没有对新的阈值进行更改的情况,也就是之前的哈希表是空的,然后指定了阈值的情况,这是就根据新表的容量和负载因子求出新的阈值
- 复制到新表
- 如果以前的哈希表中有元素,就直接遍历原表,然后判断当前哈希桶里面有没有元素
- 如果有而且他的下一个为空,就代表这个链表只有一个节点,那就直接求出他的哈希值,然后给对应的哈希桶
- 如果他下一个不为空而且他是红黑树的实例,那就调用split方法
- 如果他下一个不为空,也不是红黑树的实例,那就开始遍历链表,判断当前及节点新的哈希值,如果还是当前值,那就放到lo链表上去,如果不是当前值,那就放到hi链表
- 然后遍历完成后,直接把lo链表放到当前哈希桶,把hi放到当前哈希值+旧的哈希数组长度也就是新的哈希值对应的哈希桶上去
分析3.4 HashMap # putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
常用API
增、改
HashMap # put(K key, V value)
功能:
- 如果原来的表里面没有key对应的节点,就把key和value插入
- 如果有对应的节点,就把将key对应节点的value更改为传入的value
1 | public V put(K key, V value) { |
HashMap # putAll(Map<? extends K, ? extends V> m)
功能:
- 直接把Map里面的内容传入HashMap
1 | public void putAll(Map<? extends K, ? extends V> m) { |
HashMap # putIfAbsent(K key, V value)
功能:
- 根据key找到对应节点
- 如果该节点已经有value,就返回此value
- 否则就将此value插入,并返回null
1 |
|
HashMap # replace(K key, V oldValue, V newValue)
功能:
- 根据key和value找到对应节点,然后把旧值用newValue替换
1 |
|
HashMap # replace(K key, V value)
功能:
- 根据key找到对应的节点,然后直接把value替换过去
1 |
|
删
remove(Object key)
功能:
- 根据key找到节点并删除
1 | public V remove(Object key) { |
remove(Object key, Object value)
功能:
- 根据key和value找到对应节点,然后删除
1 | public boolean remove(Object key, Object value) { |
分析4.2.1 HashMap # removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)
1 | /** |
查
HashMap # get(Object key)
功能:
- 根据key找到对应节点,并返回节点的value。
1 | public V get(Object key) { |
HashMap # containsValue(Object value)
功能:
- 根据value找到第一个找到的节点;
- 如果找到了就返回true;
- 没有返回false。
1 | public boolean containsValue(Object value) { |
HashMap # containsKey(Object key)
功能:
- 根据key找到对应节点;
- 如果有返回true;
- 否则返回false。
1 | public boolean containsKey(Object key) { |
HashMap # getOrDefault(Object key, V defaultValue)
功能:
- 根据key找到对应节点;
- 如果有返回找到节点的value;
- 否则返回传入的defaultValue。
1 | public V getOrDefault(Object key, V defaultValue) { |
分析4.3.1 HashMap # getNode(int hash, Object key)
1 | final Node<K,V> getNode(int hash, Object key) { |
判空 isEmpty()
这个方法没啥好说的
1 | public boolean isEmpty() { |
遍历
先将一下用法吧。因为HashMap的遍历有点特别。
他的遍历并不是直接使用迭代器或者他自己有个啥foreach方法能遍历(虽说他有foreach方法,但是他那个方法不是用来遍历,而是遍历进行操作的)。
他的遍历方式很奇特:1
2
3for(Object key : map.keySet()) {
// do something
}
或1
2
3for(HashMap.Entry entry : map.entrySet()) {
// do something
}
从上面代码片段中可以看出,大家一般都是对 HashMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历 keySet 方法产生的集合,在编译时会转换成用迭代器遍历,等价于:1
2
3
4
5
6Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
大家在遍历 HashMap 的过程中会发现,多次对 HashMap 进行遍历时,遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的。产生上述行为的原因是怎样的呢?
现在咱们就先来看看代码吧。
首先看下keySet方法:
HashMap # keySet()
1 | public Set<K> keySet() { |
HashMap # KeySet
1 | final class KeySet extends AbstractSet<K> { |
HashMap # KeyIterator
1 | final class KeyIterator extends HashIterator |
HashMap # HashIterator
1 | abstract class HashIterator { |
如上面的源码,遍历所有的键时,首先要获取键集合KeySet对象,然后再通过 KeySet 的迭代器KeyIterator进行遍历。KeyIterator 类继承自HashIterator类,核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂,在初始化时,HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后,再继续寻找下一个包含链表节点引用的桶,找到继续遍历。找不到,则结束遍历。
拓展
为什么哈希桶的长度一定是2的次方幂
这是因为在哈希表中,为了计算方便,他全部都用hash&(n-1)
代替了hash%n
,但是这样替换的前提就是n必须是2的次方幂。
hash()方法核心
1 | static final int hash(Object key) { |
代码的流程就是执行key的hashCode方法得到他的hashCode,然后再让他的hashCode与hashCode右移16位之后的值相与。
那为啥要这样呢?
理论上散列值是一个int型,如果直接拿散列值作为下标访问HashMap主数组的话,考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。
但问题是一个40亿长度的数组,内存是放不下的。你想,HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标。
这样的话,就算我的散列值分布的再松散,要是只取最后几位的话,碰撞也会很严重,这时,就可以让hashCode自己的高位和低位相与,这样加大了数据的随机性,很大程度降低了碰撞的几率。
变量table为什么被transient修饰
HashMap明明实现了serializable接口,而且还定义里serialVersionUID,那为什么table还需要用transient修饰而不去直接序列化呢?
其实HashMap并没有使用默认的序列化机制,而是通过实现readObject/writeObject两个方法自定义了序列化的内容。如果直接对table进行序列化的话存在着两个问题:
- table大多数情况下都是无法被存满的,序列化未使用的部分,浪费空间;
- 同一个键值对在不同JVM下,所处的桶位置可能是不同的,在不同的JVM下反序列化table可能会发生错误。
第一个好理解,那我们说一下第二个:大家都知道HashMap很多地方都是根据hash值来进行存入或者取出数据的,但是hash调用的是Object的hashCode方法。但是hashCode方法是native方法,这个是取决于JVM的,不同的JVM可能计算hashCode的方法不同。所以如果在不同的平台下,序列化和反序列化HashMap之后。可能序列化时的HashMap是对着的,直接反序列化后,可能序列化中的元素a应该放在哈希桶1中,这样,反序列化也放在桶1中,但是由于反序列化的平台不同,导致hashcode算法不同,导致在反序列时元素a应该在桶2中,这样就导致HashMap结构出问题。