Java 数据结构实现原理之 HashMap

HashMap 使用及特点

直接代码走一波:

1
2
3
4
5
6
7
8
9
10
11
12
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);
for(Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}

运行结果:

政治: 5
生物: 7
历史: 4
数学: 2
化学: 8
语文: 1
英语: 3
地理: 6

可以看到,当去顺序遍历 HashMap 的时候,HashMap 的值并不是我们顺序存储的值,那么发生了什么?

Java_Hashmap

通过 Eclipse 的断点调试可以看到 map 中存储的数据,所以第一步所研究的便是数据在 HashMap 中是如何存储。

官方文档中对 HashMap 的描述如下:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

大致意思为 HashMap 是实现 Map 接口,允许键/值为 null ,不同步并且不保证有序、不保证序不随时间变化。

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

  • Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
  • Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

Capacity 容量是 buckets 的数目,Load factor 是 buckets 填满 HashMap 的最大比例,当 buckets 填充的数目(即 hashmap 中元素的个数)大于 capacity*load factor时就需要调整 buckets 的数目为当前的2倍。

常用方法

1. put 方法的实现

大体思路如下:

  1. 对 key 的 hashCode() 做 hash ,然后再计算 index;
  2. 如果没碰撞直接放到 bucket 里;
  3. 如果碰撞了,以链表的形式存在 buckets 后;
  4. 如果碰撞导致链表过长(大于等于 TREEIFY_THRESHOLD ),就把链表转换成红黑树;
  5. 如果节点已经存在就替换 old value (保证 key 的唯一性)
  6. 如果bucket满了(超过 load factor*current capacity ),就 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
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做处理
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;
// 该链为树(红黑树)
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) // -1 for 1st
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;
}
2. get 方法的实现

在理解了put之后,get就很简单了。大致思路如下:

  1. bucket里的第一个节点,直接命中;
  2. 如果有冲突,则通过key.equals(k)去查找对应的entry
    若为树,则在树中通过key.equals(k)查找,O(logn);
    若为链表,则在链表中通过key.equals(k)查找,O(n)。

具体代码的实现如下:

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
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

原理实现

1. HashCode 的计算

HashMap 是由数组和链表组成的数据结构(Java 8 中将链表长度超过 8 的链表转化为了红黑树),存取时候会根据键值计算出所属的”类别“(即 hashCode ),再根据类别定位到数组对应的位置,而后进行操作。

理解 hashCode 是作为一个对象的标识存在, 在 Java 中 hashCode 是一个 int 类型的值,通过 hashCode 指定数组的索引可以快速定位到对象在数组所在的位置,而后遍历链表找到对应值,理想情况下时间复杂度为 O(1),并且不同对象可以拥有相同的 hashCode 。

使用 hashCode 之后可以直接定位到所需要的位置,时间的耗费主要是在遍历链表上,理想的情况下( hash 算法完美),链表只有一个节点,就是我们要的,那么时间复杂度就是 O(1) ,假设 A、B …… Z 为 hashCode 值,逻辑示例如图:

hash_code_O(1)

不理想的情况下( hash 算法糟糕),假设hash 算法计算每个数据都返回同样的 hashCode,那么此时的时间复杂度是 O(n):

hashcode_terrible

所以 HashMap 的时间复杂度一个关键点是算法的实现,因为 HashMap 是一个使用频率很高的数据结构,所以可想而知其算法设计是比较合理高效的。

在研究具体算法之前,还需要引入一个 负载因子 的概念,在源码中可以看到默认 HashMap 初始化长度为 16(1 >> 4 ),当往 HashMap 中存值的时候,假设理想状态下是一个优秀的 Hash 算法,每次往 HashMap 里存键值对的时候,都不会重复,当 HashMap 里有16个键值对的时候,要找到指定的某一个,只需要1次,而后继续存值,会产生碰撞,这时候 HashMap 会引入链表,依次类推,那么当有 128 个键值对的时候,找到一个元素,最坏的额情况需要 8 次,对此,HashMap 给出的解决方案是扩容 ,当到达一定值的时候,进行扩容,HashMap 的扩容会导致对应索引值的改变,因为每次扩容需要重新根据新表的长度计算对应的 hashCode 值。

负载因子 就是确定何时所需要扩容的 float 类型值,默认值为 0.75,扩容时机并不是数组满了之后才会扩容,而是存在一个 阀值

