java.util.HashMap 源码分析

缘起

面试一家魔都电商的高级java工程师职位的时候，面试官问了我有木有看过HashMap的源码? 虽然对于此问题我早有心理准备并且已经纳入了阅读计划，但是无奈那时还在与前端技术搏斗~~ 所以还没看. 于是懵逼了. 最后只给了中级java工程师的offer. 于是痛定思痛，决心将hashmap掏底!

java.util.HashMap 属于那种几乎所有java码农都用过，但是具体底层没有老老实实认真关心过的东西. 但是这种在j2ee中这么重要的数据结构，是非常影响整个网站性能的, 作为一个有追求的码农，怎么能不透彻了解hashmap的底层实现原理呢?

分析

首先，如果不理解哈希表这种数据结构的话, 可以参见【1】.

我们来看看JDK的hashmap的总体结构

注意，本文分析的是JDK1.8+的java.util.HashMap. 那么一个自然的问题是为什么要分jdk1.7和jdk1.8呢? 因为JDK8以后对于太长的链表的优化采用了红黑树.(对于红黑树不熟悉的童鞋可以参考【2】)，也就是说

JDK7采用的是

（桶）数组+链表（【1】中采用的就是数组实现的哈希表）

JDK8 采用的是

（桶）数组+链表+红黑树

哈希表的插入和查找属于基操, 详见【1】

本文主要参考了【3】（一篇很棒的文章）.

至于为什么JDK8做了如此的优化，参见【4】，但是一言以蔽之就是JDK采用链表解决hash碰撞可能导致搜索复杂度最坏变成为O(n)进而导致DOS攻击的形成. 尽管jdk7也做了改进——比如扩容重hash的时候添加了时间随机因子来让hash变得更加随机. 但是重新计算hash值是相当消耗性能的. 所以JDK8将红黑树搬了出来——性能介于AVL和Splay之间的平衡查找树. 最坏也只会蜕化到O(logn). 以此抵御DOS攻击.

下面我们来看看hashmap的源码

构造函数

有四种重载，但是我们只挑下面一种重载细说

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

​ 源码1

可以看到，上面就是对HashMap的initialCapacity、loadFactor以及threshold 三个属性进行了设置. 要求initialCapacity介于0和0x40000000(十进制的10亿多)之间. 有趣的是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;
    }

​ 源码2

源码2中的注释写的很清楚了——tableSizeFor方法返回的是>=入参cap的最小2的整幂次. 例如cap=3, 则tableSizeFor返回的就是 2^2=4（因为4是>=3的最小二次幂）, 如果入参cap=4, 则tableSizeFor返回的也是4. 因为2^2>=4. 那这个算法为什么正确呢? 其实只需要证明最后的n一定最高位以下全部是1的值+1. 例如3=11（2进制），则 源码2的第10行的n就是11. 又如 6=110， 则源码2的第十行的n是111, 为什么呢? 反证法，如果n的某位不是1，而是0的话，则沿着源码2第10行逆推回去的话，n的全部位都应该是0，即n=0， cap为-1. 但是这与源码1中的入参initialCapacity的范围是相佐的. 所以得证. 因此我们知道，你使用HashMap的构造函数初始化的并不是真正存放Map.Entry的数组，即源码中的table属性（回忆HashMap本质上就是一个数组实现的哈希表, 而数组元素的类型就是 Map.Entry. 再多说一句，其实是Map.Entry的实现类——HashMap.Node），而是一些初始的参数. 其中

initialCapacity 需要控制在[0, 0x40000000]
loadFactor 自定义，loadFactor属性=Map.Entry总数/数组长度. loadFactor越大，表明哈希表越满. 则发生哈希碰撞的概率越大. 注意，loadFactor可以>1
threshold 是>=initialCapacity的最小的2的整数次幂，这个是阈值, 在后面的扩容处理中会细讲

另2种HashMap构造器的重载如下

public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

查找

我们最常用的查找方法.

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

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {   // 哈希1
            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)
                    // 就调用红黑树的查找算法（本质就是BST查找，详见【2】）
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do { // 链表搜索
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 哈希2, 这里就表明HashMap允许key为null
    }

