乐趣区

关于java:刷完HashMap源码我们一起进大厂

不可不知的哈希映射

引言
hashmap 这个货色呢,太陈词滥调了
开发中罕用、面试中常问
总之,很重要。。。。。接下来呢
咱们就一起来看下,外面到底有哪些解不开的货色

2.1 HashMap 数据结构

指标:

HashMap 概念、数据结构回顾(JDK8 和 JDK7)& 为什么 1.8 应用红黑树?

概念:

HashMap 是一个利用 散列表(哈希表)原理来存储元素的汇合,是依据 Key value 而间接进行拜访的数据结构

在 JDK1.7 中,HashMap 是由 数组 + 链表形成的。

在 JDK1.8 中,HashMap 是由 数组 + 链表 + 红黑树形成

回顾: 数组、链表(劣势和劣势)

数组: 劣势:数组是间断的内存,查问快(o1)劣势:插入删除 O(N)
链表: 劣势:不是间断的内存,轻易插入(前、两头、尾部)插入 O(1) 劣势:查问慢 O(N)

思考?

为什么是 JDK1.8 是数组 + 链表 + 红黑树???

HashMap 变动历程

1.7 的数据结构:链表变长,效率低 了!!!

1.8 的数据结构:

数组 + 链表 + 红黑树

penwrite.cn/29993_960E722C5C864534BC24621ECB4A2BB2)

链表 – 树(链长度 >8、数组长度大于 64)

备注:当初重点讲 map,不讲树的操作。树在算法课里有具体学习

总结:

JDK1.8 应用红黑树,其实就是为了进步查问效率

因为,1.7 的时候应用的数组 + 链表,如果链表太长,查问的工夫复杂度间接回升到了 O(N)

2.2 HashMap 继承体系

指标:梳理 map 的继承关系

<img src=”assets/image-20201205220552037-1609839160181.png” alt=”image-20201205220552037″ style=”zoom: 67%;” />

总结

HashMap 曾经继承了 AbstractMap 而 AbstractMap 类实现了 Map 接口

那为什么 HashMap 还要在实现 Map 接口呢?

据 java 汇合框架的创始人 Josh Bloch 形容,这样的写法是一个失误。

在 java 汇合框架中,相似这样的写法很多,最开始写 java 汇合框架的时候,他认为这样写,在某些中央可能是有价值的,直到他意识到错了。

显然的,JDK 的维护者,起初不认为这个小小的失误值得去批改,所以就这样存在下来

  • Cloneable 空接口,示意能够克隆
  • Serializable 序列化
  • AbstractMap 提供 Map 实现接口

2.3 HashMap 源码深度分析

1)指标:

通过浏览 HashMap(since1.2)源码,咱们能够晓得以下几个问题在源码是如何解决的

(1)HashMap 的底层数据结构是什么?

(2)HashMap 中增删改查操作的底部实现原理是什么?

(3)HashMap 是如何实现扩容的?

(4)HashMap 是如何解决 hash 抵触的?

(5)HashMap 为什么是非线程平安的?

2)测试代码如下

package com.mmap;

import org.openjdk.jol.info.ClassLayout;

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

public class MMapTest {public static void main(String[] args) {HashMap<Integer, String> m = new HashMap<Integer, String>();// 尾插
        // 断点跟踪 put
        m.put(1, "001");
        m.put(1, "002");
        m.put(17, "003");// 应用 17 可 hash 抵触(存储地位雷同)System.out.println(ClassLayout.parseInstance(m).toPrintable());
        // 断点跟踪 get
        System.out.println(m.get(1));// 返回 002(数组查找)System.out.println(m.get(17));// 返回 003(链表查找)// 断点跟踪 remove
        m.remove(1);// 移除
        System.out.println(m);
        m.remove(1, "002");// 和下面的 remove 走的同一个代码
    }
}

3)对于 hashMap 根本构造的验证

先来个小验证,简直地球人都晓得 map 是 数组 + 链表 构造,那咱们先来验证一下

再来看 debug 后果:

验证了根本构造,那为啥 1 和 17 就在一块了?到底谁和谁放在一个链上呢?外部到底怎么运作的?往下看 ↓

2.3.1 成员变量与外部类

指标:先理解一下它的根本构造

回顾:位运算(上面还会频繁用到)

1<<4

二进制相当于 1 左边补 4 个 0:10000

十进制相当于 1 x 2 的 4 次方,也就是 16

