HashMap源码解读

发表于   |   分类于   |  

关于HashMap的疑问

  • HashMap底层的数据结构，怎样解决hash碰撞。

  • HashMap何时扩容，扩容的过程是怎样的

  • 红黑树是一种怎样的数据结构

JDK8 HashMap数据结构

1
2
3
4
5
6
7
8
9

static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       volatile V val;
       volatile Node<K,V> next;
      //省略省略
}
transient volatile Node<K,V>[] table;

　　不难发现HashMap底层由数组、链表和红黑树三者组成。

Node类

　　包含一个执行自身类型的引用next，显然Node类是组成链表的节点，next引用负责链接各个节点。

table数组

　　Node类组成的数组，装载所有的键值对。table有以下几个特点:

  • 长度N一定为2的幂。即使指定初始长度，N一定是大于等于初始长度的2的幂（可以参考tableSizeFor函数）
  • table[i]包含的是hash&(N-1)的Node节点。由于N为2的幂，hash&(N-1)等价于hash%N。与运算的速度大大高于取余，这就是作者的高明之处。
  • 延迟初始化，只用第一次在Map中放入元素时，才会调用这个分配空间。

链表和红黑树

　　多个元素hash&(n-1)的值相同的情况称为hash碰撞。链表和红黑树这两种数据结构都是在发生hash碰撞时产生的结果。如果链表的长度大于8且table长度大于64，链表被转化为红黑树。如果红黑树的节点数量小于6，则转化为链表。

HashMap重要字段

  • Node[] table，文章已经提到不再赘述

  • DEFAULT_INITIAL_CAPACITY = 1 << 4。HashMap默认初始大小为16

  • DEFAULT_LOAD_FACTOR = 0.75f。默认负载因子是0.75，也就是说table数组有75%非空时进行扩容。

  • size：记录Map中键值对个数。

  • threshold：记录下一次扩容的阈值。threshold = loadFactor * table.length.

重要的函数

get操作实现函数getNode

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

final Node<K,V> getNode(int hash, Object key) {

        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

        //延迟初始化导致table可能为空

        if ((tab = table) != null && (n = tab.length) > 0 &&

            (first = tab[(n - 1) & hash]) != null) {

            //hash对应table数组位置的头元素key等于查找key，直接返回头节点

            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 && //遍历链表直到找到hash相等 key相等的元素

                         ((k = e.key) == key || (key != null && key.equals(k))))

                        return e;

                } while ((e = e.next) != null);

            }

        }

        return null;

    }

put操作实现函数putVal

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

                   boolean evict) {

        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //第一次执行put操作时初始化table

        if ((tab = table) == null || (n = tab.length) == 0) 

            n = (tab = resize()).length;

        //节点填充的位置为null，直接放入新的Node节点

        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 &&  //key已经在Map中出现，直接覆盖原数字

                ((k = p.key) == key || (key != null && key.equals(k))))

                e = p;

            else if (p instanceof TreeNode)  //p是一棵红黑树

                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {               //p是一个链表，将元素放置到链表末尾

                for (int binCount = 0; ; ++binCount) {

                    if ((e = p.next) == null) {

                        p.next = newNode(hash, key, value, null);
                        // 链表长度大于等于8，链表转化为红黑树

                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);

                        break;

                    }              

                    if (e.hash == hash &&     // 相同key在链表中存在，覆盖原来节点

                        ((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;

            }

        }

        //table数组有一个位置被占用，判断是否扩容

        ++modCount;

        if (++size > threshold)

            resize();

        afterNodeInsertion(evict);

        return null;

    }

扩容函数resize

1）获取新数组newTab的长度，为newTab申请空间。需要考虑容量最大边界，延迟初始化等问题。

2）将原数组oldTab中的节点，放入newTab中。链表和红黑树拆解问题。数组容量是2的幂，所以拆解过程很有技巧

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

final Node<K,V>[] resize() {

        Node<K,V>[] oldTab = table;

        int oldCap = (oldTab == null) ? 0 : oldTab.length;

        int oldThr = threshold;  //原数组阈值

        int newCap, newThr = 0; //分别记录新table容量 和 新的阈值

        if (oldCap > 0) {

            if (oldCap >= MAXIMUM_CAPACITY) {

                threshold = Integer.MAX_VALUE;

                return oldTab;

            }

            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                     oldCap >= DEFAULT_INITIAL_CAPACITY)

                newThr = oldThr << 1; // double threshold

        }

        else if (oldThr > 0) // Map设置初始容量,threshold为table初始容量

            newCap = oldThr;

        else {               // zero initial threshold signifies using defaults

            newCap = DEFAULT_INITIAL_CAPACITY;

            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

        }

        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) {

            for (int j = 0; j < oldCap; ++j) {   //遍历原始table

                Node<K,V> e;

                if ((e = oldTab[j]) != null) {

                    oldTab[j] = null;

                    if (e.next == null)    // 不存在hash碰撞，只有一个节点

                        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;
                            

/* table的capcity一定是2的幂。e.hash & oldCap 结果 r只可能等于0或者oldCap
 e.hash & oldCap == 0 时，e.hash & (oldCap-1) == e.hash & (newCap-1)
e.hash & oldCap == oldCap 时,e.hash & (oldCap-1)+oldCap ==e.hash&(newCap-1)*/


                            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);

                        if (loTail != null) {

                            loTail.next = null;

                            newTab[j] = loHead;

                        }

                        if (hiTail != null) {

                            hiTail.next = null;

                            newTab[j + oldCap] = hiHead;

                        }

                    }

                }

            }

        }

        return newTab;

    }