• HashMap源码解析（jdk1.8，万字大章，图文并茂）

    HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

    一、Hash冲突

    在读hashMap源码之前，我们先了解一下什么是hash冲突。

    1、hash算法和hash表

    Hash算法就是把任意的输入通过散列算法变成固定长度的输出（散列值），这个输出结果就是一个散列值。
    我们通过Hash算法，把key映射到表中的某个位置，来获取这个位置的数据，从而加快数据的查找，这个就是hash表。通过key直接访问到内存存储位置。
    举个栗子：
    在这里插入图片描述

    hash(a)计算出key在Hash表中的位置，然后在这个位置进行存取。

    2、hash冲突

    什么是hash冲突呢？从上图可以看出，在hash函数计算之后，会有一个固定的值，这个固定的值是有限的，但是需要计算的key有无限种可能，这时候就会发生不同的key值计算出来的固定值是相同的，这个时候数据存放的位置就是相同的。不同的值经过hash算法计算后，得到相同的hash值，就是hash冲突。
    怎么解决hash冲突呢？一般有以下四种方法：
    （1）开放地址法
    简单来说，就是如果发生冲突了，就往后找，找一个空位置来存储。ThreadLocal用的就是开放地址法。
    有线性探测再散列和平方探测再散列，顾名思义，就是往后找，或者按当前位置的+1平方或者-1平方的位置，这里就不深究了。
    画个图，如下：
    在这里插入图片描述
    （2）链地址法
    把有hash冲突的key值，以链表的形式存储再同一个位置。HashMap用的链地址法。
    在这里插入图片描述
    （3）再hash法
    如果发生冲突，用另一个方法计算hash值，两次结果值不一样就不会发生hash冲突；
    （4）建立公共溢出区
    将哈希表分为基本表和溢出表两部分，和基本表发生冲突的元素，一律填入溢出表。

    二、HashMap解析

    1、数据结构

    jdk1.8之后，HashMap的数据结构变成了数组+链表+红黑树。
    如图所示：
    在这里插入图片描述
    为什么这么设计呢？首先，jdk1.7的时候采用的链地址法解决hash冲突，链表查询的时间复杂度是O(n)；jdk1.8中如果链表长度超过8位，且数组长度超过64位时，采用红黑树，增删查改的时间复杂度都为O(log n)，减少查询时间，提高了效率。如果链表不超过8位或者数组长度不超过64位时，直接对数组扩容。
    我们看以下源码：
    （1）HashMap基础属性

    public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    //序列号，序列化的时候使用。
    private static final long serialVersionUID = 362498820763181265L;
    /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，
    使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
    //默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量，2的30次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子，用于扩容使用。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //当某个桶节点数量大于8 时，会转换为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    static final int UNTREEIFY_THRESHOLD = 6;
    //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
    static final int MIN_TREEIFY_CAPACITY = 64;
    //存储元素的数组，transient关键字表示该属性不能被序列化
    transient Node<K,V>[] table;
    //存放具体元素的集,迭代时使用
    transient Set<Map.Entry<K,V>> entrySet;
    //元素数量
    transient int size;
    //统计该map修改的次数
    transient int modCount;
    //临界值，也就是元素数量达到临界值时，会进行扩容。容量*填充因子
    int threshold;
    //也是加载因子，只不过这个是变量。
    final float loadFactor;  

    • 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

    loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。
    loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。 给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16* 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

    （2）Node节点
    源码如下：

    //继承自 Map.Entry
 static class Node<K,V> implements Map.Entry<K,V> {
 		// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
        final int hash;
        final K key;
        V 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;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
		//重写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;
        }
		//重写equals方法
        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;
        }
    }

    • 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

    看代码，总结一下，Node节点主要存hash、key、value、next四个值。
    如果是红黑树的话，树节点源码如下;

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
		//父节点
        TreeNode<K,V> parent;  // red-black tree links 
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        //颜色
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         * 根节点
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
......

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    红黑树源码很多，我们就不一一贴出来了。

    2、构造方法

    代码如下：

     //指定“容量大小”和“加载因子”的构造函数
 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //最大容量是2的30次方，超过这个就取这个值
        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);
    }

    /**
     * 指定“容量大小”的构造函数，使用默认的加载因子
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

  	//无参构造方法，使用默认的加载因子
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 包含另一个“Map”的构造函数，传入一个Map，然后把该Map转为hashMap
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }


    • 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

    putMapEntries方法源码如下：

     final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
        	//判断table是否已经初始化，存储元素的数组
            if (table == null) { // pre-size
            //求出需要的容量，因为实际使用的长度=容量*0.75得来的
            //+1F是为了向上取整
                float ft = ((float)s / loadFactor) + 1.0F;
                //判断该容量大小是否超出上限
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                //计算得到的t大于临界值，则初始化临界值
                if (t > threshold)
                //tableSizeFor(t)这个方法会返回大于t值的，且离其最近的2次幂，例如t为29，则返回的值是32
                    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
    • 25
    • 26
    • 27

    3、hash方法

    源码如下：

     static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。(h = key.hashCode()) ^ (h >>> 16);是为了减少hash冲突。

    4、put方法

    代码如下：

    //put方法调用了putVal方法
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //数组未初始化或者数组长度为0，对齐扩容
        //使用的是懒加载，table一开始是没有加载的，等put后才开始加载
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //  如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，
        //  此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p
        if ((p = tab[i = (n - 1) & hash]) == null)
        	// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
            tab[i] = newNode(hash, key, value, null);
        //发生哈希冲突的几种情况
        else {
        	//桶不为空
        	//e 临时节点的作用， k 存放该当前节点的key 
            Node<K,V> e; K k;
            //第一种,比较桶中第一个元素(数组中的结点)与插入值的hash值相等，key相等，e = p，则表示为首节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点
            else if (p instanceof TreeNode)
            	//放入树中
            	//在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功
            	//如果添加成功返回null
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
            //遍历该链表
                for (int binCount = 0; ; ++binCount) {
                	//链表尾部
                	//表明添加的key-value没有重复，在尾部进行添加
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判断是否要转换为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中有重复的key，e则为当前重复的节点，结束循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //有重复的key，则对待插入值进行覆盖，返回旧值。——第一种第二种第三种结束之后的判断
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //统计该map修改的次数
        //到了此步骤，则表明待插入的key-value是没有key的重复,因为重复的都return了
        ++modCount;
        //实际长度+1，判断是否大于临界值，大于则扩容
        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
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    特别说明：
    (n - 1) & hash 是数组的下标，也就是存放的位置，是无序的。
    看代码太枯燥，我们直接上图：
    在这里插入图片描述

    整个人都舒服了。。。。。

    5、扩容resize方法

    代码如下：

    final Node<K,V>[] resize() {
		//没扩容之前叫odlTab
        Node<K,V>[] oldTab = table;
        //oldTab的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //当前的临界值
        int oldThr = threshold;
        //初始化new的长度和临界值
        int newCap, newThr = 0;
        //oldCap > 0也就是说不是首次初始化，因为hashMap用的是懒加载
        if (oldCap > 0) {
        //超过最大值就不再扩充了，就只好随你碰撞去吧
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //没超过最大值，就扩充为原来的2倍*****初始化大于等于16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //临界值也扩容为old的临界值2倍
                newThr = oldThr << 1; // double threshold
        }
        //如果oldCap<0，但是已经初始化了，像把元素删除完之后的情况，那么它的临界值肯定还存在，        
        //如果是首次初始化，它的临界值则为0
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //首次初始化，给与默认的值
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            //临界值等于容量*加载因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //始化时容量小于默认值16的*****，此时newThr没有赋值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            //判断是否new容量是否大于最大值，临界值是否大于最大值
            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;
        //把old中的元素，遍历到new中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        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;
                            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
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90

    总结一下：
    （1）初始化数组长度是16，临界值是12；
    （2）超过最大长度就不再扩充了；
    （3）没超过最大值，就扩充为原来的2倍，临界值也扩充为2倍；
    （4）对应初始化数组长度小于16了，需计算临界值，容量*加载因子。

    6、get方法

    源码如下：

    public V get(Object key) {
        Node<K,V> e;
        //计算key的hash值
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    final Node<K,V> getNode(int hash, Object key) {
		//first 头结点，e 临时变量，n 长度,k key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //数组下标的节点赋值first头结点
        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) {
            	//是不是红黑树
                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);
            }
        }
        //都找不到返回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

    总结，就是从头开始找，然后判断红黑树，从树里找，不然就从链表找。

    7、remove方法

    代码如下：

    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
     public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

    • 1
    • 2
    • 3

    第一参数为哈希值，第二个为key，第三个value（value值为空的话，表示将key节点全都删除，不要再去查询了），
    第四个为true的话，则表示删除它key对应的value，不删除key；
    第五个如果为false，则表示删除后，不移动节点。

    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;
        //获得到要删除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;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果数组下标的头节点正好是要删除的节点，把值赋给临时变量node
                node = p;
            //要删除的节点，在链表或者红黑树上，先判断是否为红黑树的节点
            else if ((e = p.next) != null) {
                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;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            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

    总结一哈，先删头节点，不然就红黑树，不然就链表删除。

    三、总结

    1、hash冲突是因为hash函数计算后，值相同，占数组里的同一个位置导致的；
    2、数组+链表+红黑树，几个数：16，0.75，12，8，64，扩容是2倍，HashMap 总是使用 2 的幂作为哈希表的大小。
    3、HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。

  • 相关阅读:
    表单基本操作
    学习 RabbitMQ 这一篇就够了
    rush learn note
    算法第七天：leetcode之209.长度最小的子数组
    iNFTnews｜传统Web2品牌商如何进军元宇宙?
    python问题：vscode切换环境，pip安装库网络错误
    JS——数字字符串的比较逻辑分析
    商业合作保密协议书范本(中英文对照版))
    [HackMyVM]靶场 Quick3
    热更新的代码实现
  • 原文地址：https://blog.csdn.net/liwangcuihua/article/details/125725559