二进制运算是因为它的计算效率高

        
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //16,默认数组容量:左位移 4 位,即 16
    static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量:即 2 的 30 次幂
    static final float DEFAULT_LOAD_FACTOR = 0.75f;// 负载因子:扩容应用,统计学计算出的最正当的
    static final int TREEIFY_THRESHOLD = 8;// 链表转红黑树阈值
    static final int UNTREEIFY_THRESHOLD = 6;// 当链表的值小 <6, 红黑树转链表

         ……

    transient Node<K,V>[] table;//HashMap 中的数组, 中间状态数据
    transient Set<Map.Entry<K,V>> entrySet;// 用来寄存缓存, 中间状态数据;

    transient int size;//size 为 HashMap 中 K - V 的实时数量(重点), 留神!不是 table 的长度!transient int modCount;// 用来记录 HashMap 的批改次数,几个汇合里都有它
    int threshold;// 扩容临界点;(capacity * loadFactor)(重点)final float loadFactor;// 负载因子  DEFAULT_LOAD_FACTOR = 0.75f 赋值

具体的 key,value 放在哪里呢?答案是一个动态外部类(1.8 前是 Entry)

 static class Node<K,V> implements Map.Entry<K,V> {// 数组和链表上的节点,1.8 前叫 Entry
        final int hash;// 扰动后的 hash
        final K key;//map 的 key
        V value;//map 的 value
        Node<K,V> next;// 下个节点

        Node(int hash, K key, V value, Node<K,V> next) { // 构造函数,没啥说的
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;// 链表下一个
        }
 }
                

2.3.2 HashMap 结构器

1)指标:学习上面的三个结构器,它们都干了哪些事件?

    public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; //  负载因子 DEFAULT_LOAD_FACTOR = 0.75f}
    public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
          // 赋值,多了一些边界判断
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity:" +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor:" +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);  // 留神,map 里是没有 capacity 这个类变量的!}

map 的构造函数就做了几个赋值这么点事?这么简略?错!接着往下看

2)无参构造函数验证

第一步:增加以下 debug 变量

第二步:应用默认构造函数时,在 put 之前和之后别离 debug 以上变量信息比照看看

put 之前:

<img src=”pic/image-20210507164837142.png” alt=”image-20210507164837142″ style=”zoom:50%;” />

之后

<img src=”pic/image-20210507165029294.png” alt=”image-20210507165029294″ style=”zoom:50%;” />

毫无违和感,那么,咱们接着往下!

3)自定义初始化参数验证

接下来咱们胡搞一下,让容量 =15,因子 =0.5,猜一猜会产生什么?

调试到 put 之后,再来看:

源码分析:

在有参数结构时,最终 tableSizeFor

        //capacity 函数,初始化了 table,就是 table 的 length,否则取的是 threshold
        final int capacity() {return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

        // 带参数的初始化,其实 threshold 调用的是以下函数:// 这是什么神操作???// 其实是将 n 转成 2 进制,右移再和本人取或,相当于把外面所有的 0 变成了 1
        // 最终目标:找到 >= n 的,1 结尾前面全是 0 的数。如果 n =111,那就是 1000;如果 n =100,那就是它本人
        // 而这个数,恰好就是 2 的指数,为前面的扩容做铺垫
        static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;  // 到这一步 n 曾经各个位都是 1 了。// 范畴校验,小于 0 返回 1,大于最大值返回最大值,绝大多数失常状况下,返回 n +1,也就是 10000……
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

        
        

调试案例:

package com.mmap;

public class TableSizeTest {public static void main(String[] args) {System.out.println(tableSizeFor(9));  // 9 的二进制更能看出以下变动
    }

    static final int tableSizeFor(int cap) {System.out.println(Integer.toBinaryString(cap));  //1001
        int n = cap - 1;
        System.out.println(Integer.toBinaryString(n)); //1000
        n |= n >>> 1;   // 无符号右移,后面补 0
        System.out.println(Integer.toBinaryString(n)); // 右移再或,1100
        n |= n >>> 2;
        System.out.println(Integer.toBinaryString(n)); // 再挪动 2 位,1111
        n |= n >>> 4;
        System.out.println(Integer.toBinaryString(n)); // 就这么长,再迁徙也是 1111
        n |= n >>> 8;
        System.out.println(Integer.toBinaryString(n));
        n |= n >>> 16;
        System.out.println(Integer.toBinaryString(n)); //Integer 的最大长度 32 位,16 折半后迁徙全笼罩
        System.out.println(Integer.toBinaryString(n+1));
        return  n + 1;  //+ 1 后变为 10000,也就是 16,2 的 4 次方
    }
}

4)总结:

