Java类--HashMap

1、概述

我们都知道HashMap是一个非常常用的数据结构，在java8之前是有数组+链表组合构成，在java8及之后都用的是数组+链表+红黑树组合构成。数组的每个地方都存储了kv键值对即Key-Value，这些键值对在java7中叫Entry，在java8中叫Node。

其实HashMap的底层原理就是哈希表，我么都知道哈希表是通过哈希函数计算元素应该放在数组的哪个位置，如果有两个元素通过哈希函数计算出来的值相同就会产生哈希冲突，而链表以及红黑树就是我们来解决哈希冲突的方法。我们通过HashMap的源码来了解一下HashMap的底层实现原理。

2、成员变量

//默认初始容量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;
//链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
//链表转红黑树是最小的数组长度
static final int MIN_TREEIFY_CAPACITY = 64;
//多有node节点
transient Node[] table;
//所有的键值对
transient Set> entrySet;
//元素的个数
transient int size;
//操作次数，fail-fast机制
transient int modCount;
//扩容阈值
int threshold;
//负载因子
final float loadFactor;
//链表节点
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    ....
}
//红黑树节点
static final class TreeNode extends linkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

3、构造方法

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);
}

public HashMap(int initialCapacity) {//给定容量
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {//无参构造，将默认负载因子0.75赋值给负载因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

public HashMap(Map m) {//默认负载因子，将给定的map的值复制到现在的map中
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);//这个就是先根据m.size以及负载因子确定容量，然后扩容，遍历赋值
}
//tableSizeFor方法就是获取大于cap的最小2的n次方，至于为什么我们往后看
static final int tableSizeFor(int cap) {//如果cap为14即1110
    int n = cap - 1;//n为13即1101
    n |= n >>> 1;//1101 >>> 1 = 0110，1101 | 0110 = 1111 = 15
    n |= n >>> 2;//1111 >>> 2 = 0111, 1111 | 0111 = 1111 = 15
    n |= n >>> 4;//...
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//判断是否容量超过最大容量
}

在这里面我们其实可以发现，除了用map构造，其他构造方法只是给负载因子loadFactor、threshold扩容阈值也可以理解为容量。没有进行任何初始化操作。HashMap把初始化操作放在put方法中，也就是第一次put的时候进行初始化操作，给table等内容赋值。注意一点：我们在无参构造的时候只是给loadFactor赋初值，而threshold没有复制，有参构造的时候两个全部复制了，这点区别我们放在put方法中研究。

4、原理解析 4.1、hash值计算

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//这是getNode方法中的部分代码
if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {

我们可以看到如果key为空，计算出来的hash值为0，说明HashMap的key值允许为空。

正常情况我们计算hash值直接获取key对象的hashCode就可以了，为什么还要与hashCode的高16位进行异或运算？

首先我们看getNode方法中给定一个key值，HashMap是通过(n-1) & hash(key)来确定的，为什么用这个式子嘞：

• n即table长度也就是2的n次幂，我们看下面一些例子

  14          = 00001100
  18          = 00010010
  24          = 00011000
  16 - 1 = 15 = 00001111
  14 & 15     = 00001100 = 14 = 14 % 16
  18 & 15     = 00000010 = 2 = 18 % 16
  24 & 15     = 00001000 = 8 = 24 % 16
  

• 我们可以看出(n - 1) & hash(key)即求hash(key)对n进行取模运算。那我们再看这样一些运算

  hash1                  = 10110010 00000000 10011101 11100011;
  hash1 >>> 16           = 00000000 00000000 10110010 00000000;
  hash1 ^ (hash1 >>> 16) = 10110010 00000000 00101111 11100011 = h1;
  hash2                  = 11111010 00000000 10011101 11100011;
  hash2 >>> 16           = 00000000 00000000 11111010 00000000;
  hash2 ^ (hash2 >>> 16) = 11111010 00000000 01100111 11100011 = h2;
  n - 1                  = 00000000 00000000 11111111 11111111;
  hash1 & (n - 1)        = 00000000 00000000 10011101 11100011;
  h1 & (n - 1)           = 00000000 00000000 00101111 11100011;
  hash2 & (n - 1)        = 00000000 00000000 10011101 11100011;
  h2 & (n - 1)           = 00000000 00000000 01100111 11100011;
  

• 我们看上述运算，hash1与hash2的低16位完全相同，不同的是高16位。此时n = 2 ^ 16，这是如果直接对hash1与hash2进行取模运算，那么结果一定是相同的，在哈希表中相同就代表发生了哈希冲突。看到这里详细大家就知道了为什么要与高16位进行异或运算了，就是为了降低发生哈希冲突的概率。

• 那么问题又来了，为什么要用异或运算而不是与、或、非运算？

  1010 ^ 1100 = 0110
  1010 & 1100 = 1000
  1010 | 1100 = 1110
  

• 大家是不是有那么一丢丢的想法了，那就是异或的0、1个数相比于与、或运算接近于1 : 1。至于非运算？别开玩笑了，你能对两个对象使用非运算？

4.2、get方法

public V get(Object key) {
    Node e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    //判断数组是否为空、长度是否为零、该key对应的位置是否为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //是否当前位置的头结点key与hash值与给定的一致
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //判断当前位置是否只有一个元素
        if ((e = first.next) != null) {
            //判断是否为红黑树结构
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            //到这里说明为链表结构且当头结点不是所需要的，长度不为一
            do {
                //是否当前位置的头结点key与hash值与给定的一致
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //走到这里说明没有找到key值
    return null;
}

get方法可以分为一下几步：

1、根据key值，调用hash(key)方法获取key对应的hash值。

2、根据hash值以及table长度找到在table中对应的位置。

3、判断当前位置是否有值，没有值走8。

4、判断当前位置的头结点是否为所查找的元素。

5、如果当前位置不止一个元素，则判断是否是红黑树结构，是则直接调用getTreeNode获取，然后走7.

6、循环遍历当前链表直到找打所需元素。

7、返回查找结果。

8、返回空值。

其中getTreeNode就是在红黑树中查找元素，红黑树本质上是平衡二叉树，对于平衡二叉树查找相信小伙伴们已经很熟悉了。

4.3、resize方法

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //判断table长度是否不为0
    if (oldCap > 0) {
        //如果table长度已经达到最大值，则无法扩容，只能将扩容阈值变为最大值，返回老table
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //将newCap赋值为oldCap的2倍，如果newCap<最大容量并且oldCap>=16, 则将新阈值设置为原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //此时oldTab长度为0，说明了是第一次put时的扩容。而oldThr大于0为有参构造，此时oldThr为2的n次幂，所以我们将其赋给新容量
    else if (oldThr > 0)
        newCap = oldThr;
    else {//此时oldTab长度为0，oldThr为零，说明是无参构造，所以容量与扩容阈值赋默认值，其中扩容阈值为容量乘负载因子
        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);
    }
    //将刚才计算出来的新阈值，新容量赋给新表，并用新容量建一个新表赋给newTab
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    //如果老表中有数据，则需要将其中的数据rehash，也就是重新计算hash，根据新的hash放入到新的位置
    if (oldTab != null) {
        //循环遍历老表每一个位置
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            //如果当前位置不为空，将其赋给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)e).split(this, newTab, j, oldCap);
                else { //如果e时链表结构，则对每个元素进行rehash
                    //对于某个位置的元素将那些rehash的结果只会有两个，要么还在当前位置，要么在当前位置 + oldCap，具体在下面解释
                    Node loHead = null, loTail = null;//rehash在当前位置的节点
                    Node hiHead = null, hiTail = null;//rehash在当前位置 + oldCap位置的节点
                    Node next;
                    do {
                        next = e.next;
                        //如果e的hash值与老表的容量进行与运算为0，则其位置不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //如果e的hash值与老表的容量进行与运算不为0，则其位置在当前位置 + oldCap
                        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;
}

resize实际上分为两种状态，第一种时第一次put时的resize和非第一次put的resize，简单地说就是第一次resize和非第一次resize。

第一次扩容

第一次扩容又分为有参构造和无参构造

• ==有参构造：==我们在有参构造时传入了负载因子，初时容量(初时容量赋给了扩容阈值)。

  • 将用扩容阈值代表的初时容量初始化table
  • 将容量 * 负载因子赋给扩容阈值
  • 返回空表。

• 无参构造：

  • 将默认负载因子赋给loadFactor

  • 用默认初时容量初时容量初始化table

  • 将容量 * 负载因子赋给扩容阈值

  • 返回空表。

非第一次扩容

• 如果容量大于等于最大容量，则将扩容阈值设为最大值，返回老表；否则继续走。

• 将容量扩大1倍，如果容量扩大后小于最大容量且老容量大于等于16则将扩容阈值扩大一倍。

• 根据新容量重新初始化新表。

• 遍历老表中的每一个节点。

  • 如果当前节点为空则跳过，否则继续走。

  • 将老表当前节点设置为空。

  • 如果当前节点只有一个节点，那么根据hash值与新节点重新计算位置并复制；否则继续走。

  • 如果当前节点为树形结构则调用split方法进行rehash；否则继续走。

  • 如果当前节点为链表结构

    • 如果当前节点hash & 老容量为0，则位置不变。
    • 如果当前节点hash & 老容量不为0，则位置变为当前位置+老容量。

• 返回新表。

在resize过程中有两个点相信大家也很有疑问：

为什么扩容阈值时负载因子*容量，负载因子到底代表什么？为什么默认为0.75

我们先来这样想，如果负载因子为1，也就是说扩容阈值与容量相同，那就会出现一种情况。只有table每个位置都有节点时才会进行扩容，而每个位置都有节点代表着每插入一个元素必然会发生哈希冲突，大量的哈希冲突会导致我们节点的长度变长，大于8之后就会变成红黑树，继续增长下去只会导致底层红黑树结构变的很复杂，影响我们的查询效率。

如果负载因子为0.5，那么一旦size大于容量的一半就扩容，这样哈希冲突当然减少了，但是我们有一半的空间就浪费了，这种等于空间换取效率。0.75就是介于0.5与1之间的值。负载因子就是用来平衡时间与空间的一个数值。

你可千万不要问为什么不是0.76、0.74，那我只能给你个白眼你自己体会喽！

为什么rehash的时候可以通过 hash & 老容量来确定位置，而且为什么一个位置的节点rehash后只会出现在两个位置上？

这个就是HashMap设计的巧妙之处了，看完这部分之后你差不多就悟了！！！！

我们先看这几个例子：假如老容量为16，新容量为32，老容量节点10上面有这么几个hash值：10，26，42，58

10 % 16 = 10; 10 / 16 = 0; 10 % 32 = 10; 10 & 16 = 00001010 & 00010000 = 0;
26 % 16 = 10; 26 / 16 = 1; 26 % 32 = 26; 26 & 16 = 00011010 & 00010000 = 16 !=0;
42 % 16 = 10; 42 / 16 = 2; 42 % 32 = 10; 42 & 16 = 00101010 & 00010000 = 0;
58 % 16 = 10; 58 / 16 = 3; 58 % 32 = 26; 58 & 16 = 00111010 & 00010000 = 16 !=0;

各位好兄弟看到这里有没有顿悟呀。

出现在节点10上的点全都是hash对16取模后为10的节点，现在容量变为32了，之前对16取模为10的就分成了两拨数，也就是hash / 16为奇数和偶数两拨。而 hash & 老容量就是来确定这一归属的判定。

4.3.1、split方法

final void split(HashMap map, Node[] tab, int index, int bit) {
    //扩容后的rehash，红黑树中的节点只会出现在原索引位置、原索引位置 + oldCap
    TreeNode b = this;//当前位置头结点
    TreeNode loHead = null, loTail = null;//存储在原索引位置
    TreeNode hiHead = null, hiTail = null;//存储在原索引位置 + oldCap
    int lc = 0, hc = 0;
    //循环遍历整个红黑树的全部节点进行rehash，跟之前链表的类似不在多说
    for (TreeNode e = b, next; e != null; e = next) {
        next = (TreeNode)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
	//如果原索引位置有数据
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)//节点数小于6转链表结构
            tab[index] = loHead.untreeify(map);
        else {//构造新的红黑树结构
            tab[index] = loHead;
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    //同上
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

红黑树结构的rehash跟之前链表结构类似，原因就是红黑树保留了原来链表的结构。其比链表多了一个红黑树转链表以及重新构造红黑树的操作。这个过程见下述。

4.3.2、untreeify方法

final Node untreeify(HashMap map) {
    Node hd = null, tl = null;
    //从调用该方法的节点, 即链表的头节点开始遍历, 将所有节点全转为链表节点
    for (Node q = this; q != null; q = q.next) {
        //调用replacementNode方法构建新节点
        Node p = map.replacementNode(q, null);
        //如果tl为null, 则代表当前节点为第一个节点, 将hd赋值为该节点
        if (tl == null)
            hd = p;
        //否则, 将尾节点的next属性设置为当前节点p
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

该方法就是红黑树结构转链表结构。

4.4、put方法

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) {
    Node[] tab; Node p; int n, i;
    //如果是第一次put则进行resize操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果hash对应位置节点为空则直接赋值
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        //如果对于位置头结点key与hash值与给定的对应则赋给e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)//红黑树
            e = ((TreeNode)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);
                    if (binCount >= TREEIFY_THRESHOLD - 1) //如果该位置链表长度大于8则转红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                //如果找到对应的节点，则跳出
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果找到对应的节点，如果对应value为空则直接进行更改，否则更具onlyIfAbsebt来判断是否更改
        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;
}

put方法问我们要知道几点：

• table为0要先resize
• 先找到节点然后再赋值，没有找到则创建节点
• 链表长度大于8需要转换为红黑树
• 新建节点我们需要记录HashMap结构变化，并且size + 1，然后判断是否需要resize

4.4.1、putTreeval方法

final TreeNode putTreeval(HashMap map, Node[] tab,
                               int h, K k, V v) {
    Class kc = null;
    boolean searched = false;
    //查找根节点, 索引位置的头节点并不一定为红黑树的根节点
    TreeNode root = (parent != null) ? root() : this;
    //将根节点赋值给p节点，开始进行查找
    for (TreeNode p = root;;) {
        int dir, ph; K pk;
        //如果传入的hash值小于p节点的hash值，将dir赋值为-1，代表向p的左边查找树
        if ((ph = p.hash) > h)
            dir = -1;
        //如果传入的hash值大于p节点的hash值， 将dir赋值为1，代表向p的右边查找树
        else if (ph < h)
            dir = 1;
        //如果传入的hash值和key值等于p节点的hash值和key值, 则p节点即为目标节点, 返回p节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //如果k所属的类没有实现Comparable接口 或者 k和p节点的key相等
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //第一次符合条件, 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则返回
            if (!searched) {
                TreeNode q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            //否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找
            dir = tieBreakOrder(k, pk); // dir<0则代表k xp = p;   // xp赋值为x的父节点,中间变量,用于下面给x的父节点赋值
        //dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 走进来代表已经找到x的位置，只需将x放到该位置即可
            Node xpn = xp.next;    // xp的next节点
            //创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
            TreeNode x = map.newTreeNode(h, k, v, xpn);
            //调整x、xp、xpn之间的属性关系
            if (dir <= 0)   // 如果时dir <= 0, 则代表x节点为xp的左节点
                xp.left = x;
            else        // 如果时dir> 0, 则代表x节点为xp的右节点
                xp.right = x;
            xp.next = x;    // 将xp的next节点设置为x
            x.parent = x.prev = xp; // 将x的parent和prev节点设置为xp
            // 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
            if (xpn != null)
                ((TreeNode)xpn).prev = x;
            //进行红黑树的插入平衡调整
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

在这篇文章中我们先做一个简单的了解，对于红黑树的具体操作我们后面再说。

4.4.2、treeifyBin方法

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    //如果table为空或者table的长度小于64, 调用resize方法进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //根据hash值计算索引值，将该索引位置的节点赋值给e，从e开始遍历该索引位置的链表
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
            //将链表节点转红黑树节点
            TreeNode p = replacementTreeNode(e, null);
            //如果是第一次遍历，将头节点赋值给hd
            if (tl == null)	// tl为空代表为第一次循环
                hd = p;
            else {
                // 如果不是第一次遍历，则处理当前节点的prev属性和上一个节点的next属性
                p.prev = tl;    // 当前节点的prev属性设为上一个节点
                tl.next = p;    // 上一个节点的next属性设置为当前节点
            }
            // 将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）
            tl = p;
        } while ((e = e.next) != null);
        // 将table该索引位置赋值为新转的TreeNode的头节点，如果该节点不为空，则以以头节点(hd)为根节点, 构建红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

4.4.3、treeify方法

final void treeify(Node[] tab) {
    TreeNode root = null;
    // 将调用此方法的节点赋值给x，以x作为起点，开始进行遍历
    for (TreeNode x = this, next; x != null; x = next) {
        next = (TreeNode)x.next;   // next赋值为x的下个节点
        x.left = x.right = null;    // 将x的左右节点设置为空
        // 如果还没有根节点, 则将x设置为根节点
        if (root == null) {
            x.parent = null;    // 根节点没有父节点
            x.red = false;  // 根节点必须为黑色
            root = x;   // 将x设置为根节点
        }
        else {
            K k = x.key;	// k赋值为x的key
            int h = x.hash;	// h赋值为x的hash值
            Class kc = null;
            // 如果当前节点x不是根节点, 则从根节点开始查找属于该节点的位置
            for (TreeNode p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 如果x节点的hash值小于p节点的hash值，则将dir赋值为-1, 代表向p的左边查找
                if ((ph = p.hash) > h)
                    dir = -1;
                // 如果x节点的hash值大于p节点的hash值，则将dir赋值为1, 代表向p的右边查找
                else if (ph < h)
                    dir = 1;
                // 走到这代表x的hash值和p的hash值相等，则比较key值
                else if ((kc == null && // 如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右查找
                    dir = tieBreakOrder(k, pk);
 
                TreeNode xp = p;   // xp赋值为x的父节点,中间变量用于下面给x的父节点赋值
                // dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // x和xp节点的属性设置
                    x.parent = xp;  // x的父节点即为最后一次遍历的p节点
                    if (dir <= 0)   // 如果时dir <= 0, 则代表x节点为父节点的左节点
                        xp.left = x;
                    else    // 如果时dir > 0, 则代表x节点为父节点的右节点
                        xp.right = x;
                    // 进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 如果root节点不在table索引位置的头节点, 则将其调整为头节点
    moveRootToFront(tab, root);
}

4.5、remove方法

public V remove(Object key) {
    Node e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node[] tab; Node p; int n, index;
    //判断table是否为空，为空不进行操作
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {//根据hash确定所在位置
        Node node = null, e; K k; V v;
        //如果当前位置头结点与给定的key、hash对应则赋给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)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)node).removeTreeNode(this, tab, movable);
            else if (node == p)//如果是当前位置的头结点
                tab[index] = node.next;
            else//非头结点
                p.next = node.next;
            ++modCount;//记录操作次数
            --size;//size - 1
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

remove方法就是找到节点就移除，否则返回空。

4.5.1、removeTreeNode方法

final void removeTreeNode(HashMap map, Node[] tab,
                          boolean movable) {
    // --- 链表的处理start ---
    int n;
    // 1.table为空或者length为0直接返回
    if (tab == null || (n = tab.length) == 0)
        return;
    // 2.根据hash计算出索引的位置
    int index = (n - 1) & hash;
    // 3.将索引位置的头节点赋值给first和root
    TreeNode first = (TreeNode)tab[index], root = first, rl;
    // 4.该方法被将要被移除的node(TreeNode)调用, 因此此方法的this为要被移除node节点,
    // 将node的next节点赋值给succ节点，prev节点赋值给pred节点
    TreeNode succ = (TreeNode)next, pred = prev;
    // 5.如果pred节点为空，则代表要被移除的node节点为头节点，
    // 则将table索引位置的值和first节点的值赋值为succ节点(node的next节点)即可
    if (pred == null)
        tab[index] = first = succ;
    else
        // 6.否则将pred节点的next属性设置为succ节点(node的next节点)
        pred.next = succ;
    // 7.如果succ节点不为空，则将succ的prev节点设置为pred, 与前面对应
    if (succ != null)
        succ.prev = pred;
    // 8.如果进行到此first节点为空，则代表该索引位置已经没有节点则直接返回
    if (first == null)
        return;
    // 9.如果root的父节点不为空, 则将root赋值为根节点
    if (root.parent != null)
        root = root.root();
    // 10.通过root节点来判断此红黑树是否太小, 如果是则调用untreeify方法转为链表节点并返回
    // (转链表后就无需再进行下面的红黑树处理)
    if (root == null || root.right == null ||
        (rl = root.left) == null || rl.left == null) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    // --- 链表的处理end ---
 
    // --- 以下代码为红黑树的处理 ---
    // 11.将p赋值为要被移除的node节点，pl赋值为p的左节点，pr赋值为p 的右节点
    TreeNode p = this, pl = left, pr = right, replacement;
    // 12.如果p的左节点和右节点都不为空时
    if (pl != null && pr != null) {
        // 12.1 将s节点赋值为p的右节点
        TreeNode s = pr, sl;
        // 12.2 向左一直查找，跳出循环时,s为没有左节点的节点
        while ((sl = s.left) != null)
            s = sl;
        // 12.3 交换p节点和s节点的颜色
        boolean c = s.red; s.red = p.red; p.red = c;
        TreeNode sr = s.right; // s的右节点
        TreeNode pp = p.parent;    // p的父节点
        // --- 第一次调整和第二次调整：将p节点和s节点进行了位置调换 ---
        // 12.4 第一次调整
        // 如果p节点的右节点即为s节点，则将p的父节点赋值为s，将s的右节点赋值为p
        if (s == pr) {
            p.parent = s;
            s.right = p;
        }
        else {
            // 将sp赋值为s的父节点
            TreeNode sp = s.parent;
            // 将p的父节点赋值为sp
            if ((p.parent = sp) != null) {
                // 如果s节点为sp的左节点，则将sp的左节点赋值为p节点
                if (s == sp.left)
                    sp.left = p;
                // 否则s节点为sp的右节点，则将sp的右节点赋值为p节点
                else
                    sp.right = p;
            }
            // s的右节点赋值为p节点的右节点
            if ((s.right = pr) != null)
                // 如果pr不为空，则将pr的父节点赋值为s
                pr.parent = s;
        }
        // 12.5 第二次调整
        // 将p的左节点赋值为空，pl已经保存了该节点
        p.left = null;
        // 将p节点的右节点赋值为sr，如果sr不为空，则将sr的父节点赋值为p节点
        if ((p.right = sr) != null)
            sr.parent = p;
        // 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点赋值为s节点
        if ((s.left = pl) != null)
            pl.parent = s;
        // 将s的父节点赋值为p的父节点pp
        // 如果pp为空，则p节点为root节点, 交换后s成为新的root节点
        if ((s.parent = pp) == null)
            root = s;
        // 如果p不为root节点, 并且p是pp的左节点，则将pp的左节点赋值为s节点
        else if (p == pp.left)
            pp.left = s;
        // 如果p不为root节点, 并且p是pp的右节点，则将pp的右节点赋值为s节点
        else
            pp.right = s;
        // 12.6 寻找replacement节点，用来替换掉p节点
        // 12.6.1 如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
        if (sr != null)
            replacement = sr;
        // 12.6.1 如果sr为空，则s为叶子节点，replacement为p本身，只需要将p节点直接去除即可
        else
            replacement = p;
    }
    // 13.承接12点的判断，如果p的左节点不为空，右节点为空，replacement节点为p的左节点
    else if (pl != null)
        replacement = pl;
    // 14.如果p的右节点不为空,左节点为空，replacement节点为p的右节点
    else if (pr != null)
        replacement = pr;
    // 15.如果p的左右节点都为空, 即p为叶子节点, replacement节点为p节点本身
    else
        replacement = p;
    // 16.第三次调整：使用replacement节点替换掉p节点的位置，将p节点移除
    if (replacement != p) { // 如果p节点不是叶子节点
        // 16.1 将p节点的父节点赋值给replacement节点的父节点, 同时赋值给pp节点
        TreeNode pp = replacement.parent = p.parent;
        // 16.2 如果p没有父节点, 即p为root节点，则将root节点赋值为replacement节点即可
        if (pp == null)
            root = replacement;
        // 16.3 如果p不是root节点, 并且p为pp的左节点，则将pp的左节点赋值为替换节点replacement
        else if (p == pp.left)
            pp.left = replacement;
        // 16.4 如果p不是root节点, 并且p为pp的右节点，则将pp的右节点赋值为替换节点replacement
        else
            pp.right = replacement;
        // 16.5 p节点的位置已经被完整的替换为replacement, 将p节点清空, 以便垃圾收集器回收
        p.left = p.right = p.parent = null;
    }
    // 17.如果p节点不为红色则进行红黑树删除平衡调整
    // (如果删除的节点是红色则不会破坏红黑树的平衡无需调整)
    TreeNode r = p.red ? root : balanceDeletion(root, replacement);
 
    // 18.如果p节点为叶子节点, 则简单的将p节点去除即可
    if (replacement == p) {
        TreeNode pp = p.parent;
        // 18.1 将p的parent属性设置为空
        p.parent = null;
        if (pp != null) {
            // 18.2 如果p节点为父节点的左节点，则将父节点的左节点赋值为空
            if (p == pp.left)
                pp.left = null;
            // 18.3 如果p节点为父节点的右节点， 则将父节点的右节点赋值为空
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        // 19.将root节点移到索引位置的头节点
        moveRootToFront(tab, r);
}

这块代码较长，具体移除逻辑我们放到红黑树里面讨论，要记住当前位置的节点个数小于6时要将红黑树转换为链表。

有人会问了，之前大于8的时候变红黑树，然后现在为什么不是小于8变链表而是小于6变链表？

如果一个HashMap频繁的在8整个值之间来回改变，那么就会不断地在红黑树与链表之间来回转换，这样就会大大影响效率。至于为什么是8而不是其他值，这是因为在这个值的时候两种方式的查询速率相同。

5、java7死循环问题

我们看到这里应该发现在java8中，我们resize扩容的时候，链表采用的是尾插法。但是在之前HashMap采用的是头插法，这个头插法就是造成死循环的罪魁祸首。

对于这个问题的分析可以参考：疫苗：Java HashMap的死循环

简单的来说就是，java7的HashMap进行resize之后链表会反序，而HashMap又是线程不安全的。一旦出现两个线程同时进行扩容操作，如下图所示：

线程一这时候继续执行最终会如下图：

这时候就会出现A->B->A的一个环形结构，这时候悲剧发生了。

在java8后，头插法改为了尾插法，也就是说原来是A->B，现在还是A->B，上述情况就不会发生了。

6、总结

(emmm…我发现参考博文总结写的比我好多了，就直接拿来用了…(手动狗头保命))

• HashMap的底层是个 Node数组（Node[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。
• 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key的 hashCode值；2）将 hashCode的高位参与运算，重新计算 hash值；3）将计算出来的 hash值与 “table.length - 1” 进行 & 运算。
• HashMap的默认初始容量（capacity）是 16，capacity必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity* load factor。
• HashMap在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。
• 导致 HashMap扩容后，同一个索引位置的节点重 hash最多分布在两个位置的根本原因是：1）table的长度始终为 2 的 n 次方；2）索引位置的计算方法为 “(table.length - 1) & hash”。HashMap扩容是一个比较耗时的操作，定义 HashMap时尽量给个接近的初始容量值。
• HashMap有 threshold属性和 loadFactor属性，但是没有 capacity属性。初始化时，如果传了初始化容量值，该值是存在 threshold变量，并且 Node数组是在第一次 put时才会进行初始化，初始化时会将此时的 threshold值作为新表的 capacity值，然后用 capacity和 loadFactor计算新表的真正 threshold值。
• 当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。
• 当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify方法。
• HashMap在 JDK 1.8 之后不再有死循环的问题，JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。
• HashMap是非线程安全的，在并发场景下使用 ConcurrentHashMap来代替。

7、参考链接

https://blog.csdn.net/v123411739/article/details/78996181

https://coolshell.cn/articles/9606.html