HashMap源码分析

阅读量：4224 次

发布时间：2019-05-26

本文共 20159 字，大约阅读时间需要 67 分钟。

文章目录

概述

HashMap最早出现在JDK 1.2中，底层基于散列算法实现。HashMap允许null键和null值，在计算键的哈希值时，null键哈希值为0。HashMap并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap是非线程安全类，在多线程环境下可能会存在问题。

原理

散列算法的冲突处理方式分为散列再探测和链地址法。HashMap则使用了链地址法，并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下：

对于拉链式的散列算法，其数据结构是由数组和链表（或树形结构）组成。在进行增删查等操作时，首先要定位到元素的所在桶的位置，之后再从链表中定位该元素。比如我们要查询上图结构中是否包含元素35，步骤如下：

定位元素35所处桶的位置，index = 35 % 16 = 3

在3号桶所指向的链表中继续查找，发现35在链表中。

上面就是HashMap底层数据结构的原理，HashMap基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于JDK 1.8中引入了红黑树，底层数据结构由数组+链表变为了数组+链表+红黑树，不过本质并未变。

与JDK 1.7相比，JDK 1.8对HashMap进行了一些优化。比如引入红黑树解决过长链表效率低的问题。重写resize方法，移除了alternative hashing相关方法，避免重新计算键的hash等。

源码分析

构造方法

HashMap有四个构造方法。HashMap构造方法做的事情比较简单，一般都是初始化一些重要变量，比如loadFactor（负载因子）和threshold（容纳量）。而底层的数据结构则是延迟到插入键值对时再进行初始化。HashMap相关构造方法如下：

/** 构造方法 1 */public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/** 构造方法 2 */public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** 构造方法 3 */public HashMap(int initialCapacity, float loadFactor) {
       //初始容量不能<0     if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +                                           initialCapacity);    //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30     if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    //负载因子不能 < 0     if (loadFactor <= 0 || Float.isNaN(loadFactor))        throw new IllegalArgumentException("Illegal load factor: " +                                           loadFactor);    this.loadFactor = loadFactor;    //设置HashMap的容量极限    this.threshold = tableSizeFor(initialCapacity);}/** 构造方法 4 */public HashMap(Map
    m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;    putMapEntries(m, false);}

初始容量、负载因子、阈值

一般情况下，都会使用无参构造方法创建HashMap。但当我们对时间和空间复杂度有要求的时候，使用默认值有时可能达不到我们的要求，这个时候需要手动调参。在HashMap构造方法中，可供我们调整的参数有两个，一个是初始容量initialCapacity，另一个负载因子loadFactor。通过这两个设定这两个参数，可以进一步影响阈值大小。但初始阈值threshold仅由initialCapacity经过移位操作计算得出。他们的作用分别如下：

enter description here

/** The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;/** The load factor used when none specified in constructor. */static final float DEFAULT_LOAD_FACTOR = 0.75f;final float loadFactor;/** The next size value at which to resize (capacity * load factor). */int threshold;

默认情况下，HashMap初始容量是16，负载因子为0.75。这里并没有默认阈值，原因是阈值可由容量乘上负载因子计算而来（注释中有说明），即threshold = capacity * loadFactor。初始化threshold的方法源码如下：

/** * Returns a power of two size for the given target capacity. */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;}

该方法的目的为：找到大于或等于cap的最小2的幂。

上面是 ableSizeFor方法的计算过程图，这里cap = 536,870,913 = 2²⁹ + 1，多次计算后，算出n + 1 = 1,073,741,824 = 2³⁰

对于HashMap来说，负载因子是一个很重要的参数，该参数反应了HashMap桶数组的使用情况（假设键值对节点均匀分布在桶数组中）。通过调节负载因子，可使HashMap时间和空间复杂度上有不同的表现。当我们调低负载因子时，HashMap 所能容纳的键值对数量变少。扩容时，重新将键值对存储新的桶数组里，键的键之间产生的碰撞会下降，链表长度变短。此时，HashMap 的增删改查等操作的效率将会变高，这里是典型的拿空间换时间。相反，如果增加负载因子（负载因子可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高。这意味着链表长度变长，效率也随之降低，这种情况是拿时间换空间。至于负载因子怎么调节，这个看使用场景了。一般情况下，我们用默认值就可以了。