阀值 = 当前数组长度 * 负载因子

所以默认的 HashMap ,存到第 13 个 元素便会扩容了,负载因子的作用是决定什么时候扩容,另外,关于默认长度和负载因子均可以通过 HashMap 的构造方法自定义初始化。

至此,可以看到源码中关于 Hash 的计算方法:

对hashCode进行hash操作,然后再通过hash值进一步计算下标

hashcode

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

可见,HashCode 的计算是:高 16bit 不变,低 16bit 和高 16bit 做了一个异或。

代码注释如下:

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

hash 函数中,因为目前的 table 长度 n 为 2 的幂,而计算下标的时候,是这样实现的(使用&位操作,而非%求余):

1
(n - 1) & hash

而设计者认为这方法很容易发生碰撞。思考一波,在 n - 1 为 15( 0x1111 ) 时,其实散列真正生效的只是低 4bit 的有效位,容易发生碰撞。

因此,设计者设计了一个顾全大局的方法( 综合考虑了速度、作用、质量 ),就是把高 16bit 和 低16bit 异或了一下。设计者还解释到因为现在大多数的 hashCode 的分布已经很不错了,就算是发生了碰撞也用 O(logn) 的 tree去做了。

仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

注释中提到,如果还是产生了频繁的碰撞,使用树来处理频繁的碰撞 ( we use trees to handle large sets of collisions in bins ),在JEP-180中,描述了这个问题:

Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

在获取 HashMap 的元素时,基本分两步:

  1. 首先根据 hashCode() 做 hash,然后确定 bucket 的 index;
  2. 如果 bucket 的节点的 key 不是我们需要的,则通过 keys.equals() 在链中找。

在 Java 8 之前的实现中是用链表解决冲突的,在产生碰撞的情况下,进行 get 时,两步的时间复杂度是O(1)+O(n) 。因此,当碰撞很厉害的时候n很大,O(n) 的速度显然是影响速度的。

因此在 Java 8 中,利用红黑树替换链表,这样复杂度就变成了 O(1)+O(logn) 了,这样在n很大的时候,能够比较理想的解决这个问题,可以参考Java 8:HashMap的性能提升

2. RESIZE 的实现

执行 put 函数时候,会根据上面提到的阀值进行判断,当需要扩容时,会调用 resize 方法,简而言之就是将容量扩容为原来的两倍,并且重新计算对应下标的值。resize 注释:

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

超过限制的时候会resize,然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。

假设从 16 大小扩展到 32:

resize

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

resize2

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

resize3

设计既省去了重新计算 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
final Node<K,V>[] resize() {
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;
}
// 没超过最大值,就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
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;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
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) {
// 把每个 bucket 都移动到新的 buckets 中
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;
}
// 原索引 +oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到 bucket 里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 +oldCap 放到 bucket 里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

Java 7 与 Java 8 对比

  1. 发生hash冲突时,Java 7 会在链表头部插入,Java 8 会在链表尾部插入
  2. 扩容后转移数据,Java 7 转移前后链表顺序会倒置,Java 8 还是保持原来的顺序
  3. 关于性能对比参考 美团技术博客Java 8:HashMap的性能提升 。,引入红黑树的 Java 8大程度得优化了 HashMap 的性能

总结

  1. 特点

    基于 Map 接口实现,存储键值对,键值可以为 null ,非同步。

  1. 工作原理

    通过 hash 的方法,通过 put 和 get 存储和获取对象。

    存储时,调用 hashCode 计算 hash 从而得到 bucket 位置,进一步存储。

    HashMap 会根据当前 bucket 的占用情况自动调整容量(超过 Load Facotr 则 resize 为原来的2倍)

    读取时,将 Key 传给 get,它调用 hashCode 计算 hash 从而得到 bucket 位置,并进一步调用 equals() 方法确定键值对。

    数据碰撞,通过链表将元素组织起来,超过 8 ,Java 8 中采用红黑树来替换链表,提高速度。

  1. Hash 实现

    Java 8 中,提供过 hashCode 的高 16 位与低 16 位实现:(h = k.hashCode()) ^ (h >>> 16);

    目的为减少开销。

  2. 扩容

    如果超过了负载因子(默认 0.75 ),则会重新 resize 一个原来长度两倍的 HashMap ,并且重新调用 hash 方法。

坚持原创技术分享,您的支持将鼓励我继续创作!
0%