​ 源码3

其中值得注意的是两个hash的算法(即上面的哈希1和哈希2). 其中哈希1是通过取余的方式计算要插入的元素在table中的位置. 因为n是table的长度，是2的整数次幂（后面扩容处理中会讲）. n-1就是全部是1的二进制表示, &运算就可以截取hash与n二进制等长的比特字节. 不就相当于是模掉n的结果么? 这种做法显然更高（zhuang）效（bi）. 至于哈希2，其本质就是拿一个32为整型的高16比特位与低16比特位进行与运算. 这样做的好处是充分利用到入参key.hashcode的全部比特位, 不然的话, 如果仅仅就使用key.hashcode作为hash值入参getNode方法的话, 则(n-1)&hash 的重复度就非常高了. 即哈希碰撞（所谓哈希碰撞指的是hash值一样但是equals不一样的元素插入HashMap）就非常严重（尤其是如果程序员覆写的hashCode方法设计不佳的话）. 所以才要使用哈希2处的算法来计算一个key的哈希值而不是简单使用native方法的hashCode返回值作为key的哈希值.

至于搜索的具体代码，上面注释的很明白了. 我们唯一要讲解的是上面红黑树的搜索. 我们来到TreeNode的源码

final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

​ 源码4

第一段代码是很显然的——如果当前TreeNode的parent不为null, 亦即当前节点不是根节点，则先找到根节点（通过root方法（本质就是不断通过parent指针寻根）），然后从红黑树的根节点进行搜索(即上面的find方法). 剩下的使用的基本就是BST搜索的那套了. 参见【5】. 其中值得注意的是先通过hash值判断往二叉树的左走还是右走. 如果hash值相等的话，再判断key是不是相等（==或者equals），如果满足相等的话，则返回节点本身（第15行代码）.如果key不相等（即==和equals都不成立）. 再判断 pl和pr是否为空. 如果一方为空，则往另一方走. 如果两方都不为空的话，则计算dir值

(kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0

kc是获取k（即key）的Class, 如果k实现了Comparable接口的话，返回k的Class, 否则返回null. 其中源码如下

static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                for (int i = 0; i < ts.length; ++i) {
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    /**
     * Returns k.compareTo(x) if x matches kc (k's screened comparable
     * class), else 0.
     */
    @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

理解上面的源码需要一丢丢反射的知识(尤其是参数化泛型类如何获取泛型参数类型). 读者可以移步去查阅相应的的泛型知识. 这里就不详细展开了.

这里有必要说一句，其实我阅读这部分源码的时候就觉得怪怪的. 因为一个顺畅的bst查找不应该写的如源码4那样写的”丑”. 后来才知道，其实HashMap设计之初并没有考虑到会以红黑树来优化链表过长导致的DOS攻击问题. 而BST的前提就是全序（即树节点实现Comparable接口）. 所以上面的源码4才会在第24-27行无奈的到右子树上搜索一番，如果没有搜到的话，就跑到左子树上去搜索，这无疑降低了红黑树查询的效率，所以JDK8 的HashMap的API上推荐插入的元素实现了Comparable接口.

ps: 看到这里，其实我内心也挺奔溃的——它的查询最坏也是O(n), 我估计是当时HashMap设计者没考虑到Hash 碰撞的DOS攻击这个玩意，更没想到用红黑树优化这个问题，所以没强制让哈希数组的元素实现Comparable的接口。所以简单的二叉树查询会被写的这么丑~~ 而且如果没实现Comparable接口的话（虽然目前情况不多，而且JDK8 api推荐我们使用HashMap的泛型参数要实现Comparable接口），完全可能蜕化最坏成O（n）的境地~ 我估计JDK的作者看不下去了，所以有了TreeMap（还没看源码，只是猜测）~

遍历

我们熟知的HashMap遍历代码如下

for(Object key : map.keySet()) {
    // do something
}

或者

for(HashMap.Entry entry : map.entrySet()) {
    // do something
}

而与 C# 类似，java对于实现了Iterable接口的类进行foreach遍历提出的也是迭代器模式进行遍历. 所以都会被javac编译为

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

因此，我们考察HashMap的算法——到底HashMap是按照什么顺序进行遍历的呢? 注意，稍微跟一下源码就知道下面的讨论对于两种遍历HashMap的代码都是有效的.

不难知道HashMap的keySet方法返回的是一个KeyIterator，它是HashIterator的子类. 而我们最关心的是它的next方法.

 HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] 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);
            }
        }