节点

HashMap的底层数据结构是一个Node[]，Node是HashMap的一个内部类，源代码如下：

transient Node
   
    [] table;static class Node
    
      implements Map.Entry
     
       {
           final int hash;        final K key;        V value;        Node
      
        next;        Node(int hash, K key, V value, Node
       
         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; }        public final int hashCode() {
               return Objects.hashCode(key) ^ Objects.hashCode(value);        }        public final V setValue(V newValue) {
               V oldValue = value;            value = newValue;            return oldValue;        }        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;        }    }

查找

查找先定位键值对所在的桶的位置，然后再对链表或红黑树进行查找。通过这两步即可完成查找，该操作相关代码如下：

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;    // 1. 定位键值对所在桶的位置    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) {
               // 2. 如果 first 是 TreeNode 类型，则调用黑红树查找方法            if (first instanceof TreeNode)                return ((TreeNode
       
        )first).getTreeNode(hash, key);                            // 2. 对链表进行查找            do {
                   if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}

查找的核心逻辑是封装在 getNode 方法中的，查找过程的第一步是确定桶位置，其实现代码如下：

// index = (n - 1) & hashfirst = tab[(n - 1) & hash]

HashMap中桶数组的大小 length 总是2的幂，此时，(n - 1) & hash 等价于对 length 取余。

在上面源码中，除了查找相关逻辑，还有一个计算 hash 的方法。这个方法源码如下：