map 的构造函数没有你设想的那么简略!

  • 无参结构时,容量 =16,因子 =0.75。第一次插入数据时,才会初始化 table、阈值等信息
  • 有参结构时,不会容忍你胡来,会取大于然而最靠近你容量的 2 的指数倍(想一下为什么?提醒:和扩容规定无关)
  • 无论哪种结构形式,扩容阈值最终都是 =(容量 * 因子)

2.3.3 HashMap 插入方法

指标:图解 + 代码 + 断点剖析 put 源码

1)先理解下流程图

<img src=”assets/map-put-1609730434509-1609839160182.jpg” alt=”map-put” style=”zoom:150%;” />

2)对于 key 做 hash 值的计算

当咱们调用 put 办法增加元素时,理论是调用了其外部的 putVal 办法,第一个参数须要对 key 求 hash 值

   public V put(K key, V value) {return putVal(hash(key), key, value, false, true);// 调用 Map 的 putVal 办法
    }

小发问:map 里所谓的 hash 是间接用的 key 的 hashCode 办法吗?

    static final int hash(Object key) {
        int h;
          //【知识点】hash 扰动
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

图解:

<img src=”pic/Center.png” alt=”img” style=”zoom: 150%;” />

论断:应用移位和异或做二次扰动,不是间接用的 hashCode!

3)外围逻辑

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {//onlyIfAbsent:true 不更改现有值;evict:false 示意 table 为创立状态
          // 几个长期变量://tab= 数组,p= 插槽指针,n=tab 的长度,i 数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)// 数组是否 null 或者 ==0,第 1 次 put 为空
              // 初始化数组(or 扩容),所以 table 是在这里初始化的,不是 new 的时候!// 初始时,n=16
            n = (tab = resize()).length;  // resize,上面独自讲扩容
          
          //【知识点】为何 1 与 17 在一个槽上!机密就藏在寻址这里
        if ((p = tab[i = (n - 1) & hash]) == null)// 寻址:(n - 1) & hash(重要!)tab[i] = newNode(hash, key, value, null);// 以后插槽没有值,空的!将新 node 间接扔进去
        else {  // 有值,阐明插槽上产生了碰撞,须要追加成链表了!// 还是长期变量
              //e= 是否找到与以后 key 雷同的节点,找到阐明是更新,null 阐明是新 key 插入
              //k= 长期变量,查找过程中的 key 在这里暂存用
            Node<K,V> e; K k;  
            if (p.hash == hash &&  // 如果正好,插槽第一个节点(p),跟插入的 key 雷同
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; // 就将它赋值给 e,留神!这时候还没笼罩下来,只是标记到 e,发现了雷同 key 的节点!else if (p instanceof TreeNode) // 如果不是这个 key,然而类型是一个红黑树节点
                  // 这阐明以后插槽的链很长,曾经变成红黑树了,就调 putTreeVal,扔到这颗树上去
                  // 树的插入,这里不赘述,在数据结构课中有
                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);// 而后把 key 封装成新 node 追加到尾巴上
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度计数如果 >8 转红黑树
                            treeifyBin(tab, hash);// 转成树
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;// 如果遍历过程中找到雷同 key,那就赋给 e,break 跳出 for 循环,执行前面的逻辑
                    p = e;
                }
            }
            if (e != null) { // 如果 e 非空,阐明后面一顿猛如虎的操作后,找到了雷同的 key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;// 看看 onlyIfAbsent,如果让笼罩那就笼罩,不让那就算了
                afterNodeAccess(e);
                return oldValue;// 返回笼罩前的 value 值,也就是 put 办法的返回值
            }
        }
        ++modCount;// 用来记录 HashMap 的批改次数
        if (++size > threshold)//key 的数量是否大于阈值
            resize();// 如果 size 大于 threshold,就须要进行扩容
        afterNodeInsertion(evict);
        return null;
    }

4)重点(寻址计算):

接上文,对于 hash 值获得后,放入 tab 的哪个插槽,也就是所谓的寻址咱们重点来讲

(n - 1) & hash

咱们还是以开始的例子,1 和 17 为例,他们的 hash 计算后正好是 1 和 17 自身,咱们能够验证一下

Integer i = new Integer(1);
Integer j = new Integer(17);
System.out.println(i.hashCode() ^ i.hashCode()>>16);  //1
System.out.println(j.hashCode() ^ j.hashCode()>>16);  //17