final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> 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;
        }

​ 源码6

不难知道nextNode方法中的next就是table上的不为null的第一个数组元素（注意，不是链表上或者红黑树上的）.如果modCount和expectedModCount不相等的话，就快速失败. 注意，HashMap等非线程安全集合一般都要这个快速失败机制（具体参见【6】）.

如果e为null的话，表示整个HashMap都是空的. 所以抛出NoSuchElementException异常. (注意，并不意味着遍历空的HashMap会抛NoSuchElementException异常, 因为还有一个hasNext方法判断呢!) 最后我们关注第18行代码，nex通过next指针变成了下一个, 如果是null的话, 就沿着table数组继续遍历. 否则的话就沿着next指针进行遍历. 所以HashMap的遍历顺序应该类似于下面的样子

这就是为什么HashMap遍历的顺序和HashMap插入的顺序一般不一致的原因.

扩容

只要底层使用数组实现的集合，都存在扩容问题.

在【1】中我们指出哈希表性能陡降的时候就是扩容的时候——因为需要重哈希. HashMap虽然使用红黑树解决了碰撞频繁导致查询效率O(n)的问题，但是扩容再哈希的问题依旧存在. 我们看看HashMap的扩容方法的源码

final Node<K,V>[] resize() {
    // 1. 计算新桶数组的容量 newCap 和新阈值 newThr
        Node<K,V>[] 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;
            }
            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
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
    // 2. 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
    // 3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。
        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 { // 拆解链表
                        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) { // 对应 35 和 19
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { // 对应 27 和 43
                                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;
    }

​ 源码5

虽然源码有点小长，但是大体分成上述3个部分.

1. 我们关键要搞清楚，什么情况下会进入其中的if代码块. 能进入第七行代码块的，一定是曾经扩容过的. 因为oldCap只在第四行赋过值，大于0表示oldTab=table不为空. 并且在当前数组长度>=0x40000000(十进制的1073741824)的时候，不再扩容了. 否则，在扩容后不会超出1073741824 的前提下newThr(新阈值)进行扩容.

   进入第16行if代码块的情况是oldCap=0 但是oldThr>0 的情况就是调用构造函数源码1的时候. 因为oldThr初始化为threshold（它是受源码2初始化过的，初始化的结果就是2的幂次）.则newCap=oldThr，即newCap是2的次幂. 而newThr是0.

   能进入18行代码块的情况是oldCap和oldThr=threshold 都是0的情况，即调用的是无参构造函数的情况.,此时newCap初始化为16，newThr初始化为16*0.75=12, 所以我们知道调用HashMap的无参构造器得到的底层table数组是一个长为16 的数组. 并且阈值是12（一旦插入的键值对数目超过了12，就要resize扩容）

   进入22行的if代码块的，要么是调用源码1构造函数, 要么就是【3】中提及的newThr右移过度了归零了.

2. 就一行代码，唯一值得说的事情是，这一行代码保证了数组table的长度恒为2的正整数幂.

3. 就是处理扩容的再哈希问题. 首先明白为什么要再哈希? 举个例子

   

上图是原先table中的情况(可能有一些其他的元素没画). 原先容量是8. 35&7 = 27 & 7 = 19&7 = 43 & 7 = 3（所以在丢在一个链表中）.现在要将其扩容为16. 则

35 & 15 = 27 & 15 = 19 & 15 = 43 & 15 还成立吗? 显然，如果依旧成立的话，我们完全可以依旧放在一个哈希位置上. 否则就要拆解这个链表. 其实 n&15 之间等不等不就是看n之间的低4个比特位是否一致嘛~ 现在已经知道低3个比特位一致了. 所以我们只需要知道第四个比特位是否一致即可. 怎么知道第4个比特位是否一致? 不就是看

35 & 8=27 & 8=19 & 8=43 & 8 是否成立嘛~ 其中8不就是扩容前的长度么? 显然

35&8=19&8=0

27&8=43&8=1

所以扩容后35和19继续在原先的链表中，而27和43要移动到哪里去呢? 移动到3+8=11的位置上去. 因为与运算结果是1嘛~ 即结果如下

至于源码中的loHead、loTail、hiHead、hiTail的作用就是控制这两根链表的插入行为（尾插法，其实就是维护两根新的链表，遍历老的链表，根据与运算结果，将节点接到新链表上去，最后将新链表装到table数组上去）

有了上面的图示，不难理解拆解链表的算法部分. 下面讲解拆解红黑树部分，即源码5的第41行. 红黑树需要拆解和链表需要拆解的原因是一样的， 都是再哈希. 源码如下（split方法只在resize扩容中被调用）

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this; // b是头结点,是数组table上的节点
            // Relink into lo and hi lists, preserving order
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            int lc = 0, hc = 0;
            for (TreeNode<K,V> e = b, next; e != null; e = next) {
                next = (TreeNode<K,V>)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) // UNTREEIFY_THRESHOLD=6
                    tab[index] = loHead.untreeify(map); // 拆解后的红黑树过短, 需要链化
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        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);
                }
            }
        }

