HashMap的put和get数据流程揭秘

121 阅读 0 评论 80 点赞

我是靠谱客的博主潇洒鼠标，这篇文章主要介绍HashMap的put和get数据流程揭秘，现在分享给大家，希望可以做个参考。

本文是针对JDK1.8中的HashMap，之前以为已经懂的不错了，结果发现很多关键点没明白

1. 先说HashMap的数据结构

核心数据结构就三个：数组，链表，Tree

数组Node<K,V> table
数据就是个简单的Node数组，存放的是当前索引应第一个Node<K,V>对节点，或者是空（说明没有存放数据）
链表
如果挂在同一个索引下的数据Node个数小于变Tree阈值（默认是8个），那么将以数组中的元素为头节点，依次挂成一个链表
Tree
如果这个个数超过了变Tree阈值，将把key的hash()结果变成value，建立红黑树

2. 关键点

K V对进来时怎么找到放到table中的位置？
K V对进来时，放到数组中的位置是根据K的hashcode和当前数组的容量计算出来的一个索引值，这种计算方式是HashMap放置数据的核心。

计算在数组中的位置主要方式是：
首先，计算出K的hashcode，如果是String的话，那就是直接拿的Object的Native方法；
然后，取这个hashcode的高16位和低16位做作疑惑，得到一个hash值，为啥要这么做呢？源码中解释是有助于减少冲突；

复制代码

1
2
3
4
5
6
	就是这样计算的hash值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

最后，把hash与容量建议相与，即 index = (n - 1) & hash

这个index 就是新进来的K V对应该放的位置。

复制代码

1
2
3
4
5
6
7
插播：
对象的hash算法和equal是存在一定关系的，不是随便写个hash算法和equal方法就可以了
对于同一个对象：
1. 相同对象，多次hashcode得到的int型数字应该是一样的；
2. 如果两个对象equal，那这两个对象的hashcode必须一样；
3. 两个对象不equal，不一定hashcode不一样

所以HashMap中如果Key是自定义对象的话，一定要重新hashcode方法和equal方法，不然本来相同的会拿到不同的hashcode，用equal时也会判断不相等。

3. get取数据

核心的核心是根据Key值找到数组中对应的index，当时找index的方法就是2中所说的

了解到数据结构和运行原理后，相信基本能猜到HashMap里面是怎么个逻辑了

找到数组中的index，其实就是如果这个key有数据，那它会在数组中哪个开头的链表或者树上。
如果这个index上的头为空，那就是没有；如果只有一个头，但和它和key不相等，那也没有；如果不止一个头，说明是链表或者树，根据first instanceof TreeNode来判断是不是树；
剩下的就是如果是链表就链表找，如果是树就树找，判断找到的条件是，地址一样或者equal

源码中关键方法是:

复制代码

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
get(Object key);
get(int hash, Object key);
// 这个方法就是个入口，顶多是计算了从哪找
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) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

4. put数据

put数据就比get要复杂些，但也没什么太神奇的，相信如果自己去实现，逻辑也是基本类似的。

首先，肯定是找Key放的位置，就是计算index，及数组中第一个元素；
然后，如果这个位置为空，那new 一个就可以了；如果这个位置的头结点是TreeNode呢，那它肯定已经变树了，那按树的方式放数据；如果不是呢，那就按链表的方式，放到链表最后面，为啥不放到头节点后面呢？因为放完之后还要看要不要把链表变树，肯定要遍历一遍，所以应该这样就直接放到尾节点了。如果达到了变树的阈值，肯定就要变树了。
最后，上面其实做的是放位置，放完位置还有检查下是不是该扩容了，如果要扩容就麻烦点了，需要resize。

扩容的几个关键点在于：

数组table扩成两倍大小；
扩容之后node的位置，要么是在原有的index上，要么在原有数组大小+index的位置，就这两种可能。
扩容的过程中首先造一个两倍的数组，然后遍历老的数组，对于每一个头节点的要么是单个数据，要是是链表，要么是树。单个数据的简单，链表和树的就会把原有的数据拆分两部分，一部分放到index位置，一部分放到数组大小+index位置

复制代码

// 这个是常看到的，对我的，在这里计算了hash
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)
// 这是table未初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// index上啥也没有，直接加
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;
if (++size > threshold)
resize();
// 搞完发现该扩容了
afterNodeInsertion(evict);
return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

// 这个是常看到的，对我的，在这里计算了hash
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)
// 这是table未初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// index上啥也没有，直接加
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;
if (++size > threshold)
resize();
// 搞完发现该扩容了
afterNodeInsertion(evict);
return null;
}