开始位运算

默认 n =16,n- 1 也就是 15,二进制是 1111

那么 15 & 1
1 1 1 1
0 0 0 1
与运算后 = 1

再来看 15 & 17,17 是 10001
  1 1 1 1
1 0 0 0 1
与运算后 = 1

所以,1 和 17 必定会落在 table 的 1 号插槽上!两者会成为链表,解释了咱们后面的案例

原理:不论你算出的 hash 是多少,超出 tab 长度的高位被抹掉,低位是多少就是你所在的槽的地位,也就是 table 的下标

思考:为什么不必 mod(模运算)进行寻址?mod 也能保障不会超出数组边界,岂不是更简略直观?

package com.mmap;

public class CMod {public static void main(String[] args) {bit();
        mod();}

    public static void bit() {
        int a ;
        long start = System.currentTimeMillis();
        // 同样的计算次数,先位运算,后取余
        for (int i = 1; i < Integer.MAX_VALUE; i++) {a = 1 & i;}
        long end = System.currentTimeMillis();
        System.out.println("BIT 耗时 >>" + (end - start));

    }

    public static void mod() {
        int a ;
        long start = System.currentTimeMillis();
        for (int i = 1; i < Integer.MAX_VALUE; i++) {a = 1 % i;}
        long end = System.currentTimeMillis();
        System.out.println("MOD 耗时 >>" + (end - start));

    }

}

跑一下试试?

论断:

所有为了性能

2.3.4 HashMap 扩容办法

指标:图解 + 代码(map 扩容与数据迁徙)

留神:扩容简单、绕、难

备注:线程不平安的

图解:假如咱们 new HashMap(8)

迁徙前:长度 8 扩容临界点 6(8*0.75)

迁徙过程

外围源码 resize 办法

// 留神!该办法兼容了初始化和扩容,所以比拟难理分明!// 须要对照下面的图例来同步解说。final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 旧的数组先拿进去
        int oldCap = (oldTab == null) ? 0 : oldTab.length;// 旧数组是 null,那就是初始化咯
        int oldThr = threshold;// 扩容临界点(旧)
        int newCap, newThr = 0;// 长期变量,数组容量(新)、扩容临界点(新)
        if (oldCap > 0) {
              // 扩容的时候调用
            if (oldCap >= MAXIMUM_CAPACITY) { // 如果旧值达到下限
                threshold = Integer.MAX_VALUE; // 扩容阈值也调到最大,从此再无意义
                return oldTab;  // 不扩了,间接返回旧的。下限了还扩什么扩
            }
              // 如果没到下限就计算新容量,留神这时候还没产生理论的数组扩容,真正的扩容迁数据操作在上面
              // 将旧容量左移 1 位,也就是乘以 2 作为新容量,所以 map 是每次扩到之前的 2 倍
              // 链表是右移 1 位再加上旧长度,也就是扩为原来的 1.5 倍,留神区别
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 同时,阈值也乘以 2,为下次扩容做筹备
        }
        else if (oldThr > 0) 
              // HashMap(int initialCapacity, float loadFactor)初始化的时候调用
              // 将 cap 和 thres 相等,约定
            newCap = oldThr;
        else {// HashMap() 初始化的时候调用,留神后面验证过了,是在第一次 put 的时候调的
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {// 如果新阈值为 0,依据负载因子设置新阈值
            float ft = (float)newCap * loadFactor; // put 之后的变动就在这里
            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) {  // 遍历数组
                Node<K,V> e; // 长期变量,记录以后指向的 node
                if ((e = oldTab[j]) != null) {oldTab[j] = null;//gc 解决
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;// 只一个节点,赋值到新数组的索引下即可
                    else if (e instanceof TreeNode)// 如果变成了树,拆成俩拼到新 table 下来
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 如果是链表,拆成两个(重点!!!)Node<K,V> loHead = null, loTail = null;// 低位链表(原地位 i)Node<K,V> hiHead = null, hiTail = null;// 高位链表(i+ n 地位)Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {  //oldCap=8,2 进制为 1000
                                  // 如果为 0,阐明 e 的 hash 没超出旧 cap 长度去,在低位不动即可
                                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;// 下标:原地位 + 原数组长度(重点!)// 这中央诠释了为什么 map 要两倍扩容,对应地位位运算后,加上原长度就行了
                        }
                    }
                }
            }
        }
        return newTab;// 返回新数组
    }