​ 源码7

从源码7可以看出，算法和源码5基本是一致的. 注意，源码7中的b是数组table上的元素，是红黑树的根节点（插入算法保证的，后面会细讲）, 从根节点开始通过next指针遍历红黑树. 注意，插入算法能保证从根节点开始沿着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;
    ...

​ 源码8

可见，红黑树节点是Table数组元素类型的子类, 这是显然的，因为红黑树除了必须要是数组元素之外还必须对外提供二叉树操作的接口. 所以必须要有相应的数据结构做支撑的. 这里红黑树相应的数据结构就是 parent（指向父节点的指针）、left（左孩子指针）、right（右孩子指针）、red（是否是红色节点）. 而从HashMap.Node继承来的next指针和prev指针（prev指针和next指针会在链表树化的时候进行维护，后面会讲）是用于遍历红黑树的（next、prev从某种角度来讲，是记录了原先树化前链表的顺序，而不是采用bst的前中后序遍历红黑树）. 也就是说红黑树节点有两套系统，一套是 parent、left、right，另一套是 next、prev. 前者用于红黑树的查询等接口（JDK8引入红黑树优化过长链表就是基于这个目的），后者用于红黑树遍历.

既然有了这套next指针，算法就和上面的拆解链表是几乎一样的了. 唯一不同的地方在于，如果拆解完毕之后的子树如果长度过短的话（<=6），则就需要红黑树链化. 否则，就重新树化（因为如果不重新树化缩小红黑树的大小，会影响查询效率的）.

下面看看链化的源码

final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null); // 将TreeNode转换为Node，注意，这种转换是必要的，因为后面很多删除、查找都是根据table上的元素的类型是不是TreeNode采用红黑树算法还是链表算法, 所以切不可以因为TreeNode是Node的子类就可以不换而仅仅根据next装配链表完事儿
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

​ 源码9

其实链化很简单，因为我们知道，当前红黑树的状态是next指针在源码7的前半段在维护. 所以只需要从当前节点（即源码9中的this）出发沿着next指针一路走到null然后尾插法装配起来即可.

再来看看树化的源码