/** * 计算键的 hash 值 */static final int hash(Object key) {
       int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

这样做有两个好处，图中的hash是由键的hashCode产生。计算余数时，由于n比较小，hash只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的hash高4位数据与低4位数据进行异或运算，即hash ^ (hash >>> 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：

在 Java 中，hashCode 方法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位。

上面所说的是重新计算hash的一个好处，除此之外，重新计算 hash 的另一个好处是可以增加hash的复杂度。当我们覆写hashCode方法时，可能会写出分布性不佳的hashCode方法，进而导致hash的冲突率比较高。通过移位和异或运算，可以让hash变得更复杂，进而影响hash的分布性。这也就是为什么HashMap不直接使用键对象原始hash的原因了。

遍历

// 遍历键for(Object key : map.keySet()) {
       // do something}// 遍历值for(HashMap.Entry entry : map.entrySet()) {
       // do something}

上面代码片段中用foreach遍历keySet方法产生的集合，在编译时会转换成用迭代器遍历，等价于：

Set keys = map.keySet();Iterator ite = keys.iterator();while (ite.hasNext()) {
       Object key = ite.next();    // do something}

KeySet的源代码：

public Set
   
     keySet() {
       Set
    
      ks = keySet;    if (ks == null) {
           ks = new KeySet();        keySet = ks;    }    return ks;}/** * 键集合 */final class KeySet extends AbstractSet
     
       {
       public final int size()                 {
    return size; }    public final void clear()               {
    HashMap.this.clear(); }    public final Iterator
      
        iterator()     {
    return new KeyIterator(); }    public final boolean contains(Object o) {
    return containsKey(o); }    public final boolean remove(Object key) {
           return removeNode(hash(key), key, null, false, true) != null;    }    // 省略部分代码}/** * 键迭代器 */final class KeyIterator extends HashIterator     implements Iterator
       
         {
       public final K next() {
    return nextNode().key; }}abstract class HashIterator {
       Node
        
          next; // next entry to return Node
         
           current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node
          
           [] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry // 寻找第一个包含链表节点引用的桶 do { } while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node
           
             nextNode() { Node
            
             [] t; Node
             
               e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { // 寻找下一个包含链表节点引用的桶 do { } while (index < t.length && (next = t[index++]) == null); } return e; } //省略部分代码}

遍历所有的键时，首先要获取键集合KeySet对象，然后再通过KeySet的迭代器KeyIterator进行遍历。KeyIterator类继承自HashIterator类，核心逻辑也封装在HashIterator类中。HashIterator的逻辑并不复杂，在初始化时，HashIterator先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历；找不到，则结束遍历。

插入

首先HashMap是变长集合，所以需要考虑扩容的问题。其次，在JDK 1.8中，HashMap引入了红黑树优化过长链表，因此插入过程较为复杂。

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;    // 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // 如果桶中不包含键值对节点引用，则将新键值对节点的引用存入桶中即可    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {
           Node
     
       e; K k;        // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;                    // 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法        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) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                                // 条件为 true，表示当前链表包含要插入的键值对，终止遍历                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }                // 判断要插入的键值对是否存在 HashMap 中        if (e != null) {
    // existing mapping for key            V oldValue = e.value;            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    // 键值对数量超过阈值时，则进行扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}

插入操作的入口方法是put(K,V)，但核心逻辑在V putVal(int, K, V, boolean, boolean)方法中。putVal 方法主要做了这么几件事情：

当桶数组table为空时，通过扩容的方式初始化table;

查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值；

如果不存在，则将键值对链入链表中，并根据链表长度决定是否将链表转为红黑树；

判断键值对数量是否大于阈值，大于的话则进行扩容操作。

扩容机制(重点)

在 HashMap 中，桶数组的长度均是2的幂，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。HashMap的扩容机制与其他变长集合的套路不太一样，HashMap按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去。源代码如下：

final Node
   
    [] resize() {
       Node
    
     [] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    // 如果 table 不为空，表明已经初始化过了    if (oldCap > 0) {
           // 当 table 容量超过容量最大值，则不再扩容        if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;            return oldTab;        }         // 按旧容量和阈值的2倍计算新容量和阈值的大小        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold    } else if (oldThr > 0) // initial capacity was placed in threshold        /*         * 初始化时，将 threshold 的值赋值给 newCap，         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值         */         newCap = oldThr;    else {
                  // zero initial threshold signifies using defaults        /*         * 调用无参构造方法时，桶数组容量为默认容量，         * 阈值为默认容量与默认负载因子乘积         */        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }        // newThr 为 0 时，按阈值计算公式进行计算    if (newThr == 0) {
           float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;    // 创建新的桶数组，桶数组的初始化也是在这里完成的    Node
     
      [] newTab = (Node
      
       [])new Node[newCap];    table = newTab;    if (oldTab != null) {
           // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中        for (int j = 0; j < oldCap; ++j) {
               Node
       
         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 { // preserve order Node
         
           loHead = null, loTail = null; Node
          
            hiHead = null, hiTail = null; Node
           
             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;}

上面的源码总共做了3件事，分别是：

计算新桶数组的容量newCap和新阈值newThr；

根据计算出的newCap创建新的桶数组，桶数组table也是在这里进行初始化的；

将键值对节点重新映射到新的桶数组里。如果节点是TreeNode类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。

newCap和newThr计算过程

// 第一个条件分支if ( oldCap > 0) {
       // 嵌套条件分支    if (oldCap >= MAXIMUM_CAPACITY) {
   ...}    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY) {
   ...}} else if (oldThr > 0) {
   ...}else {
   ...}// 第二个条件分支if (newThr == 0) {
   ...}

分支一：

这里把oldThr > 0情况单独拿出来说一下。在这种情况下，会将oldThr赋值给newCap，等价于newCap = threshold = tableSizeFor(initialCapacity)。我们在初始化时传入的initialCapacity参数经过threshold中转最终赋值给了newCap。

嵌套分支：

当 loadFactor小数位为 0，整数位可被2整除且大于等于8时，在某次计算中就可能会导致 newThr 溢出归零。见下图：

分支二：

节点重新映射

在JDK 1.8中，重新映射节点需要考虑节点类型。对于树形节点，需先拆分红黑树再映射。对于链表类型节点，则需先对链表进行分组，然后再映射。需要的注意的是，分组后，组内节点相对位置保持不变。先来看看链表是怎样进行分组映射的。

[参考] http://www.tianxiaobo.com

链表树化

树化的代码：

static final int TREEIFY_THRESHOLD = 8;/** * 当桶数组容量小于该值时，优先进行扩容，而不是树化 */static final int MIN_TREEIFY_CAPACITY = 64;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; TreeNode(int hash, K key, V val, Node
         
           next) { super(hash, key, val, next); }}/** * 将普通节点链表转换成树形节点链表 */final void treeifyBin(Node
          
           [] tab, int hash) { int n, index; Node
           
             e; // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // hd 为头节点（head），tl 为尾节点（tail） TreeNode
            
              hd = null, tl = null; do { // 将普通节点替换成树形节点 TreeNode
             
               p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 将普通链表转成由树形节点链表 if ((tab[index] = hd) != null) // 将树形链表转换成红黑树 hd.treeify(tab); }}TreeNode
              
                replacementTreeNode(Node
               
                 p, Node
                
                  next) { return new TreeNode<>(p.hash, p.key, p.value, next);}

在扩容过程中，树化要满足两个条件：

链表长度大于等于TREEIFY_THRESHOLD（8）；

桶数组容量大于等于MIN_TREEIFY_CAPACITY（64）；

treeifyBin方法主要的作用是将普通链表转成为由TreeNode型节点组成的链表，并在最后调用treeify是将该链表转为红黑树。TreeNode继承自Node类，所以TreeNode仍然包含next引用，原链表的节点顺序最终通过next引用被保存下来。假设树化前，链表结构如下：

HashMap在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像TreeMap那样，要求键类实现comparable接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现comparable接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap是做了三步处理，确保可以比较出两个键的大小，如下：

比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较

检测键类是否实现了Comparable接口，如果实现调用compareTo方法进行比较

如果仍未比较出大小，就需要进行仲裁了，仲裁方法为tieBreakOrder

通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：

可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。

红黑树拆分

在将普通链表转成红黑树时，HashMap通过两个额外的引用next和prev保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。

// 红黑树转链表阈值static final int UNTREEIFY_THRESHOLD = 6;final void split(HashMap
   
     map, Node
    
     [] tab, int index, int bit) {
       TreeNode
     
       b = this;    // Relink into lo and hi lists, preserving order    TreeNode
      
        loHead = null, loTail = null;    TreeNode
       
         hiHead = null, hiTail = null;    int lc = 0, hc = 0;    /*      * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。     * 下面的循环是对红黑树节点进行分组，与上面类似     */    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) { // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; /* * hiHead == null 时，表明扩容后， * 所有节点仍在原位置，树结构不变，无需重新树化 */ 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); } }}

重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由TreeNode组成的链表。如果链表长度小于UNTREEIFY_THRESHOLD(6)，则将链表转换成普通链表。否则根据条件重新将TreeNode链表树化。

红黑树链化

红黑树中仍然保留了原链表节点顺序，再将红黑树转成链表就简单多了，仅需将TreeNode链表转成Node类型的链表即可。相关代码如下：

final Node
   
     untreeify(HashMap
    
      map) {
       Node
     
       hd = null, tl = null;    // 遍历 TreeNode 链表，并用 Node 替换    for (Node
      
        q = this; q != null; q = q.next) {
           // 替换节点类型        Node
       
         p = map.replacementNode(q, null);        if (tl == null)            hd = p;        else            tl.next = p;        tl = p;    }    return hd;}Node
        
          replacementNode(Node
         
           p, Node
          
            next) { return new Node<>(p.hash, p.key, p.value, next);}

删除

第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：

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;    if ((tab = table) != null && (n = tab.length) > 0 &&        // 1. 定位桶位置        (p = tab[index = (n - 1) & hash]) != null) {
           Node
       
         node = null, e; K k; V v;        // 如果键的值与链表第一个节点相等，则将 node 指向该节点        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            node = p;        else if ((e = p.next) != null) {
                 // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点            if (p instanceof TreeNode)                node = ((TreeNode
        
         )p).getTreeNode(hash, key); else { // 2. 遍历链表，找到待删除节点 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 3. 删除节点，并修复链表或红黑树 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; afterNodeRemoval(node); return node; } } return null;}