【Source Code】HashMap
通过 HashMap 的 field 和 method(hash()
, put()
, get()
, resize()
)入手了解了一下 Java 中 HashMap 的设计。
存储结构-字段
1 | /** |
- DEFAULT_INITIAL_CAPACITY,默认 HashMap 的大小
- MAXIMUM_CAPACITY,最大的 HashMap 的大小
- DEFAULT_LOAD_FACTOR,默认的负载因子的大小
- TREEIFY_THRESHOLD,将链表升级成红黑树的 threshold
- UNTREEIFY_THRESHOLD,当 HashMap 删除元素后,红黑树退化成链表的 threshold
- MIN_TREEIFY_CAPACITY,升级成红黑树的最小容量,表示 HashMap 达到这个容量之后,一定会升级成红黑树或者 resize。 (但是我没在别人的博客里看到过这个。。我只是按照注释理解了一下。。这个东西下面没用到)
- table[],存放数据的数组,每个元素是一个内部类 Node
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
39static 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 String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}- hash 就是 hash 值
- key 是存放的 key 值
- value 是存放的 value 值
- next 是指向下一个 Node 的引用,生成链表时用的,如果升级成红黑树,会用 TreeNode (也是一个内部类) 代替 Node
- size,HashMap 的 size
- modCount,表示 HashMap 的 structural modified 次数 (比如,添加删除元素,或者 resize 都算,但是如果仅仅是值的改变不算) 。当迭代操作或者序列化操作时,操作前后需要比较 modCount 是否相等,不相等就 Fail-Fast,抛出 ConcurrentModificationException。
- threshold,resize 的大小,等于 (capacity * load factor) ,达到 threshold 的时候就会扩容 (会 rehash,复制数据等操作,比较消耗性能)
- loadFactor,负载因子
功能实现 - method
hash()
1 | static final int hash(Object key) { //jdk1.8 & jdk1.7 |
- 取 key 的 hashCode 值
- 高位运算
- 取模运算
这个有一个点,就是 HashMap 中桶的个数 capacity 设计成 2 的幂次(一般都是设计成素数的)。之所以这样设计是为了在取模和扩容时做优化:
- 取模可以直接优化成了 and 位运算。
- 扩容时重新计算元素位置时取模更快了,而且扩容时可以直接根据 mask 位置上的新增位数是 0 还是 1 来确定当前元素是在【当前位置】,还是在【当前位置 * 2】的位置上。
但是这样设计也带来了一些问题,取模后的哈希值是有可能出现很差的哈希分布的,在 capacity 比较小的时候,hash 值高位 Bit 的信息完全丢失了。所以做了一个高位运算逻辑右移 >>>
16 位(逻辑右移,左边全部使用 0 填充),减少高位 Bit 信息的丢失。
put()
1 | final V putVal(int hash, K key, V value, boolean onlyIfAbsent, |
- 判断当前 table 是否未初始化,未初始化就初始化一波
- 根据 hash 值定位到具体的 bin,如果这个 bin 为空,直接新建一个 bin 放入这个 Node,然后返回
- 判断 key 是否和当前结点的 key 相等,相等就直接替换 Node (或者 key 都为 null 的时候,HashMap 允许 key 为 null,顺便再插一句,HashMap 中 null 无法计算其 hash 值,默认都是放到下标为 0 的 上)
- 如果当前结点是 TreeNode 红黑树结点,就按红黑树的方法插入 (具体就不展开了)
- 如果是链表,就遍历链表,找到相同的 key 的 Node 就可以直接替换 Node,如果没找到就 newNode() (这个方法会在对应的 bin 中插入 Node)
- 统一替换 Node (即 e 不为空)
- modCount 自增
- 判断是否需要 resize
get()
1 | /** |
- 判断 table 是否未初始化,未初始化或者定位到的 bin 为空的话,直接返回 null
- 判断第一个 Node/TreeNode 的值是否为查询的 key,是的话直接返回 (always check first node) ,若不匹配就下一步
- 判断为 TreeNode,查找红黑树
- 判断链表,遍历链表查找
resize()
扩容 (resize) 就是重新计算容量,向 HashMap 对象里不停的添加元素,而 HashMap 对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然 Java 里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。所以扩容就涉及到哈希值的重新计算,复制元素等操作,是很消耗性能的,如果能在开始就能确定好元素的个数,建议在一开始就设置好。
当插完元素后,size > threshold = capacity * Load factor
,扩容就开始了。
1 | void resize(int newCapacity) { //传入新的容量 |
transfer() 方法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。
1 | void transfer(Entry[] newTable) { |
可以看出来复制的时候,链表是用头插法的方式复制的,所以原来的链表会被 revert 一下。在多线程场景,在两个线程 resize 的时候,可能会出现环形链表。
扩展问题
1. Hash 时取模一定要模质数吗?
好的 hash 算法期望是 hash 值在取模后能尽可能均匀地分布。不模 prime number 的话,很容易会有分布不均匀的情况产生。
假设需要放入长为 m 的 hash 表的数是 n,取模函数是: $f(n) = n \% m$ , $f(n)$ 为需要放置在 hash 表中的位置的下标。
取 m 为质数的目的是:让 m 和 n 的最大公约数为 1,也就是: $gcd(m, n)=1$ 。因为在 m 为质数时,除非 n 恰好是 m 的倍数,否则他们的最大公约数都为 1。
$$ f(n) = n \% m $$
$$ \Rightarrow a \times m + f(n) = n(a = 0, 1, 2,3…) $$
$$ \Rightarrow f(n) = n - a \times m $$
$$ \Rightarrow f(n) = gcd(m, n) *( \frac{n}{gcd(m,n)} - \frac{a \times m}{gcd(m,n)}) $$
也就是我们算出来的 hash 值只可能是为 $gcd(m, n)$ 的倍数的那些值,倘若数据特别一点,全都是 gcd 的倍数,这样会让分布很不均匀。
2. 为什么 java 在计算 hashcode 时使用 31 作为乘数?
确实很奇怪。。感觉是个 magic number。把这个搞成了一个类似 31 进制的数字。看了很多说法,stackoverflow 上说:
The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.
是因为 31 是个奇素数,并且可以直接优化成位运算提高性能。偶数的话,相当于 shift 运算,会丢失信息,但是奇数因为在 shift 后在加上原数,所以比偶数好。之所以用素数是因为 traditional。。(我看到有的会用 33 来做,据说和 31 差不多)。
有个答案提到是根据实验得出发现 31 的,根据字典跑数据跑出的结果。(但是我看那个数据也是英文字典,ascii 字符,要是非 ascii 字符的实验结果呢?)
- Why does Java’s hashCode() in String use 31 as a multiplier? - Stack Overflow
- 为什么Java String哈希乘数为31?