HashMap -- 调研

前言

在Java中，保存数据有两种比较简单的数据结构:数组和链表。

数组的特点是:寻址容易，插入和删除 困难;
链表的特点是:寻址困难，但插入和删除容易;

所以我们将数组和链表结合在一起，发挥两者各 自的优势，使用一种叫做拉链法的方式可以解决哈希冲突 。散列表

---

JDK1.8之前

JDK1.8之前采用的是拉链法。

拉链法:

   将链表和数组相结合。也就是说创建一个链表数组，
1

数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认为8)时，将
链表转化为红黑树，以减少搜索时间。

---

JDK1.7 VS JDK1.8 比较

优化了一下问题:

1. resize 扩容优化
2. 引入了红黑树，目的是避免单条链表过长而影响查询效率
3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

HashMap的put方法的具体流程?

public class HashMapDemo<K, V> extends HashMap<K, V> {

    // 默认初始容量 - 必须是 2 的幂。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 如果任一带有参数的构造函数隐式指定更高的值，则使用最大容量。必须是 2 的幂 <= 1<<30。
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 初始因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 使用树而不是箱列表的箱计数阈值。当将元素添加到至少具有这么多节点的 bin 时，bin 会转换为树。该值必须大于2，并且至少应为8，以便与树木移除中有关收缩后转换回普通箱的假设相吻合。
    static final int TREEIFY_THRESHOLD = 8;


    // 在调整大小操作期间对（分割）bin 进行树形化的 bin 计数阈值。应小于 TREEIFY_THRESHOLD，且最多 6 个网格，以便在移除时进行收缩检测。
    static final int UNTREEIFY_THRESHOLD = 6;


    // bin 可以树化的最小表容量。  初始数量（否则，如果 bin 中的节点太多，则表的大小将被调整。）应至少为 4的倍数以避免调整大小和树化阈值之间的冲突。
    static final int MIN_TREEIFY_CAPACITY = 64;


    transient HashMapDemo.Node<K, V>[] table;
    transient Set<Entry<K, V>> entrySet;
    transient int size;
    transient int modCount;
    int threshold;


    // 创建一个节点Node类  作为链表使用
    static class Node<K, V> implements Map.Entry<K, V> {
        // hash值
        final int hash;
        // key
        final K key;
        // 对应的值
        V value;
        // 子节点
        HashMapDemo.Node<K, V> next;

        Node(int hash, K key, V value, HashMapDemo.Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        // get set
        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final String toString() {
            return key + "=" + value;
        }

        // 计算规则，  节点上的key 进行hashCode 计算，异或 hashCode 值
        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 方法， 通过hashCode 得到一个长度 位运算 h>>> 高低16bit
    static final int hash(Object key) {
        int h;

        // key.hashCode()) ^ (h >>> 16)   hashcode  和 自己hashcode 位运算异或
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }


    // put方法
    @Override
    public V put(K key, V value) {
        return super.put(key, value);
    }


    V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

        HashMapDemo.Node<K, V>[] tab;


        HashMapDemo.Node<K, V> p;
        int n;
        int i;

        // 初始化表大小或将表大小加倍。如果为空，则根据阈值字段中保存的初始容量目标进行分配
        if ((tab = table) == null || (n = tab.length) == 0) {
            // 步骤1:tab为空则创建   table未初始化或者长度为0，进行扩容
            n = (tab = resize()).length;
        }


        // 计算下标是否为空  通过hash算法  得到 p (n - 1) & hash 确定元素存放在哪个桶中
        if ((p = tab[i = (n - 1) & hash]) == null) {
            // 为空找不到，放到桶里面
            tab[i] = newNode(hash, key, value, null);
        }


        // 桶里面存在类
        else {
            HashMapDemo.Node<K, V> e;
            K k;

            // 步骤3:节点key存在，直接覆盖value比较桶中第一个元素(数组中的结点)的hash值相等，key相等
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                // 直接覆盖值
                e = p;
            }


            // 步骤4:判断该链为红黑树  hash值不相等，即key不相等;为红黑树结点 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node   e可能为空
            else if (p instanceof TreeNode) {
                // 放入树中
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            }

            // 步骤5 不是树就是链表
            else {

                // 循环
                for (int binCount = 0; ; ++binCount) {
                    // 为空最后一个节点
                    if ((e = p.next) == null) {
                        // 在链表最末插入Node结点
                        p.next = newNode(hash, key, value, null);

                        判断链表的长度是否达到转化红黑树的临界值，临界值为8
                        // TREEIFY_THRESHOLD 属性 8 前面定义类
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            // 链表结构转树形结构
                            treeifyBin(tab, hash);
                        break;
                    }


                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        // 相等，跳出循环
                        break;
                    }

                    // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                    p = e;
                }
            }


