沉淀、分享、成长,让自己和他人都能有所收获!😄

一、HashMap插入

HashMap插入的流程主要包括:计算下标、何时扩容、何时链表转红黑树等,具体如下:

  1. 首先对key进行hash值的扰动,获取一个新的hash值。

    1
    (key == null) ? 0 : h = key.hashCode() ^ (h >>> 16)
  2. 判断tab是否为null或者长度为0,如果是则进行扩容操作。

    1
    2
    if ((tab == table) == null || (n = tab.length == 0))
    n = (tab = resize()).length;
  3. 根据hash值计算下标,如果tab对应下标没有存放数据,则直接插入该数据。

    1
    2
    if ((p = tab[i = (n-1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  4. 如果键值对键的值以及节点 hash 等于链表中的第一个键值对节点时,则将e指向该键值对。

    1
    2
    3
    if (p.hash == hash && 
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
  5. 如果桶中引用类型是树节点,则向树插入该节点,否则向链表中插入该节点。

    1
    2
    else if (p instanceof TreeNode)
    e = ((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value);
  6. 如果链表插入节点的时候,链表长度大于等于8,则需要将链表转换为红黑树。treeifyBin是一个链表转树的方法,但不是所有链表长度大于等于8时都会转成树,还需要对当前数组桶长度是否小于64做判断,如果小于则需要扩容,大于64则进行链表转树操作。因为当数组长度小于64时,使用链表比使用红黑树查询速度更快。数组长度较小时应该尽量避开红黑树,因为红黑树需要进行左旋、右旋、变色操作来保持平衡。

    1
    2
    3
    4
    5
    if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  7. 判断需要插入的键值对是否存在HashMap中,如果存在根据onlyIfAbsent(默认false)或者值为null,则更新值。

    1
    2
    3
    4
    5
    6
    7
    8
    if (e != null) {
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null) {
    e.value = value;
    afterNodeAccess(e);
    return oldValue;
    }
    }
  8. 最后元素处理完成之后,判断容量是否超过阙值,如果超过则进行扩容操作。

    1
    2
    if (++size > threshold)
    resize();

JDK1.8 HashMap的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
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;
// 判断数组桶tab是否为null或者长度为0,如果是则进行扩容操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果桶中不包含键值对节点引用, 则将新键值对节点的引用存入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e; K k;
// 如果键值对键的值以及节点hash等于链表中的第一个键值对节点时, 则将e指向该键值对
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用类型为TreeNode, 则调用红黑树插入值
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)
treeifyBin(tab, hash);
break;
}
// 如果当前链表包含需要插入的键值对时, 终止遍历
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判断要插入的键值对是否存在HashMap中,
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
=return oldValue;
}
}
++modCount;
// 键值对数量超过阙值时, 则进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

二、HashMap扩容机制

  1. 扩容时计算出新的newCap、newThr,这两个单词是Capacity、Threshold,分别代表容量、阙。
  2. newCap用于创建新的数组桶new Node[new Cap]。
  3. 随着扩容后,原来那些因为hash碰撞,存放成链表和红黑树的元素,都需要进行拆分存放到新的位置中。

三、链表树化

HashMap这种散列表的数据结构,最大的性能在于可以O(1)时间复杂度定位到元素,但是因为哈希碰撞不得已在一个下标里存放多组数据,在jdk1.8之前的设计只是采用链表的方式进行存放,时间复杂度为O(n),链表越长性能越低。所以在jdk1.8把链表长度超过8个(包含8个)的链表转成自平衡的红黑树结构,以此让定位元素的时间复杂度为O(logn)提升查找效率。

链表树化源码:

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
final void treefyBin(Node<K, V>[] tab, int hash) {
int n, index; Node<K, V> e;
// 数组容量大于64才进行链表树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 头部、尾部
TreeNode<K, V> hd = null, tl = null;
do {

} while ((e = e.next) != null) {
// 将普通节点转换为树节点, 此时还不是红黑树
TreeNode<K, V> p = replacementTreeNode(e, null);
if (t1 == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
}
if((tab[index] == hd) != null)
// 转红黑树操作
hd.treeify(tab);
}
}

流程如下:

  1. 链表树化的条件有两个:链表长度大于等于8、桶容量大于64,否则只是扩容,不会树化。
  2. 链表树化的过程中是先由链表转成树节点,此时的树还不是平衡树。同时在树转换过程中会记录链表的顺序,tl.next = p,这主要是方便后续树转链表和拆分更方便。
  3. 链表转换成树完成之后,再进行红黑树的转换。

四、红黑树转链

因为在链表树化的时候,记录了原有链表的顺序,所以直接把TreeNode转换成Node即可,源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
final Node<K, V> untreeify(HashMap<K, V> map) {
Node<K, V> hd = null, tl = null;
// 遍历TreeNode
for (Node<K, V> q = this; q != null; q = q.next) {
// TreeNode转成Node
Node<K, V> p = map.replacementNode(q, null);
if (tl = null)
hd = p;
else
t1.next = p;
tl = p;
}
return hd;
}

Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
return new Node<K, V>(p.hash, p.key, p.value, next);
}

五、HashMap查找get方法

get方法源码如下:

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;
// 通过扰动函数计算hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K, V> getNode() {
Node<K, V>[] tab; Node<K, V> first, e; int n; K k;
// 判断桶数组不为空, 且通过hash值计算下标存在节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null){
// 判断是否为第一个节点
if (first.hash == hash && ((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);
}
}
}

流程如下:

  1. 通过扰动函数计算hash值。
  2. 通过hash值计算下标,并判断数组桶不为空且该下标存在节点。
  3. 判断存在的节点是否为第一个节点。
  4. 判断节点是红黑树节点还是链表节点,再进行节点获取。