/**
         * Forms tree of the nodes linked from this node.
         */
        final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                x.left = x.right = null;
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

 /**
         * Ensures that the given root is the first node of its bin.
         */
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash; // 找到根节点所在红黑树的应该长在哪个table数组元素上，index就是这个元素的索引. 我们称这个元素为红黑树中的"遍历首位"
                TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; // 拿到遍历首位元素
                if (root != first) { // 如果红黑树根节点不是遍历首位
                    Node<K,V> rn;
                    tab[index] = root; // 遍历首位更新为红黑树的根节点
                    TreeNode<K,V> rp = root.prev; // 维护原先链表中的next、prev指针
                    if ((rn = root.next) != null)
                        ((TreeNode<K,V>)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null) // 注意，将原先遍历首位作为了红黑树根节点的后继.
                        first.prev = root;
                    root.next = first;
                    root.prev = null; // 遍历首位（已经变更为了红黑树根节点）的prev自然是null
                }
                assert checkInvariants(root); // 递归断言依旧是一棵红黑树
            }
        }

/**
         * Recursive invariant check
         */
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }

​ 源码10

源码10展示了3个API. 其中第一个就是树化，第二个是树化工作完毕之后要将新的根节点（链表的头结点未必是树化之后红黑树结点）移动到table数组上去(即链表的头结点. 当然，需要进一步维护next指针和prev指针，因为查询的时候能从table数组第一个触及的元素变了.). 第三个是递归断言整个红黑树的定义依旧符合（红黑树详细参见【2】）.

先来看第一个. 树化的思想其实很简单, 就是重新插入一遍（从当前节点出发沿着维护好的next指针一路插入红黑树，而插入的本质就是调整，也就是源码10中的balanceInsertion.） 调整的算法参见【2】（良心推荐【2】，关于红黑树的算法不仅有大量生动化的注释还有恰到好处的图示）. JDK实现红黑树和【2】实现红黑树的本质都是一样的（都参考了算法导论）.

值得注意的事情是和查询的时候（既源码4）往左走还是往右走不同的决定算法不同. 这里使用了tieBreakOrder方法. (tie-break是网球术语，代表抢七. 即最终决战) 即最终如何决定往左插还是往右插呢? 因为和查找不同，查找是为了找到，所以往右查询没查到的话，就要往左查询咯（查询一个方向都不能落下, 而插入的话，只需要选择一个方向进行插入即可） . tieBreakOrder 的源码如下:

static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

用到了identityHashCode这个api. 该API和Object的hashCode方法（都是native的）的不同在于后者可以被覆写. 而前者返回的就是根据内存映射地址计算的hash值（举个例子就是String a1 = new String(“a”)和String a2 = new String(“a”)的hashCode值一样，但是identityHashCode不一样）. 同查询，也是HashMap的作者伊始没有考虑到会有一天使用红黑树进行优化，所以没有强制要求树节点实现Comparable接口.

插入

插入的源码见下

public V put(K key, V value) {
    // false表示可能会改变原本HashMap中的值, 举个例子就是map原先有 "a"=1, "b"=2, 如果此时你再put("a",3)的话，这里是false，则就会变成 "a"=3, 否则key一样就不改变原先的value.
    // true 的意义在HashMap中用不到，对于LinkedHashMap有用, 所以此文不必关注
        return putVal(hash(key), key, value, false, true); 
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; // 特别的，首次插入空的HashMap, 则先扩容
        if ((p = tab[i = (n - 1) & hash]) == null) // 如果待插入的位置是空的话, 则表明没有出现hash碰撞，直接插入就好了
            tab[i] = newNode(hash, key, value, null);
        else { // 出现了碰撞
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) // 如果key的哈希值相等并且equals方法相等，则在HashMap中被视为同一个元素, 则就要修改（或者说覆盖HashMap中原本元素的value）
                e = p;
            else if (p instanceof TreeNode) // 如果不满足，就要该插红黑树插红黑树，该插链表插链表来解决碰撞，这里是插红黑树，如果原先没有这个key的话，e可能最终是null
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { // 这里是插链表，如果原先没有这个key的话，e可能最终是null
                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 如果插入的元素达到了树化的阈值8,就要树化.
                            treeifyBin(tab, hash);
                        break;
                    } // 否则继续遍历链表直至找到应该插入的位置（这里采用的是尾插法）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key, 如果 onlyIfAbsent为false，即支持覆盖的话，就覆盖, 并且返回之前被覆盖掉的value.
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); // LinkedHashMap才会用,LinkedHashMap会覆写此方法
                return oldValue; // 如果覆盖了既有元素的话，则返回之前被覆盖掉的元素
            }
        }
        ++modCount;
        if (++size > threshold) // 如果新增之后超过阈值，则扩容HashMap
            resize();
        afterNodeInsertion(evict);  // LinkedHashMap才会用
        return null; // 如果没有覆盖既有key的话，返回null
    }

