jdk1.8.0_144
HashMap 作为最常用集合之一, 继承自 AbstractMapJDK8 的 HashMap 实现与 JDK7 不同, 新增了红黑树作为底层数据结构, 结构变得复杂, 效率变得更高为满足自身需要, 也重新实现了很多 AbstractMap 中的方法本文会围绕 HashMap, 详细探讨 HashMap 的底层数据结构扩容机制并发环境下的死循环问题等
JDK8 同 JDK7 一样对 Map.Entry 进行了重新实现, 改了个名字叫 Node, 我想这是因为在红黑树中更方便理解, 方法和 JDK7 大体相同只是取消了几个方法并且此时的 Node 节点 (也就是 Entry) 结构更加完善:
- static class Node<K,V> implements Map.Entry<K,V> {
- final int hash; // 节点 hash 值
- final K key; //key 值
- V value; //value 值
- Node<K,V> next; // 指向的下一个节点
- // 省略, 由于 JDK8 的 Map 接口新增了几个 compare 比较的方法, Node 直接就继承了
- }
Node 作为 HashMap 维护 key-value 的内部数据结构比较简单, 下面是 HashMap 重新实现 Map 的方法
public int size()
HashMap 并没有继承 AbstractMap 的 size 方法, 而是重写了此方法 HashMap 在类中定义了一个 size 变量, 再此处直接返回 size 变量而不用调用 entrySet 方法返回集合再计算可以猜测这个 size 变量是当插入一个 key-value 键值对的时候自增
public boolean isEmpty()
判断 size 变量是否 0 即可
public boolean containsKey(Object key)
AbstractMap 通过遍历 Entry 节点的方式实现了这个方法, 显然 HashMap 觉得效率太低并没有复用而是重写了这个方法
JDK8 的 HashMap 底层数据结构引入了红黑树, 它的实现要比 JDK7 略微复杂, 我们先来看 JDK7 关于这个方法的实现
- //JDK7,HashMap#containsKey
- public boolean containsKey(Object key) {
- return getEntry(key) != null; // 调用 getEntry 方法
- }
getEntry 实现的思路也比较简单, 由于 JDK7 的 HashMap 是数组 + 链表的数据结构, 当 key 的 hash 值冲突的时候使用链地址法直接加到冲突地址 Entry 的 next 指针行程链表即可所以 getEntry 方法的思路也是先计算 key 的 hash 值, 计算后再找到它在散列表的下标, 找到过再遍历这个位置的链表返回结果即可
JDK8 加入了红黑树, 在链表的个数达到阈值 8 时会将链表转换为红黑树, 如果此时是红黑树, 则不能通过遍历链表的方式寻找 key 值, 所以 JDK8 对该方法进行了改进主要是需要遍历红黑树, 有关红黑树的具体算法在此不多介绍
- //JDK8,HashMap#containsKey
- public boolean containsKey(Object key) {
- return getNode(hash(key), key) != null; //JDK8 中新增了一个 getNode 方法, 且将 key 的 hash 值计算好后作为参数传递
- }
- //HashMap#getNode
- final Node<K,V> getNode(int hash, Object key) {
- // 此方法相比较于 JDK7 中的 getEntry 基本相同, 唯一不同的是发现 key 值冲突过后会通过 first instanceof TreeNode 检查此时是否是红黑树结构如果是红黑树则会调用 getTreeNode 方法在红黑树上进行查询如果不是红黑树则是链表结构, 遍历链表即可
- }
- public boolean containsValue(Object value)
遍历散列表中的元素
public V get(Object key)
在 JDK8 中 get 方法调用了 containsKey 的方法 getNode, 这点和 JDk7 的 get 方法中调用 getEntry 方法类似
将参数 key 的 hash 值和 key 作为参数, 调用 getNode 方法;
根据 (n - 1) & hash(key) 计算 key 值所在散列桶的下标;
取出散列桶中的 key 与参数 key 进行比较:
3.1 如果相等则直接返回 Node 节点;
3.2 如果不相等则判断当前节点是否有后继节点:
3.2.1 判断是否是红黑树结构, 是则调用 getTreeNode 查询键值为 key 的 Node 节点;
3.2.2 如果是链表结构, 则遍历整个链表
public V put(K key, V value)
这个方法最为关键, 插入 key-value 到 Map 中, 在这个方法中需要计算 key 的 hash 值, 然后通过 hash 值计算所在散列桶的位置, 判断散列桶的位置是否有冲突, 冲突过后需要使用链地址法解决冲突, 使之形成一个链表, 从 JDK8 开始如果链表的元素达到 8 个过后还会转换为红黑树在插入时还需要判断是否需要扩容, 扩容机制的设计, 以及在并发环境下扩容所带来的死循环问题
由于 JDK7 比较简单, 我们先来查看 JDK7 中的 put 方法源码
- JDK7HashMap#put
- //JDK7, HashMap#put
- public V put(K key, V value) {
- //1. 首先判断是否是第一次插入, 即散列表是否指向空的数组, 如果是, 则调用 inflateTable 方法对 HashMap 进行初始化
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
- //2. 判断 key 是否等于 null, 等于空则调用 putForNullKey 方法存入 key 为 null 的 key-value,HashMap 支持 key=null
- if (key == null)
- return putForNullKey(value);
- //3. 调用 hash 方法计算 key 的 hash 值, 调用 indexFor 根据 hash 值和散列表的长度计算 key 值所在散列表的下标 i
- int hash = hash(key);
- int i = indexFor(hash, table.length);
- //4. 这一步通过循环遍历的方式判断插入的 key-value 是否已经在 HashMap 中存在, 判断条件则是 key 的 hash 值相等, 且 value 要么引用相等要么 equals 相等, 如果满足则直接返回 value
- for (Entry<K,V> e = table[i]; e != null; e = e.next) {// 如果插入位置没有散列冲突, 即这个位置没有 Entry 元素, 则不进入循环有散列冲突则需要遍历链表进行判断
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value;
- e.value = value;
- e.recordAccess(this);
- return oldValue;
- }
- }
- // 插入
- modCount++;// 记录修改次数, 在并发环境下通过迭代器遍历时会抛出 ConcurrentModificationException 异常(Fail-Fast 机制), 就是通过这个变量来实现的在迭代器初始化过程会将 modCount 赋给迭代器的 ExpectedModCount, 是否会抛出 ConcurrentModificationException 异常的实现就是在迭代过程中判断 modCount 是否与 ExpectedModCount 相等
- // 插入 key-value 键值对, 传入 key 的 hash 值 keyvalue 散列表的插入位置 i
- addEntry(hash, key, value, i);
- }
- //JDK7,HashMap#addEntry, 这个方法是 put 方法的实现核心, 在其中会判断是否冲突, 是否扩容
- void addEntry(int hash, K key, V value, int bucketIndex) {
- // 第一步判断就是是否扩容, 需要扩容的条件需要满足以下两个: 1Map 中的 key-value 的个数大于等于 Map 的容量 threshold(threshold = 散列表容量(数组大小)* 负载因子)2key 值所对应的散列表位置不为 null
- if ((size>= threshold) && (null != table[bucketIndex])) {
- resize(2 * table.length); // 关键的扩容机制, 扩容后的大小是之前的两倍
- hash = (null != key) ? hash(key) : 0; // 计算 key 的 hash 值
- bucketIndex = indexFor(hash, table.length); // 重新计算 key 所在散列表的下标
- }
- // 创建 Entry 节点并插入, 每次插入都会插在链表的第一个位置
- createEntry(hash, key, value, bucketIndex);
- }
来看看 HashMap 是如何扩容的 JDK7HashMap 扩容的大小是前一次散列表大小的两倍 2 * table.length
void resize(int newCapacity)
在这个方法中最核心的是 transfer(Entry[], boolean)方法, 第一个参数表示扩容后新的散列表引用, 第二参数表示是否初始化 hash 种子
结合源码我们用图例来说明 HashMap 在 JDK7 中是如何进行扩容的
假设现在有如下 HashMap, 初始容量 initialCapacity=4, 负载因子 loadFactor=0.5 初始化时阈值 threshold=4*0.5=2 也就是说在插入第三个元素时, HashMap 中的 size=3 大于阈值 threshold=2, 此时就会进行扩容我们从来两种情况来对扩容机制进行分析, 一种是两个 key-value 未产生散列冲突, 第二种是两个 key-value 产生了散列冲突
1. 扩容时, 当前 HashMap 的 key-value 未产生散列冲突
此时当插入第三个 key-value 时, HashMap 会进行扩容, 容量大小为之前的两倍, 并且在扩容时会对之前的元素进行转移, 未产生冲突的 HashMap 转移较为简单, 直接遍历散列表对 key 重新计算出新散列表的数组下标即可
2. 扩容时, 当前 HashMap 的 key-value 产生散列冲突
在对散列冲突了的元素进行扩容转移时, 需要遍历当前位置的链表, 链表的转移若新散列表还是冲突则采用头插法的方式进行插入, 此处需要了解链表的头插法同样通过 for (Entry<K,V> e : table)遍历散列表中的元素, 判断当前元素 e 是否为 null 由例可知, 当遍历到第 2 个位置的时候元素 e 不为 null 此时创建临时变量 next=e.next
重新根据新的散列表计算 e 的新位置 i, 后面则开始通过头插法把元素插入进入新的散列表
通过头插法将 A 插入进了新散列表的 i 位置, 此时指针通过 e=next 继续移动, 待插入元素变成了 B, 如下所示
此时会对 B 元素的 key 值进行 hash 运算, 计算出它在新散列表中的位置, 无论在哪个位置, 均是头插法, 假设还是在位置 A 上产生了冲突, 头插法后则变成了如下所示
可知, 在扩容过程中, 链表的转移是关键, 链表的转移通过头插法进行插入, 所以正是因为头插法的原因, 新散列表冲突的元素位置和旧散列表冲突的元素位置相反
关于 HashMap 的扩容机制还有一个需要注意的地方, 在并发条件下, HashMap 不仅仅是会造成数据错误, 致命的是可能会造成 CPU100% 被占用, 原因就是并发条件下, 由于 HashMap 的扩容机制可能会导致死循环下面将结合图例说明, 为什么 HashMap 在并发环境下会造成死循环
假设在并发环境下, 有两个线程现在都在对同一个 HashMap 进行扩容
此时线程 T1 对扩容前的 HashMap 元素已经完成了转移, 但由于 Java 内存模型的缘故线程 T2 此时看到的还是它自己线程中 HashMap 之前的变量副本此时 T2 对数据进行转移, 如下图所示
进一步地, 在 T2 中的新散列表中 newTable[i]指向了元素 A, 此时待插入节点变成了 B, 如下图所示
原本在正常情况下, next 会指向 null, 但由于 T1 已经对 A->B 链表进行了转置 B->A, 即 next 又指回了 A, 并且 B 会插入到 T2 的 newTable[i]中
由于此时 next 不为空, 下一步又会将 next 赋值给 e, 即 e = next, 反反复复 AB 造成闭环形成死循环
所以, 千万不要使用在并发环境下使用 HashMap, 一旦出现死循环 CPU100%, 这个问题不容易复现及排查并发环境一定需要使用 ConcurrentHashMap 线程安全类
探讨了 JDK7 中的 put 方法, 接下来看看 JDK8 新增了红黑树 HashMap 是如何进行 put, 如何进行扩容, 以及如何将链表转换为红黑树的
- JDK8HashMap#put
- //JDK8, HashMap#put
- public V put(K key, V value) {
- // 在 JDK8 中, put 方法直接调用了 putVal 方法, 该方法有 5 个参数: key 哈希值, key,value,onlyIfAbsent(如果为 ture 则 Map 中已经存在该值的时候将不会把 value 值替换),evict 在 HashMap 中无意义
- return putVal(hash(key), key, value, false, true);
- }
所以关键的方法还是 putVal
- //JDK8 中 putVal 方法和 JDK7 中 put 方法中的插入步骤大致相同, 同样需要判断是否是第一次插入, 插入的位置是否产生冲突, 不同的是会判断插入的节点是链表节点还是红黑色节点
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
- //1. 是否是第一次插入, 是第一次插入则复用 resize 算法, 对散列表进行初始化
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- //2. 通过 i = (n - 1) & hash 计算 key 值所在散列表的下标, 判断 tab[i]是否已经有元素存在, 即有无冲突, 没有则直接插入即可, 注意如果插入的 key=null, 此处和 JDK7 的策略略有不同, JDK7 是遍历散列表只要为 null 就直接插入, 而 JDK8 则是始终会插入第一个位置, 即使有元素也会形成链表
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- //3. tab[i]已经有了元素即产生了冲突, 如果是 JDK7 则直接使用头插法即可, 但在 JDK8 中 HashMap 增加了红黑树数据结构, 此时有可能已经是红黑树结构, 或者处在链表转红黑树的临界点, 所以此时需要有几个判断条件
- else {
- //3.1 这是一个特殊判断, 如果 tab[i]的元素 hash 和 key 都和带插入的元素相等, 则直接覆盖 value 值即可
- if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- //3.2 待插入节点是一个红黑树节点
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- //3.3 插入后可能继续是一个链表, 也有可能转换为红黑树在元素个数超过 8 个时则会将链表转换为红黑树, 所以第一个则需要一个计数器来遍历计算此时 tab[i]上的元素个数
- else {
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null); // 遍历到当前元素的 next 指向 null, 则通过尾插法插入, 这也是和 JDK7 采用头插法略微不同的地方
- if (binCount>= TREEIFY_THRESHOLD - 1) // tab[i]的数量超过了临界值 8, 此时将会进行链表转红黑树的操作, 并跳出循环
- treeifyBin(tab, hash);
- break;
- }
- if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 这种情况同 3.1, 出现了和插入 key 相同的元素, 直接跳出循环, 覆盖 value 值即可, 无需插入操作
- break;
- p = e;
- }
- }
- if (e != null) { // 这种情况表示带插入元素的 key 在 Map 中已经存在, 此时没有插入操作, 直接覆盖 value 值即可
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount; // 修改计数, 在使用 Iterator 迭代器时会和这个变量比较, 如果不相等, 则会抛出 ConcurrentModificationException 异常
- if (++size> threshold) // 判断是否需要扩容
- resize();
- afterNodeInsertion(evict); // 并无意义
- return null;
- }
从上面的 JDK7 和 JDK8 的 put 插入方法源码分析来看, JDK8 确实复杂了不少, 在没有耐心的情况下, 这个干货确实显得比较干, 我试着用下列图解的方式回顾 JDK7 和 JDK8 的插入过程, 在对比过后接着对 JDK8 中的红黑树插入链表转红黑树以及扩容作分析
综上 JDK7 和 JDK8 的 put 插入方法大体上相同, 其核心均是计算 key 的 hash 并通过 hash 计算散列表的下标, 再判断是否产生冲突只是在实现细节上略有区别, 例如 JDK7 会对 key=null 做特殊处理, 而 JDK8 则始终会放置在第 0 个位置; 而 JDK7 在产生冲突时会使用头插法进行插入, 而 JDK8 在链表结构时会采用尾插法进行插入; 当然最大的不同还是 JDK8 对节点的判断分为了: 链表节点红黑树节点链表转换红黑树临界节点
对于红黑树的插入暂时不做分析, 接下来是对 JDK8 扩容方法的分析
- // JDK8,HashMap#resize 扩容, HashMap 扩容的大小仍然是前一次散列表大小的两倍
- final Node<K,V>[] resize() {
- //1. 由于 JDK8 初始化散列表时复用了 resize 方法, 所以前面是对 oldTab 的判断, 是否为 0(表示是初始化), 是否已经大于等于了最大容量判断结束后 newTab 会扩大为 oldTab 的两倍, 同样 newThr(阈值)也是以前的两倍源码略
- //2. 确定好 newTab 的大小后接下来就是初始化 newTab 散列表数组
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- table = newTab;
- //3. 如果是初始化(即 oldTab==null), 则直接返回新的散列表数组, 不是则进行转移
- //4. 首先还是遍历散列表
- for (int j = 0; j <oldCap; ++j) {
- //5. e = oldCap[i] != null, 则继续判断
- //5.1 当前位置 i, 是否有冲突, 没有则直接转移
- if (e.next == null)
- newTab[e.hash & (newCap - 1)] = e; // 这里并没有对要转移的元素重新计算 hash, 对于 JDK7 来会通过 hash(e.getKey()) ^ newCap 重新计算 e 在 newTab 中的位置, 此处则是 e.hash & (newCap - 1), 减少了重新计算 hash 的过程扩容后的位置要么在原来的位置上, 要么在原索引 + oldCap 位置
- //5.2 判断是否是红黑树节点
- else if (e instanceof TreeNode)
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- //5.3 判断是否是链表节点
- else {
- }
- }
- }
JDK8 的扩容机制相比较于 JDK7 除了增加对节点是否为红黑树的判断, 其余大致相同, 只是做了一些微小的优化特别在于在 JDK8 中并不会重新计算 key 的 hash 值
public V remove(Object key)
如果已经非常清楚 put 过程, 我相信对于 HashMap 中的其他方法也基本能知道套路 remove 删除也不例外, 计算 hash(key)以及所在散列表的位置 i, 判断 i 是否有元素, 元素是否是红黑树还是链表
这个方法容易陷入的陷阱是 key 值是一个自定义的 pojo 类, 且并没有重写 equals 和 hashCode 方法, 此时用 pojo 作为 key 值进行删除, 很有可能出现删不掉的情况这需要重写 equals 和 hashCode 才能使得两个 pojo 对象相等
剩下的方法思路大同小异, 基本均是计算 hash 计算散列表下标 i 遍历判断节点类型等等本文在弄清 put 和 resize 方法后, 一切方法基本上都能举一反三所以在看完本文后, 你应该试着问自己以下几个问题:
HashMap 的底层数据结构是什么?
HashMap 的 put 过程?
HashMap 的扩容机制?
并发环境下 HashMap 会带来什么致命问题?
来源: https://www.cnblogs.com/yulinfeng/p/8558983.html