总结(扩容与迁徙):

1、扩容就是将旧表的数据迁徙到新表

2、迁徙过来的值须要从新计算下标,也就是他的存储地位

3、对于地位能够这样了解:比方旧表的长度 8、新表长度 16

旧表地位 4 有 6 个数据,如果前三个 hashCode 是一样的,前面的三个 hashCode 是一样的

迁徙的时候;就须要计算这 6 个值的存储地位

4、如何计算地位?采纳低位链表和高位链表;如果地位 4 上面的数据 e.hash & oldCap 等于 0,

那么它对应的就是低位链表,也就是数据地位不变

5、e.hash & oldCap 不等于 0 呢? 就要重写计算他的地位也就是 j + oldCap,(4+8)= 12,就是高位链表地位(新数组 12 地位)

2.3.5 HashMap 获取办法

指标:图解(这个简略!)

获取流程

<img src=”assets/map 查找流程 -1607499200869.jpg” alt=”map 查找流程 ” style=”zoom:80%;” />

get 主办法

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;// 重点在 getNode
    }

getNode 办法

    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) {
              // 如果 table 对应的索引地位上有值
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;// 看下第一个元素的 key 是不是要查找的那个,是的话,返回即可
            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;
    }

总结:

查问思路比较简单,如果是数组间接返回、如果是红黑实例,就去树上去找,最初,去做链表循环查找

2.3.6 HashMap 移除办法

指标:图解 + 断点剖析 remove 源码

移除流程

tips:

两个移除办法,参数上的区别

走的同一个代码

移除办法:一个参数

    public V remove(Object key) {
        Node<K,V> e;//// 定义一个节点变量,用来存储要被删除的节点(键值对
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

移除办法:二个参数

    @Override
    public boolean remove(Object key, Object value) {return removeNode(hash(key), key, value, true, true) != null;
    }

外围办法 removeNode

    /**
     * Implements Map.remove and related methods
     *
     * @param hash 扰动后的 hash 值
     * @param key 要删除的键值对的 key,要删除的键值对的 value,该值是否作为删除的条件取决于 matchValue 是否为 true
     * @param value key 对应的值
     * @param matchValue 为 true,则当 key 对应的值和 equals(value)为 true 时才删除;否则不关怀 value 的值
     * @param movable 删除后是否挪动节点,如果为 false,则不挪动
     * @return 返回被删除的节点对象,如果没有删除任何节点则返回 null
     */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {  // 留神,p 是以后插槽上的头节点!// 第一步:查,和下面的 get 操作一毛一样
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;// 如果 key 雷同,阐明是头结点,将它赋给 node
            else if ((e = p.next) != null) {
                  // 否则,沿着 next 始终查找
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);// 红黑查找
                else {
                    do { // 链表查找
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;  // 如果找到,赋值给 node,并终止
                            break;
                        }
                        p = e; // 如果没找到,赋值给 p,持续下一轮。} while ((e = e.next) != null);  
                  // 最终 while 完结的时候,p(前置)-> node(要被删)
                }
            }
          
              // 第二步:删
              // 如果 node 不为空,阐明依据 key 匹配到了要删除的节点
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);// 红黑删除
                else if (node == p)// 不是树,那如果 node == p 的意思是该 node 节点就是首节点
                    tab[index] = node.next;// 删掉头节点,第二个节点上位到数组槽上
                else  // p 是 node 的前置,阐明下面查找的时候走的 do while
                    p.next = node.next;// 如果不是,那就将 p 的后指针指向 node 的后指针,干掉 node 即可
                ++modCount;//HashMap 的批改次数递增
                --size;// HashMap 的元素个数递加
                afterNodeRemoval(node);
                return node;// 返回删除后的节点
            }
        }
        return null;// 找不到删除的 node,返回 null
    }

总结:

  • 移除和查问路线差不多,找到后间接 remove
  • 留神他的返回值,是删除的那个节点的值

拓展:

为什么说 HashMap 是线程不平安的

咱们从后面的源码剖析也能看出,它的元素增删改的时候,没有任何加锁或者 cas 操作。

而这外面各种 ++ 和 – 之类的操作,显然多线程下并不平安

那谁平安呢?下节课咱们剖析

本文由传智教育博学谷 – 狂野架构师教研团队公布,转载请注明出处!

如果本文对您有帮忙,欢送关注和点赞;如果您有任何倡议也可留言评论或私信,您的反对是我保持创作的能源

退出移动版