/**
         * Tree version of putVal. 即树版的putVal
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null; // 这个kc在源码4中出现过，一样的作用
            boolean searched = false; // 是否找到, 伊始是没找到
            TreeNode<K,V> root = (parent != null) ? root() : this; // 如果p不是根节点的话，就先找到其所在红黑树的根节点(就上面的putVal方法而言，不会出现这种情况，但是这样写是为了代码更加健壮)
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk))) // key的哈希值与equals都相等，则直接返回（因为找到了）
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) { // 如果key压根没实现Comparable接口或者实现了，但是Comparable比较的结果是0, 则不晓得到底往左走还是往右走，就只能左边也走，右边也走. 这无疑降低了红黑树的插入效率
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true; // 反正这个变量后面也没用，赋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;
                    }
                    dir = tieBreakOrder(k, pk); // 使用identityHashCode进行比较
                }
				// 如果代码走到这里，说明没找到（即原先红黑树中不存在key这个键）,则要插入
                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) { // dir要么是1要么是-1，不可能是0, 因为最终还有78行代码把关
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);// 构造新的待插入红黑树节点
                    if (dir <= 0) // 维护红黑树作为二叉树的父子关系
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x; // 维护作为链表的next、prev指针
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x)); // 调整红黑树, 注意，这里将根节点移动至链表首位（即table数组元素）以及调整红黑树二合一了. 因为table数组元素才是遍历算法最先触碰到的元素. 所以要这么干
                    return null;
                }
            }
        }

/**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) { // 链表树化的方法
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // table数组的长度<64的情况下，优先考虑是扩容，而不是树化. 因为哈希碰撞的主因是table太小, 而不是哈希函数设计的不合理
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) { // 找到链表头结点
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null); // 因为链表上的节点全部是HashMap.Node类型的，所以要先转换为HashMap.TreeNode
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null); // 整个过程其实就是把原先链表上的节点由Node类型改成TreeNode类型
            if ((tab[index] = hd) != null) // 最后树化TreeNode链表即可
                hd.treeify(tab);
        }
    }

​ 源码11

源码的关键点都写了注释. 但是还想说明3点.

1. modCount的变更只有在hashmap的键值对数量变化（新增或删除键值对）的时候才会+1. 对于覆盖既有键值的操作是不会导致modCount变更的. 所以我们可以在迭代器迭代HashMap的时候修改相应value值，但是不可以在迭代器迭代的时候新增或删除元素. 具体原因见【6】

2. 因为putTreeVal的最后调整了红黑树之后，将新的根节点通过改变prev、next指针移动到了table上. 所以可能前后两次遍历第一次触碰到的table上的元素(即哈希槽位上的首个元素)是不同的.

3. 为什么是8? 也就是为什么链表插入长度>=8的话就要树化? 这是一个概率论问题. 因为理想状态下哈希表的每个箱子（即源码中的bin）中，元素的数量遵守泊松分布 .而负载因子默认为0.75 的时候，Poisson定理中的 λ 是0.5， 则我们可以计算出箱子中元素个数和概率的关系如下

   | 数量 | 概率 |
   | :–: | :——–: |
   | 0 | 0.60653066 |
   | 1 | 0.30326533 |
   | 2 | 0.07581633 |
   | 3 | 0.01263606 |
   | 4 | 0.00157952 |
   | 5 | 0.00015795 |
   | 6 | 0.00001316 |
   | 7 | 0.00000094 |
   | 8 | 0.00000006 |

   这就是为什么箱子中链表长度超过 8 以后要变成红黑树，因为在正常情况下出现这种现象的几率小到忽略不计。一旦出现，几乎以100%置信度认定是哈希函数设计有问题导致的。

   Java 对哈希表的设计一定程度上避免了不恰当的哈希函数导致的性能问题，每一个箱子中的链表可以与红黑树切换

删除

删除的源码如下

public V remove(Object key) {
        Node<K,V> e;
    // null 表示value的值，因为删除只是针对key删除——不论你value是什么，所以写null即可
    // false 表示根据键删除（如果写true的话，还必要value匹配才能删除）
    // true表示删除之后要调整根节点至table数组上（我们显然需要这样）
    // 返回删除的value（如果没有此key，则返回null）
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) { // 找到红黑树的根节点或者链表的头结点
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) // 如果table上的相应位置恰好就是要删除的元素，则找到了
                node = p;
            else if ((e = p.next) != null) { // 如果这个table处的元素处理过哈希碰撞（即存在红黑树或者链表），则跑到红黑树或者链表上去找此元素
                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) // 如果不是红黑树，是链表，并且此节点就在table上，则简单替换为链表下一个节点为table上元素即可
                    tab[index] = node.next; // 是链表，而且待删除节点不在table上.则使用链表操作简单删除即可
                else
                    p.next = node.next;
                ++modCount; // 作用在插入的时候说了，就是为了快速失败机制
                --size;
                afterNodeRemoval(node); // 给LinkedHashMap用的,HashMap用不到，LinkedHashMap会覆写该方法
                return node;
            }
        }
        return null;
    }

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash; // 找到要移除元素所在table的槽位的索引
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; // first就是红黑树根节点
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; // 当前节点的前驱和后继
            if (pred == null) // 前驱为空，即要删除的节点就是根节点，则要调整table[index]了
                tab[index] = first = succ;
            else
                pred.next = succ; // 删除的是普通红黑树节点
            if (succ != null)
                succ.prev = pred; // 重新维护next、prev
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null
                || (movable
                    && (root.right == null
                        || (rl = root.left) == null
                        || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small，在这种情况下，红黑树的大小<=7, 则红黑树要链化
                return;
            } 
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) { // 开始找被删除节点的后继（因为要用后继来顶替被删除的元素）
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
			// 以上是找后继（即顶替者）
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); // 调整红黑树

            if (replacement == p) {  // detach
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r); // 和插入时是一样的
        }

具体的红黑树删除操作可以参见【2】

值得注意的问题

阅读源码的过程中值得注意的是

被 transient 所修饰 table 变量

这个问题在ArrayList源码中也同样存在. ArrayList的属性elementData也是transient的. 即不参与序列化与反序列化的.

其实对于带扩容机制的容器中，底层容器（数组）都是transient. 原因是

底层容器因为扩容机制的存在， 多数情况下是无法被存满的，序列化未使用的部分，浪费空间.

为此，HashMap和ArrayList底层都写了private的readObject和writeObject方法——去序列化”真正有内容”的数组节点.

这是我以前的认知，但是在【3】中，作者提及了另一个原因.

同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。

解释如下

“HashMap 的get/put/remove等方法第一步就是根据 hash 值（参见源码3）找到键所在的桶（bucket）位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 值可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash值，此时再对在同一个 table 继续操作，就会出现问题。”

一言以蔽之，就是别的JVM不晓得怎么根据你的hash值还原序列化过来的字节内容.

参考

【1】https://yfsyfs.github.io/2019/06/07/%E5%93%88%E5%B8%8C%E8%A1%A8/

【2】https://yfsyfs.github.io/2019/05/31/%E7%BA%A2%E9%BB%91%E6%A0%91/

【3】https://segmentfault.com/a/1190000012926722

【4】https://www.cnblogs.com/zhangminghui/p/4210800.html

【5】https://yfsyfs.github.io/2019/05/28/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91-BST/

【6】https://yfsyfs.github.io/2019/06/11/HashMap-%E7%AD%89%E9%9B%86%E5%90%88%E4%B8%AD%E7%9A%84%E5%BF%AB%E9%80%9F%E5%A4%B1%E8%B4%A5%E6%9C%BA%E5%88%B6%EF%BC%88fast-fail%EF%BC%89/