            // 判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的val ue这个值
            if (e != null) {
                // 记录e的value
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null
                if (!onlyIfAbsent || oldValue == null) {
                    // 用新值替换旧值
                    e.value = value;
                }
                // 访问后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }

        // 结构性修改
        ++modCount;
        // 步骤6:超过最大容量就扩容 实际大小大于阈值则扩容
        if (++size > threshold) {
            // 插入后回调
            resize();
        }

        // node 节点插入
        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
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

    static final int MIN_TREEIFY_CAPACITY = 64;

   final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        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 {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容;

2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3;

3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals;

4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值 对，否则转向5;

5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操 作，否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

6. 插入成功后，判断实际存在的键值对数量size是否超多了 大容量threshold，如果超过，进行扩容。

---

HashMap的扩容resize操作怎么实现的?

看一下resize 源码

    // 如果任一带有参数的构造函数隐式指定更高的值，则使用最大容量。必须是 2 的幂 <= 1<<30。
    static final int MAXIMUM_CAPACITY = 1 << 30;
   
    @Native public static final int   MAX_VALUE = 0x7fffffff;

    // 默认初始容量 - 必须是 2 的幂。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


    final HashMap.Node<K, V>[] resize() {
        // oldTab指向hash桶数组
        HashMap.Node<K, V>[] oldTab = table;

        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;

        // 如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap > 0) {

            // 如果大于最大容量了，就赋值为整数最大的阀 值
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }

            // 如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                // double threshold 双倍扩容阀值threshold
                newThr = oldThr << 1;
        }

        // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初 始化成最小2的n次幂
        else if (oldThr > 0) {
            // 直接将该值赋给新的容量
            newCap = oldThr;
        }

        // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }


        // 新的threshold = 新的cap * 0.75
        if (newThr == 0) {
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
        }


        // 计算出新的数组长度后赋给当前成员变量table
        threshold = newThr;

        @SuppressWarnings({"rawtypes", "unchecked"})
        // 新建hash桶数组
        HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];

        // 将新数组的值复制给旧的hash桶数组
        table = newTab;


        // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素 重排逻辑，使其均匀的分散
        if (oldTab != null) {

            // 遍历新数组的所有桶下标
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K, V> e;
                // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;

                    // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树
                    if (e.next == null) {
                        // 用同样的hash映射算法把该元素加入新的数组
                        newTab[e.hash & (newCap - 1)] = e;
                    }

                    // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
                    else if (e instanceof TreeNode) {
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    }

                    // e是链表的头并且e.next!=null，那么处理链表中元素重排
                    else {
                        // loHead,loTail 代表扩容后不用变换下标
                        HashMap.Node<K, V> loHead = null, loTail = null;
                        // hiHead,hiTail 代表扩容后变换下标
                        HashMap.Node<K, V> hiHead = null, hiTail = null;
                        HashMap.Node<K, V> next;

                        // 遍历链表
                        do {
                            next = e.next;

                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null) {
                                    // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead
                                    // 代表下标保持不变的链表的头元素
                                    loHead = e;
                                } else {
                                    // loTail.next指向当前e
                                    loTail.next = e;
                                }


                                // loTail指向当前的元素e
                                // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。
                                loTail = e;
                            } else {
                                if (hiTail == null) {
                                    // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                    hiHead = e;
                                } else {
                                    hiTail.next = e;
                                }

                                hiTail = e;
                            }

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

                        // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
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

可以得到的结论：每次扩展都是2倍，是否扩容的前提是容量是否大于当前的0.75，如果小于维持现状，在进行putval的时候也调用了一次resize 就是分配容量16

HashMap的扩容操作大致流程如下：

当HashMap中的元素个数（size）超过负载因子（默认为0.75）和当前容量（capacity）的乘积时，会发生扩容操作。例如，当前容量为n，元素个数超过0.75 * n时，就会触发扩容。

扩容时，会创建一个新的容量为原容量的两倍的数组，然后将原数组中的元素重新分配到新数组中。新数组的容量为原容量的两倍是因为这样可以保持较高的散列性能，减少碰撞。

扩容期间，对原数组中的每个非空元素进行重新哈希（rehashing），即根据新数组的容量重新计算它们在新数组中的位置。重新哈希的过程是通过调用元素的hashCode方法和位运算来完成的。

扩容完成后，新数组将取代原数组成为HashMap的存储结构，原数组将被丢弃，成为垃圾数据等待回收。

总结起来，HashMap的扩容操作可以看作是将原数组中的元素重新哈希到一个新的、容量为原容量两倍的数组中。这个过程会提高HashMap的性能，保持散列性能，并且适应元素数量的增长

目前代码是JDK1.8源码，可以看到扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。

在putVal()中，我们看到在 这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或 者当该数组的实际大小大于其临界值值(第一次为12) 16的0.75,

这个时候在扩容的同时也会伴随的桶上面的元素进 行重新分发，这也是JDK1.8版本的一个优化的地方，

其实在1.7中，扩容之后需要重新去计算其Hash值，根 据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是 否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小原偏移量两倍这个位置上

---

源码得到结论 小记

概念： 什么是散列

Hash，一般翻译为“散列”，也有直接音译为哈希的，这就是把任意长度的输入通过散列算法，变换成 固定长度的输出，该输出就是散列值(哈希值);这种转换是一种压缩映射，也就是，散列值的空间通 常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入 值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

概念： 什么是哈希冲突

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞(哈希碰撞)。

hashMap Hash 为什么是16bit

static final int hash(Object key) {
 inth;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位 进行异或运算(高低位异或)
}
1
2
3
4

hashMap 如何处理哈希冲突

1. 使用链地址法(使用散列表)来链接拥有相同hash值的数据;
2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率，使得数据分布更平均;
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快;

为什么HashMap中String、Integer这样的包装类适合作为K?

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少
Hash碰撞的几率都是final类型，即不可变性，保证key的不可更改性，不会存在获取 hash值不同的情况内部已重写了equals()、hashCode()等方法

HashMap 的长度为什么是2的幂次方。

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢?我们首先可能会想到采用%取余的操作来实现。但是，重点来了:
取余(%)操 作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。