• 最详细的Hashmap源码解析


    最详细的Hashmap源码解析

    一、HashMap集合简介

    • HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null,此外,HashMap中的映射不是有序的。
    • jdk1.8之前HashMap由数组+链表组成,数组是HashMap的主体,链表则是主要为了解决哈希冲突(两个对象调用的hashCode方法计算的哈希值函数算出来的地址被其他元素占用)而存在的(“拉链法”解决冲突)。jdk1.8之后由数组+链表+红黑树组成,在解决哈希冲突时,当链表长度大于阈值(或者红黑树边界值,默认为8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。
    • 补充:将链表转换为红黑树前会判断,即便阈值大于8,但是数组长度小于64,此时并不会将链表转变为红黑树,而是选择进行数组扩容。

    这样做的好处:

    ​ 当数组比较小的时候,尽量避免使用红黑树的结构,因为红黑树也是一个平衡二叉树,我们在使用红黑树的时候,必须等保证这个二叉树的平衡,那么就会伴随着会有很多大量的保持红黑树平衡的操作,比如左旋,右旋等操作,如果数组比较小,且每一个数组对应的链表比较短的时候使用红黑树,与直接查找链表比起来,查询效率还更低。

    ​ 所以结上所述为了提高性能和减少搜索时间,底层链表长度大于8并且数组长度大于64时,链表才转换为红黑树,具体可以参考treeifyBin()方法。当然虽然增了红黑树作为底层数据结构,结构变得复杂了,但是阈值大于8并且数组长度大于64时,链表转换为红黑树时,效率也变的更高效。

    在这里插入图片描述

    二、HashMap的特点

    1. 存储无序的
    2. 键和值位置都可以是null,但是键位置只能存在一个null。
    3. 键位置是唯一的,是底层的数据结构控制的。
    4. jdk1.8前数据结构是链表+数组,jdk1.8之后是链表+数组+红黑树
    5. 阈值(边界值:treeshold)> 8并且数组长度大于64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询。

    如果链表大小超过阈值(TREEIFY_THRESHOLD, 8),图中的链表就会被改造为树形结构。如果链表长度超过阈值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表。

    JDK版本实现方式节点数>=8节点数<=6
    1.8以前数组+单向链表数组+单向链表数组+单向链表
    1.8以后数组+单向链表+红黑树数组+红黑树数组+单向链表

    三、具体步骤

    1. 计算key的hashcode值,并且与key.hashcode的高16位做异或运算(通俗的讲:计算出新插入的这个数将要挂在哪个数组里面)
    2. 判断散列表table(桶数组)是否为空或者length=0
      • 如果散列表为空时,调用resize()初始化散列表
      • 如果不为空,并且没有发生hash碰撞,则直接添加元素到散列表中去
      • 如果不为空,并且发生了hash碰撞(hashCode值相同),进行三种判断
        • 若key地址相同或者equals后内容相同,则替换旧值
        • 若是key不相同,此时为红黑树结构,则直接用红黑树插入
        • 若是链表结构,JDK1.8之前使用的头插法、JDK1.8之后使用尾插法,判断链表长度有没有大于8
          • 1、如果大于8,则判断桶数组有没有大于64,大于则进行转换为红黑树,插入键值对;否则进行调用resize()进行扩容桶数组
          • 2、不大于,若key存在,则直接覆盖掉之前的数据

    四、HashMap类静态常量以及成员变量源码解析

    1、serialVersionUID

    序列化版本号

    private static final long serialVersionUID = 362498820763181265L;
    
    • 1

    2、6个静态常量

    在这里插入图片描述

    (1)默认初始容量-必须是2的幂

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    • 1

    (2)集合最大容量最大容量。必须是2的幂<=1<<30。

    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    • 1

    (3)构造一个带指定初始容量和默认负载因子(0.75)的空HashMap。

    负载因子是一个0到1的值,相当于数据存储的占比,达到了我们设定的最大值,就要开始执行扩容操作。

    一般默认0.75最佳。

    举例:

    当负载因子是1.0的时候,也就意味着,只有当数组的8个值(这个图表示了8个)全部填充了,才会发生扩容。这就带来了很大的问题,因为Hash冲突时避免不了的。当负载因子是1.0的时候,意味着会出现大量的Hash的冲突,底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。

    **优点:**用空间换取时间,查询效率最高

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    • 1

    (4)当桶(bucket)上的(链表)结点数大于这个值时会转为红黑树

    static final int TREEIFY_THRESHOLD = 8;
    
    • 1

    (5)当桶(bucket)上的结点数小于这个值,树转为链表

    static final int UNTREEIFY_THRESHOLD = 6;
    
    • 1

    (6)桶中结构转化为红黑树对应的数组长度最小的值

    static final int MIN_TREEIFY_CAPACITY = 64;
    
    • 1

    3、table

    table 用来初始化(必须是二的n次幂)(重点)

    // 存储元素的数组 
    transient Node<K,V>[] table;
    
    • 1
    • 2

    在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry 类型。从 jdk1.8 之后是 Node 类型。只是换了个名字,都实现了一样的接口:Map.Entry。负责存储键值对数据的。

    4、entrySet

    // 存放具体元素的集合
    transient Set<Map.Entry<K,V>> entrySet;
    
    • 1
    • 2

    5、size

    HashMap 中存放元素的个数(重点)

    // 存放元素的个数,注意这个不等于数组的长度
     transient int size;
    
    • 1
    • 2

    6、modCount

    用来记录 HashMap 的修改次数

    // 每次扩容和更改 map 结构的计数器
     transient int modCount;  
    
    • 1
    • 2

    7、threshold(*)

    用来调整大小下一个容量的值计算方式为(容量*负载因子)

    // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
    int threshold;
    
    • 1
    • 2

    8、loadFactor(*)

    哈希表的负载因子(重点)

    // 负载因子
    final float loadFactor;
    
    • 1
    • 2

    说明:

    • loadFactor 是用来衡量 HashMap 满的程度,表示HashMap的疏密程度,影响 hash 操作到同一个数组位置的概率,计算 HashMap 的实时负载因子的方法为:size/capacity,而不是占用桶的数量去除以 capacity。capacity 是桶的数量,也就是 table 的长度 length。
    • loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。
    • 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap 太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。所以开发中尽量减少扩容的次数,可以通过创建 HashMap 集合对象时指定初始容量来尽量避免。
    • 在 HashMap 的构造器中可以定制 loadFactor。
    // 构造方法,构造一个带指定初始容量和负载因子的空HashMap
    HashMap(int initialCapacity, float loadFactor);
    
    • 1
    • 2

    为什么负载因子设置为0.75,初始化临界值是12?

    threshold 计算公式:capacity(数组长度默认16) * loadFactor(负载因子默认0.75)=12

    五、hashmap构造方法源码解析

    1、HashMap()

    默认的无参构造

    public HashMap() {
        // 将默认的负载因子0.75赋值给loadFactor,并没有创建数组
       this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    • 1
    • 2
    • 3
    • 4

    2、 HashMap(int initialCapacity)

    指定初始化容量和默认的负载因子的有参构造函数

     // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    • 1
    • 2
    • 3
    • 4

    3、HashMap(int initialCapacity, float loadFactor)

    构造一个执行容量和指定的负载因子的构造函数

    /*
    	 指定“容量大小”和“负载因子”的构造函数
    	 initialCapacity:指定的容量
    	 loadFactor:指定的负载因子
    */
    public HashMap(int initialCapacity, float loadFactor) {
        	// 判断初始化容量initialCapacity是否小于0
            if (initialCapacity < 0)
                // 如果小于0,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                // 如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
        	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                // 如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }
    // 最后调用了tableSizeFor,来看一下方法实现:
         /*
         	返回比指定初始化容量大的最小的2的n次幂
         */
        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;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    
    • 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

    说明:

    指定初始化容量不一定就是最终的集合容量,因为初始化容量必须要满足2的n次幂,这里会设置一个大于等于指定容量的最小的一个2的n次幂的数值。

    4、HashMap(Map m)

    继承了另外的map集合

    // 构造一个映射关系与指定 Map 相同的新 HashMap。
    public HashMap(Map<? extends K, ? extends V> m) {
        	// 负载因子loadFactor变为默认的负载因子0.75
             this.loadFactor = DEFAULT_LOAD_FACTOR;
             putMapEntries(m, false);
     }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    调用了 putMapEntries()

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取参数集合的长度
        int s = m.size();
        if (s > 0) {
            //判断参数集合的长度是否大于0,说明大于0
            if (table == null) { // 判断table是否已经初始化
                    // 未初始化,s为m的实际元素个数
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                    // 计算得到的t大于阈值,则初始化阈值
                    if (t > threshold)
                        threshold = tableSizeFor(t);
            }
            // 已初始化,并且m元素个数大于阈值,进行扩容处理
            else if (s > threshold)
                resize();
            // 将m中的所有元素添加至HashMap中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    注意

    float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

    s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数。所以 + 1.0F 是为了获取更大的容量。

    **例如:**原来集合的元素个数是 6 个,那么 6/0.75 是8,是 2 的n次幂,那么新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

    六、成员方法

    1、put(K key, V value) 集合添加元素

    	
    	//调用了putVal方法
    	public V put(K key, V value) {
        	return putVal(hash(key), key, value, false, true);
    	}
    
    	 //HashMap.put的具体实现
     	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //判定table不为空并且table长度不可为0,否则将从resize函数中获取
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
             //这样写法有点绕,其实这里就是通过索引获取table数组中的一个元素看是否为Null
            if ((p = tab[i = (n - 1) & hash]) == null)
                //若判断成立,则New一个Node出来赋给table中指定索引下的这个元素
                tab[i] = newNode(hash, key, value, null);
            else {  //若判断不成立
                Node<K,V> e; K k;
                 //对这个元素进行Hash和key值匹配
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode) //如果数组中德这个元素P是TreeNode类型
                    //判定成功则在红黑树中查找符合的条件的节点并返回此节点
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { //若以上条件均判断失败,则执行以下代码
                    //向Node单向链表中添加数据
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                             //若节点数大于等于8
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                //转换为红黑树
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e; //p记录下一个节点
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold) //判断是否需要扩容
                resize();
            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
    • 1.首先获取Node数组table对象和长度,若table为null或长度为0,则调用resize()扩容方法获取table最新对象,并通过此对象获取长度大小

    • 2.判定数组中指定索引下的节点是否为Null,若为Null 则new出一个单向链表赋给table中索引下的这个节点

    • 3.若判定不为Null,我们的判断再做分支
      3.1 首先对hash和key进行匹配,若判定成功直接赋予e

      3.2 若匹配判定失败,则进行类型匹配是否为TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e

    • 3.3 若以上判定全部失败则进行最后操作,向单向链表中添加数据若单向链表的长度大于等于8,则将其转为红黑树保存,记录下一个节点,对e进行判定若成功则返回旧值

    • 4.最后判定数组大小需不需要扩容

    2、hash方法

    位运算获取hash值

    i = (n - 1) & hash
    
    • 1

    说明:为什么要确保数组桶的大小为2的n次幂呢?作用就在这个方法,每次元素的key对应的hashcode值求余数哈希值时,比如数组桶大小为8,此时hashcode值为11,11%8=3,此时哈希值为3。我们把11和8转为二进制数,然后做异或运算,如下:

    在这里插入图片描述

    我们将11和8做二进制的异或运算,保留数组桶8的的二进制位数,4位,得到最终余数3,此时得哈希值就为3。

    为什么要用异或运算而不用直接取余数呢?

    这是因为hash表为了优化数据得查询以及存储,用位运算的方式是最快的,极大的节省了时间。

    为什么这里需要将高位数据移位到低位进行异或运算呢?

    这是因为有些数据计算出的哈希值差异主要在高位,而 HashMap 里的哈希寻址是忽略容量以上的高位的,那么这种处理就可以有效避免类似情况下的哈希碰撞。

    3、扩容方法resize()

    //重新设置table大小/扩容 并返回扩容的Node数组即HashMap的最新数据
    final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table; //table赋予oldTab作为扩充前的table数据
            int oldCap = (oldTab == null) ? 0 : oldTab.length; 
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                 //判定数组是否已达到极限大小,若判定成功将不再扩容,直接将老表返回
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                 //若新表大小(oldCap*2)小于数组极限大小 并且 老表大于等于数组初始化大小
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr*2当作新数组的大小
                    newThr = oldThr << 1; // double threshold
            }
             //若老表中下次扩容大小oldThr大于0
            else if (oldThr > 0)
                newCap = oldThr;  //将oldThr赋予控制新表大小的newCap
            else { //若其他情况则将获取初始默认大小
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //若新表的下表下一次扩容大小为0
            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; //将当前表赋予table
            if (oldTab != null) { //若oldTab中有值需要通过循环将oldTab中的值保存到新表中
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {//获取老表中第j个元素 赋予e
                        oldTab[j] = null; //并将老表中的元素数据置Null
                        if (e.next == null) //若此判定成立 则代表e的下面没有节点了
                            newTab[e.hash & (newCap - 1)] = e; //将e直接存于新表的指定位置
                        else if (e instanceof TreeNode)  //若e是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循环 获取新旧索引的节点
                            do {
                                next = e.next;
                                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;
        }
    
    
    • 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

    扩容机制

    • 什么时候才需要扩容

    当 HashMap 中的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时,就会进行数组扩容,loadFactor 的默认值是 0.75。

    • HashMap 的扩容是什么

    进行扩容,会伴随着一次重新 hash 分配,并且会遍历 hash 表中所有的元素,是非常耗时的。在编写程序中,要尽量避免 resize。

    HashMap 在进行扩容时,使用的 rehash 方式非常巧妙,因为每次扩容都是翻倍,与原来计算的 (n - 1) & hash 的结果相比,只是多了一个 bit 位,所以结点要么就在原来的位置,要么就被分配到 “原位置 + 旧容量” 这个位置。

    怎么判断是原位置还是新位置呢?

    因此元素在重新计算 hash 之后,因为 n 变为 2 倍,那么 n - 1 的标记范围在高位多 1bit(红色),因此新的 index 就会发生这样的变化。

    在这里插入图片描述

    5 是假设计算出来的原来的索引。这样就验证了上述所描述的:扩容之后所以结点要么就在原来的位置,要么就被分配到 “原位置 + 旧容量” 这个位置。

    因此,我们在扩充 HashMap 的时候,不需要重新计算 hash,

    只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就可以了,是 0 的话索引没变,是 1 的话索引变成 “原位置 + 旧容量” 。

    4、删除方法 remove()

    删除方法就是首先先找到元素的位置,如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除,树小于 6 的时候要转链表。

    删除 remove() 方法:

    // remove方法的具体实现在removeNode方法中,所以我们重点看下removeNode方法
    public V remove(Object key) {
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    removeNode() 方法

    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;
    	// 根据hash找到位置 
    	// 如果当前key映射到的桶不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            // 如果桶上的结点就是要找的key,则将node指向该结点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                // 说明结点存在下一个结点
                if (p instanceof TreeNode)
                    // 说明是以红黑树来处理的冲突,则获取红黑树要删除的结点
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 判断是否以链表方式处理hash冲突,是的话则通过遍历链表来寻找要删除的结点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 比较找到的key的value和要删除的是否匹配
            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)
                    // 链表删除
                    tab[index] = node.next;
                else
                    p.next = node.next;
                // 记录修改次数
                ++modCount;
                // 变动的数量
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        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

    5、 查找元素方法 get()

    查找方法,通过元素的 key 找到 value。

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    • 1
    • 2
    • 3
    • 4

    get 方法主要调用的是 getNode 方法,代码如下:

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 如果哈希表不为空并且key对应的桶上不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            /* 
            	判断数组元素是否相等
            	根据索引的位置检查第一个元素
            	注意:总是检查第一个元素
            */
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果不是第一个元素,判断是否有后续结点
            if ((e = first.next) != null) {
                // 判断是否是红黑树,是的话调用红黑树中的getTreeNode方法获取结点
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    // 不是红黑树的话,那就是链表结构了,通过循环的方法判断链表中是否存在该key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        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

    七、常见面试问题

    1、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?

    ​ 之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

    2、说说你对红黑树的见解?

    1、每个节点非红即黑

    2、根节点总是黑色的

    3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)

    4、每个叶子节点都是黑色的空节点(NIL节点)

    h == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    return e;
    } while ((e = e.next) != null);
    }
    }
    return null;
    }

    
    ## 七、常见面试问题
    
    **1、拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?**
    
    ​		之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
    
    **2、说说你对红黑树的见解?**
    
    1、每个节点非红即黑
    
    2、根节点总是黑色的
    
    3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
    
    4、每个叶子节点都是黑色的空节点(NIL节点)
    
    5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    【OpenCV】 - 显示图像API之imshow()对不同位深度(数据类型)的图像的处理方法
    AWS认证SAA-C03每日一题
    rpc网络
    Apache Doris 系列: 入门篇-安装部署
    2023新疆褐牛产业集群高质量发展论坛伊犁召开
    深入探索Stable Diffusion:从原理到应用的全面解析
    【Unity3D】素描特效
    HTML5中的document.visibilityState
    Air实现Go程序的热重载(热加载)
    C++ Qt开发:QUdpSocket网络通信组件
  • 原文地址:https://blog.csdn.net/qq_45830276/article/details/126768408