Java8 HashMap源码阅读

概述

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap 是一个使用数组与链表（红黑树）实现的键值对集合，继承自抽象类 AbstractMap，实现了 Map 、Cloneable、Serializable 接口。

HashMap 是非线程安全的，key 与 value 允许 null 值（key的 null 只允许有一个，value无限制），遍历顺序和插入顺序不保证不一致。

几个重要参数

• DEFAULT_INITIAL_CAPACITY：默认容量，为 2 的 4 次方（16）
• loadFacotr：负载因子，默认为 0.75，如果实际 entry 数量超过了 capacity与loadFacotr 的乘积，将会进行resize
• MAXIMUM_CAPACITY：最大容量，默认为 2 的 30 次方
• TREEIFY_THRESHOLD：树化阈值，默认为 8，当 Bins内 的 Node 超过该数值，会将链表转成红黑树
• UNTREEIFY_THRESHOLD：链表化阈值，默认为 6，当 Bins 内的 Node 小于该数值，会将红黑树转成链表转成
• MIN_TREEIFY_CAPACITY：链表转树的最小容量,，默认为 64，只有容量超过该值才能进行树化。这个值至少是 4 * TREEIFY_THRESHOLD， treeifyBin() 方法中会先判断容量，如果小于 64 会直接 reszie 而不是 树化。

HashMap 是如何计算 hashCode 的

真正的 hash 值是将 key.hashCode 右移 16 位，然后与原来的 key.hashCode 做异或计算得到的，即对原来的 hashCode 做一个扰动的处理。

实际上就是将原始 hashCode 的高 16 位和低 16 位进行异或，这样就混合了原始 hashCode 的高位和低位，加大了低位的随机性，而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来，这就使得 hash 方法返回的值，具有更高的随机性，减少了冲突的可能性。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

此外，Node 内部类中的 hashCode 是由 key 的 hashCode 和 value 的 hashCode 异或得到的。

public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

负载因子的大小

一般来说，默认的load factor (0.75) 在时间和空间成本上提供了很好的权衡。

load factor 越小，HashMap 所能容纳的键值对数量变少，哈希碰撞也会减少，但空间利用率低。

load factor 越大（可以大于1），HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞率也高，也提高了查找成本。

为什么 HashMap 容量为 2 的幂

当容量为 2 的 n 次幂的时候，在 put 的时候不同的 key 算出的 index 相同的几率较小，分布较均匀，不容易发生碰撞。

从 put 策略中的计算 index 方式可以看出实际是对 length-1 与 hash(key) 做与运算，2^n 转换成二进制就是1+n个0，减1之后就是0+n个1，如16 -> 10000，15 -> 01111。

根据与运算的规则，都为1(真)时，才为1，因为2^n-1都是11111结尾的，所以碰撞几率小。

且当容量一定是2^n时，h & (length - 1) == h % length，位运算可以提高效率。

HashMap 的 Put 策略

注意，HashMap 在真正第一次 put 的时候才会进行初始化。

1. 判断当前数组是否需要初始化
2. 根据 key 的 HashCode 计算放置桶的 index

3. • 判断是否空桶 or 是否发生 Hash 碰撞

   • 解决 Has h碰撞：根据桶是红黑树还是链表进行对应的插入操作

4. 如果是链表形式，完成插入后，检查是否超过树化阈值，超过将链表转为红黑树
5. 如果节点已经存在就替换 old value
6. 最后检查实际元素个数是否超过 capacity 与 loadFacotr 的乘积，超过进行 resize

HashMap 中计算 index 的方式为index = (容量 - 1) & hash(key)，即：

p = tab[i = (n - 1) & hash])

• 计算 key 的 HashCode
• 和数组的容量减 1 做一次 “与” 运算（&）

HashMap 的 Get 策略

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

1. 根据 key 的 HashCode 找到对应桶的 index (index = (容量 - 1) & hash(key))
2. 判断是否为链表，不是链表，判断 hashCode 是否相等且用 == 判断 key 是否相等，或者直接判断 key.equals(k)
3. 判断是否为红黑树，是红黑树调用 getTreeNode() 方法
4. 不是红黑树，遍历链表寻找节点，判断 hashCode 是否相等且用 == 判断 key 是否相等，或者直接判断 key.equals(k)

HashMap 的 Remove 策略

1. 根据 key 的 HashCode 找到对应桶的 index，这一步和 get 中找 index 的方式是一样的
2. 如果是 TreeNode，调用红黑树的getTreeNode()删除节点
3. 否则， 遍历链表，判断 hashCode 是否相等且用 == 判断 key 是否相等，或者直接判断 key.equals(k)
4. 找到则删除

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))

PS：其实第二句 (k = e.key) == key ||(key != null && key.equals(k) 等价于key.equals(k)，多出的 (k = e.key) == key 可以减少后面调用 equals()，提高效率。

HashMap 的扩容 (reszie) 策略

源码注释中已明确指出：resize 后元素下标要么不变，要么增加 2 的幂

1. 计算新桶数组的容量 newCap 和新阈值 newThr
2. 检查当前容量已超过MAXIMUM_CAPACITY()，超过则将容量设为 Integer.MAX_VALUE（2的31次方-1），不进行扩容
3. 根据新的容量初始化一个 newTab
4. 如果节点是 TreeNode 类型，则需要拆分红黑树
5. 如果是链表，则先遍历 oldTab 中的元素，计算该元素 e 的 e.hash & oldCap 是否等于 0
6. 等于0，放入原来的index，否则放入 index + oldCap(原有容量)

可以看出 resiez 是个成本很高的操作，所以在存储大量数据的时候，最好预先指定 HashMap 的 size ，而且保证0.75size > 数据量。

PS：在 JDK1.7 中如果在新表的数组索引位置相同，则链表元素会倒置。

HashMap 如何解决哈希碰撞（冲突）

常见的哈希碰撞解决方法：

1. 开放地址法（可以占用本来应该其他数据占用的地址）：
   • 线性探测再散列：冲突发生时，找到下个为空的位置存放。
   • 二次探测再散列：冲突发生时，在表的左右进行跳跃探测。
   • 随机探测再散列：产生一个随机数序列，将此随机数序列作为依次探测的步长。
2. 链地址法：所有哈希值相同的元素构成一个称为同义词链的单链表，HashMap 采用的是这种方法。
3. 再哈希法：同时构造多个不同的哈希函数，如果出现哈希值相同的元素，用其他哈希函数再做一次哈希。
4. 建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

HashMap 的具体解决办法：
当 HashMap 出现哈希碰撞时，它会首先检查新键和当前检索到的键之间是否可以比较（也就是实现Comparable接口）。
如果不能比较，它就会通过调用 tieBreakOrder(Object a,Object b) 方法来对它们进行比较。
这个方法首先会比较两个键对象的类名，如果相等再调用 System.identityHashCode方法（比较内存地址）进行比较。

HashMap 并发下的死循环与元素丢失

JDK1.7 中的 HashMap 在并发的情况下，resize 时可能会产生环形链表（新的链表采用头插法，为逆序插入），在执行 get 的时候，会触发死循环。

但 JDK1.8 中新数组中的链表顺序依然与旧数组中的链表顺序保持一致，但仍有可能发生元素丢失等问题。

HashMap 自己实现 writeObject 和 readObject 方法的原因

1. HashMap 多数情况都不是满的，序列化未使用的部分，浪费空间。

2. HashMap 依靠 HashCode 来存放 Entry，而在不同的 JVM 实现中计算得出的 HashCode 可能是不同的，这样会导致 HashMap 的反序列化结果与序列化之前的结果不一致。

第 2 点在《Effective Java》中有提到:

The bucket that an entry resides in is a function of the hash code of its key, which is not, in general, guaranteed to be the same from JVM implementation to JVM implementation. In fact, it isn’t even guaranteed to be the same from run to run. Therefore, accepting the default serialized form for a hash table would constitute a serious bug. Serializing and deserializing the hash table could yield an object whose invariants were seriously corrupt.

那么，HashMap 又是如何保证序列化和反序列化数据的一致性的?

1. 首先，将底层的 table 数组用 transient 修饰，保证不被自动序列化。

2. 然后序列化的时候并不会将数组直接序列化，而是将 size 以及每个 k-v 对都进行序列化。
   在反序列化的时候，重新计算 k-v 对的位置，重新填充一个数组。

采用自定义对象作为 HashMap 的key 时的注意事项

1. 要注意这个对象是否为可变对象，否则可能导致存入Map中的数据无法取出，造成内存泄漏。
2. 要重写 hashCode() 方法和 equals() 方法。

红黑树的特点

1. 每个节点非红即黑
2. 根节点总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的，反之不一定
4. 每个叶子节点都是黑色的空节点(NIL节点)
5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点，即相同的黑色高度

源码阅读

package java.util;

import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;

/**
 * HashMap实现了Map接口，允许key与value为null。HashMap与HashSet大致等同，除了HashMap是线程不安全、允许null值的。这个实现类不保证映射的顺序，尤其是随着时间变化不保证映射的顺序不发生变化（即不能保证key的顺序不变）。
 * 
 * HashMap提供了常数级时间复杂度(O(1))的基本操作(get与put)，如果Hash函数将元素都适当地放在各个桶里的话。遍历HashMap的时间复杂度与capacity(桶的数量)与桶的大小(键-值对的数量)有关。 
 * 
 * 如果对遍历有一定的性能要求，那么不能将initial capacity(初始化容量)设置太高或者load factor(负载因子)因子设置太低。 
 * 
 * HashMap实例有两个参数会影响其性能：初始化容量(initial capacity)和负载因子(load factor)。
 * Capacity即hash table中桶的数量，initial capacity就是hash table被创建时桶的数量。
 * 
 * Load factor是一个hash table多满时需要自动扩容的百分比比例，当hash table中的entry数量超过了capacity与load factor的乘积时，hash table会被rehash(即内部数据结构重建)，这样hash table就会有之前将近2倍的桶（扩容2倍）。
 * 
 * (load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.)
 * 
 * 一般来说，默认的load factor (0.75)在时间和空间成本上提供了很好的权衡。load factor越大减少了空间的开销，但提高了查找成本（表现在哈希表的大多数操作是get和put）。当我们设置初始化容量init capacity时应该考虑会有多少entry以及负载因子load factor，以减少rehash的可能。 
如果实际的entry数量，达不到capacity*load factor，那么rehash将不会发生。 
 * PS：load factor越大，说明要扩容时的容量越接近于满，空间利用率的确大了，但是此时更容易发生哈希碰撞。而HashMap是用单链表法解决哈希碰撞，单链表的查询性能是比hash慢许多的。
 * 
 * 如果有很多的键值对要存到HashMap实例中，创建一个足够大的容量的HashMap将会使得键值对的存储比让它根据需要自动做rehash以增长表更有效率。注意，使用具有相同hashCode的多个键会影响任何hashtable的性能。为了减少这种相同hashCode的碰撞，当keys支持java.lang.Comparable的时候，可以利用排序降低影响。
 * PS：当HashMap出现哈希碰撞时，它会首先检查新键和当前检索到的键之间是否可以比较（也就是实现Comparable接口）。如果不能比较，它就会通过调用tieBreakOrder(Object a,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名，如果相等再调用 System.identityHashCode方法（比较内存地址）进行比较。
 * 
 * 注意HashMap不是线程安全的，如果有多个线程并发访问HashMap，当其中的至少一个线程改变了HashMap结构时候，必须从外部做同步操作，比如可以通过对一些封装了map的object做synchronizing来实现同步。（这里的改变结构是指添加或删除了一个或多个mapping，仅改变已存在的mapping值不属于改变结构的范畴。）
 * 
 * 如果没有这样的object存在，map应该通过Collections.synchronizedMap方法来封装。最好是在创建时完成，以防止对map的意外的非线程安全访问。e.g. Map m = Collections.synchronizedMap(new HashMap(...));
 * 
 * HashMap的所有集合视图方法返回的迭代器的遵循fail-fast机制: 如果map在创建完迭代器之后的任何时机结构发生改变，除了通过迭代器自己的remove方法外，迭代器将会抛出ConcurrentModificationException。因为并发修改时，迭代器quickly and cleanly的失败,远比未来的某个不确定时间、不确定情况、不确定操作带来的风险要好。
 * 
 * 注意iterator自身的fail-fast是不能被保证的，换句话说，在并发的线程不安全的修改下，不可能做任何硬性的保证，只是尽最大努力抛出异常ConcurrentModificationException（有可能抛出也有可能不抛出，上一段指出了iterator自身的remove不会抛出）。因此编写依赖于此异常的程序的做法是错误的，iterator的fail-fast应该只用来检测bug。
 */
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    /*
     * Implementation notes.
     * 
     * 这个map通常作为一个由bins(buckets)组成的hash table，当bins数量很多时，会将bins转换成TreeNodes，结构类似于TreeMap。大多数方法都用的是普通的bins结构，但当node数量超过一定阈值（默认为8）时，会转变为TreeNode。TreeNodes(红黑树)的bins与普通的bins(链表)没有区别，除了在数据量大的时候红黑树可以更快地查找。但是，大多数情况下bins的数量不会很多，所以在table方法的内部源码上对bins的转换可能会滞后(checking for existence of tree bins may be delayed in the course of table methods)。

     * Tree bins主要是根据bin的hashCode来排序的，但是当两个元素是同一个实现了Comparable接口类的实例时，则会根据该对象的compareTo方法来排序。额外的转换成红黑树的复杂操作是值得的，在key有不同的hashCode或是可排序的情况下，最坏的时间复杂度是O(logn)。因此，在重写hashCode()不当(如返回分布不均的hashCode)的情况下，许多的key会共享一个hashCode，HashMap的性能会显著下降，只要key是Comparable的。（如果以上两者的情况都发生了，且不采取任何预防措施，HashMap的会花费额外两倍的时间与空间）
     *
     * 由于TreeNodes的size是普通nodes的大约两倍，所以我们只在bins包含足够多的nodes时才会使用红黑树(阈值是TREEIFY_THRESHOLD，默认为8）。当这个值变得足够小（默认为6）时（由于remove或resize）时，红黑树就会转换回链表。在使用分布均匀的hashCode时，tree bins很少会被用到。理想情况，在随机的haCode下，node在每个桶中出现的频率符合0.5的泊松分布（在默认的0.75负载因子条件下），但是由于调整的粒度，方差也会变大。忽略掉方差，大小为k的list的出现频率是：(exp(-0.5) * pow(0.5, k) / factorial(k))，第一个值是：
     *
     * 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
     * 后续: 小于千万分之一
     * 
     * PS：公式中的0.5是指假定元素为桶数量的一半，即某个元素在某个桶中的概率为0.5，以此可以算出一个桶内含有0-8个元素的概率，可以看出8个元素即之后在同个桶内的概率已经非常低了。换句话来说，要是某个桶需要转换为红黑树（即nodes超过默认的TREEIFY_THRESHOLD=8），说明是十分小概率的事件。
     * 
     * 一般红黑树的根节点是第一个加入的node，但是有的时候（目前这种情况只有在Iterator.remove后，根节点也许会是其他的node，但remove掉root后也可以重新分配root。(method TreeNode.root())
     * 
     * 所有的内部方法都接受一个hashCode作为参数（通常由一个public方法来提供），这样内部互相调用时就不需要每次都计算hashCode了。大多数内部方法还接受一个"tab"参数，通常是现在的table，但当resize或转换时可能是新表或旧表。
     * 
     * 当bin lists被树化、分割，或未被树化时，我们保持他们以相同的相对访问与遍历顺序，比如基于Node.Next，以更好地保持顺序，并稍微简化调用迭代器时的split和遍历操作。当在插入操作中使用比较器时，为了保持总体有序（或尽可能接近总体有序），我们使用identityHashCodes来进行比较。
     * 
     * 由于子类LinkedHashMap的存在在，在普通模式与树模式下的使用与转换变得有点复杂。有关插入、删除、访问时调用的钩子方法，参阅下文，这些钩子方法允许LinkedHashMap的内部独立于这些结构。
     */
     
    /**
     * 默认的初始容量，必须是2的幂
     * 1 << 4表示1左移4位，变成二进制10000，即十进制16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量为2的30次方，如果构造函数传入的值大于该数，那么替换成该数
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子，为0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 默认的树化阈值，为8，当桶内元素个数超过这个值会转换为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 默认的链表化阈值，为6，当桶内元素个数小于这个值会转换为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 链表转树的最小容量,，HashMap的容量必须大于64，桶才能进行树化
     * 这个值是少是4 * TREEIFY_THRESHOLD，以避免resize与treeification thresholds的冲突
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 基本的hash bin node，一个node对应一个key-value对
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        // hashCode，表示在哪个桶内
        final int hash;
        final K key;
        V value;
        // next用于链表结构
        Node<K,V> next;
        
        // 一个node由它的hashCode、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; }
        
        // 每个node的hashCode是由key的hashCode和value的hashCode异或得到的
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        // 设置新的value并返回旧value
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 判断两个HashMap是否相等
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            // 只有key和value都相等才会返回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;
        }
    }

    /* ---------------- Static utilities -------------- */

    /**
     * 真正的hash值是将key.hashCode右移16位，然后与原来的key.hashCode做异或计算得到的
     * 也就是自己的高16位和低16位进行异或，这样就混合了原始hashCode的高位和低位，加大了低位的随机性
     * 而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来
     * 这就使得hash方法返回的值，具有更高的随机性，减少了冲突
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 如果实现了Comparable接口，返回object x的实际类型，也就是Class<C>，否则返回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;
    }

    /**
     * 如果x实际类型是kc，则返回k.compareTo(x)，否则返回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));
    }

    /**
     * 返回一个比给定容量大的2的幂
     */
    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;
    }

    /* ---------------- Fields -------------- */

    /**
     * 可以看出HashMap的底层数据结构就是一个装着node的数组，且被transient修饰，无法被自动序列化
     * 当被分配空间时，HashMap的容量总是2的幂（但有的情况下也可能是0，比如不需要初始化的时候）
     */
    transient Node<K,V>[] table;

    /**
     * entrySet()缓存
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 实际的k-v对数量
     */
    transient int size;

    transient int modCount;

    /**
     * 下一次进行resize的容量大小 (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

    /**
     * 负载因子
     *
     * @serial
     */
    final float loadFactor;

    /* ---------------- Public operations -------------- */

    /**
     * 用指定的容量与负载因子初始化一个空的HashMap
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    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);
    }

    /**
     * 用指定的容量与默认的负载因子(0.75)初始化一个空的HashMap
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 用默认的容量(16)与负载因子(0.75)初始化一个空的HashMap
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 根据已有的Map m构造一个新的HashMap，负载因子为默认值0.75，初始容量和m的容量一致
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    /**
     * 存入Map m的所有元素，实现Map.putAll和构造函数
     *
     * @param m the map
     * @param evict false when initially constructing this map, else
     * true (relayed to method afterNodeInsertion).
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            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);
            }
        }
    }

    /**
     * 返回实际的k-v对数量
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    /**
     * 如果HashMap不含任何元素，返回true
     *
     * @return <tt>true</tt> if this map contains no key-value mappings
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回key对应的value，如果没有返回null
     * 但是返回null并不意味着Map内没有这个k-v对，也可能这个key和value都是null
     * 这种情况下可以使用containsKey来区分
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * 具体实现get方法
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab;
        Node<K,V> first, e;
        int n;
        K k;
        // first = tab[(n - 1) & hash]对应桶的first node
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                // 找到first node就直接返回
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 不是first node就继续往下找
            if ((e = first.next) != null) {
                // 如果是TreeNode(红黑树)
                if (first instanceof TreeNode)
                    // 调用getTreeNode()返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 不是TreeNode就继续遍历
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 如果包含指定key的k-v对，返回true
     *
     * @param   key   The key whose presence in this map is to be tested
     * @return <tt>true</tt> if this map contains a mapping for the specified
     * key.
     */
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

    /**
     * 放入一个指定的k-v对，如果key已存在，value会被覆盖
     * 如果key已存在，则返回旧的value，否则返回null
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * 具体实现put方法
     * 如果key已存在，则返回旧的value，否则返回null
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent 如果为true，不改变原有值
     * @param evict 如果为false，表示在初始化创建中
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab;
        Node<K,V> p;
        int n, i;
        // 初始化桶数组table，可以看出在真正第一次put的时候才会进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果key对应的桶不存在
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 创建一个新的node
            tab[i] = newNode(hash, key, value, null);
        // 如果key对应的桶存在(发生哈希碰撞/冲突)
        else {
            Node<K,V> e; K k;
            // 如果k-v对与first node相等
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                // 覆盖掉当前值
                e = p;
            // 如果是TreeNode
            else if (p instanceof TreeNode)
                // 调用红黑树的putTreeVal()方法进行插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 不是覆盖操作，插入一个普通链表节点
            else {
                // 对链表进行遍历，并统计链表长度
                for (int binCount = 0; ; ++binCount) {
                    // 链表所有节点都不为空
                    if ((e = p.next) == null) {
                        // 在尾部创建一个新的node
                        p.next = newNode(hash, key, value, null);
                        // 如果链表长度达到了树化阈值8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果当前链表包含要插入的k-v对，终止遍历
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // key已存在，更新value并返回旧的value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 这是一个空的方法，用于LinkedHashMap重写使用
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // HashMap结构发生改变
        ++modCount;
        // size++并判断是否需要扩容
        if (++size > threshold)
            resize();
        // 这是一个空的方法，用于LinkedHashMap重写使用
        afterNodeInsertion(evict);
        // put成功，返回null
        return null;
    }

    /**
     * 初始化或扩容两倍
     * 如果为空（即初始化），则按照默认容量初始化HashMap
     * 如果是扩容，由于使用的容量是2的幂，resize后元素下标要么不变，要么增加2的幂
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        // 扩容前的map
        Node<K,V>[] oldTab = table;
        // 扩容前容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 扩容前的阈值
        int oldThr = threshold;
        // 扩容后容量和扩容后阈值，默认为0
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 如果当前容量已经到达上限MAXIMUM_CAPACITY
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 设置阈值为2的31次方-1
                threshold = Integer.MAX_VALUE;
                // 不进行扩容
                return oldTab;
            }
            // 按扩容前容量和阈值的2倍计算新容量和阈值的大小
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        // 如果当前表是空的，但是有阈值，代表是初始化时指定了容量、阈值的情况
        // 初始化时，将threshold的值赋值给newCap，这里是用threshold暂时替换initialCapacity
        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);
        }
        // 如果新的阈值是0，对应的是当前表是空的，但是有阈值的情况
        if (newThr == 0) {
            // 求出新的阈值
            float ft = (float)newCap * loadFactor;
            // 根据容量和负载因子是否已经越界来设置新边界
            // 越界则设置阈值为2的31次方-1
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // //更新阈值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 根据新的容量 构建新的HashMap
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 更新引用
        table = newTab;
        // 如果扩容前的HashMap内含有元素
        if (oldTab != null) {
            // 开始遍历
            for (int j = 0; j < oldCap; ++j) {
                // 取出k-v对
                Node<K,V> e;
                // 如果当前k-v对不为null
                if ((e = oldTab[j]) != null) {
                    // 将原HashMap的node设为null方便GC
                    oldTab[j] = null;
                    // e.next为null，即当前链表中只有一个元素
                    if (e.next == null)
                        // 直接将这个k-v对放到在新的桶里
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果是红黑树
                    else if (e instanceof TreeNode)
                        // 对红黑树进行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 链表，逐个处理
                    else {

                        // 因为扩容是容量翻倍，所以原链表上的每个节点在扩容后可能存放在原来的下标，即low位
                        // 或者扩容后的下标，即high位，high位=low位+扩容前容量
                        
                        // 低位链表的头结点、尾节点
                        Node<K,V> loHead = null, loTail = null;
                        // 高位链表的头结点、尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        // 临时节点 存放e的下一个节点
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 等于0代表小于oldCap，应该存放在低位，否则存放在高位
                            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);
                        // 将低位链表存放在原index处
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 将高位链表存放在原index处
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 返回扩容后的HashMap
        return newTab;
    }

    /**
     * 将链表树化为红黑树，如果容量太小(小于64)，会直接扩容
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index;
        Node<K,V> e;
        //  如果桶数组容量小于MIN_TREEIFY_CAPACITY=64，优先进行扩容而不是树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 根据hash值和数组长度进行取模运算后，得到链表的首节点
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                // 将该节点转换为TreeNode
                TreeNode<K,V> p = replacementTreeNode(e, null);
                // 如果尾节点为空，说明还没有根节点
                if (tl == null)
                    // 根节点指向当前节点
                    hd = p;
                // 尾节点不为空
                else {
                    // 双向链表
                    p.prev = tl;
                    tl.next = p;
                }
                // 把当前节点设为尾节点
                tl = p;
            // 遍历链表

            // 到目前为止，只把Node转换成了TreeNode，把单向链表转换成了双向链表
            } while ((e = e.next) != null);
            // 用转换后的双向链表替换原来位置上的单向链表
            if ((tab[index] = hd) != null)
                // 真正的红黑树转换
                hd.treeify(tab);
        }
    }

    /**
     * 将map m的元素都复制到当前map中
     * 将会把当前map中存在的k-v对替换掉
     *
     * @param m mappings to be stored in this map
     * @throws NullPointerException if the specified map is null
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

    /**
     * 删除指定key的k-v对
     * 如果key存在，返回删除前的value，否则返回null
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    /**
     * remove方法的实现
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue true表示必须key和value都对应相等才删除
     * @param movable false表示删除时不移动其他元素
     * @return the node, or null if none
     */
    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;
        // 如果table不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            // 且有hash出的index下有节点
            (p = tab[index = (n - 1) & hash]) != null) {
            // node是待删除节点
            Node<K,V> node = null, e; K k; V v;
            // 如果key的值与链表头节点相等，则将node指向该节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // 否则遍历下去
            else if ((e = p.next) != null) {
                // 如果是TreeNode，调用红黑树的getTreeNode()删除节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 遍历链表，直到找到待删除节点，再将node指向该节点
                    do {
                        /**
                         * 关键的判断依据
                         * 其实第二句(k = e.key) == key ||
                             (key != null && key.equals(k)等价于key.equals(k)
                         * 多出的(k = e.key) == key可以减少后面调用equals()，提高效率
                         * 
                         * 1. hashCode是否相等：e.hash == hash
                         * 2. key地址是否相同（key是否是同个对象）：((k = e.key) == key
                         * 3. 是否key.equals(k)
                         */
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
             //如果待删除节点node存在，matchValue为false，或者值也相等
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 如果是TreeNode，调用红黑树的getTreeNode()删除节点
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                // 如果头节点是待删除节点
                else if (node == p)
                    // 由于删除的是头节点，那么直接将删除位置(头节点)指向到第二个节点即可
                    tab[index] = node.next;
                // 如果找到的节点不是链表的头节点，那么此时p是node的前向节点
                else
                    // 直接通过p.next = node.next跨过node节点
                    p.next = node.next;
                // 结构改变
                ++modCount;
                --size;
                // LinkedHashMap回调函数
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    /**
     * 删除所有k-v对
     * HashMap将被清空
     */
    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                // 所有node都置null
                tab[i] = null;
        }
    }

    /**
     * 判断是否包含value
     * 如果HashMap内有一个或多个含有特定值的k-v对，返回true
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

    /**
     * 返回HashMap所有key的Set视图，对Map的修改会反应在Set中，反之亦然。
     * 如果在迭代Set的时候Map被修改了，迭代器返回的结果会是undefined.
     * Set支持Iterator.remove, Set.remove, removeAll, retainAll, clear
     * 不支持add, addAll
     * 
     * @return a set view of the keys contained in this map
     */
    public Set<K> keySet() {
        Set<K> ks;
        return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
    }

    // KeySet继承自抽象类AbstractSet
    // 用Set来保存所有的key就可以看出，key不能重复(最多可以有一个null值)
    final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> 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;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * 返回HashMap所有values的Collection视图，对Map的修改会反应在Set中，反之亦然。
     * 如果在迭代values的时候Map被修改了，迭代器返回的结果会是undefined.
     * values支持Iterator.remove, Collection.remove, removeAll, retainAll, clear
     * 不支持add, addAll
     *
     * @return a view of the values contained in this map
     */
    public Collection<V> values() {
        Collection<V> vs;
        return (vs = values) == null ? (values = new Values()) : vs;
    }

    // Values继承自AbstractCollection抽象类
    // value没有用Set而是使用AbstractCollection，说明value可以重复且可以有多个null
    final class Values extends AbstractCollection<V> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<V> iterator()     { return new ValueIterator(); }
        public final boolean contains(Object o) { return containsValue(o); }
        public final Spliterator<V> spliterator() {
            return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super V> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.value);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    /**
     * 返回HashMap所有k-v对的Set视图，对Map的修改会反应在Set中，反之亦然。
     * 如果在迭代entrySet的时候Map被修改了，迭代器返回的结果会是undefined.
     * entrySet支持Iterator.remove, Set.remove, removeAll, retainAll, clear
     * 不支持add, addAll
     *
     * @return a set view of the mappings contained in this map
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

    // KeySet继承自抽象类AbstractSet
    // 可以看出不允许有key和value都相同的Entry存在
    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    // JDK8 Map 接口新增的方法

    // 找到key对应的value，找不到则返回defaultValue
    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

    // put新的k-v对，若key相同，则value不会覆盖
    @Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

    @Override
    public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

    @Override
    public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }

    // 获取key对应的value，若key对应的value为空，会将Function的返回值存入并返回该值
    // 如果Function()返回的值为null或抛出异常，则不会有值存入map
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
            V oldValue;
            if (old != null && (oldValue = old.value) != null) {
                afterNodeAccess(old);
                return oldValue;
            }
        }
        V v = mappingFunction.apply(key);
        if (v == null) {
            return null;
        } else if (old != null) {
            old.value = v;
            afterNodeAccess(old);
            return v;
        }
        else if (t != null)
            t.putTreeVal(this, tab, hash, key, v);
        else {
            tab[i] = newNode(hash, key, v, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
        return v;
    }

    // 如果key对应的value存在且不为空，将BiFunction的返回值存入并返回该值
    // 如果BiFunction的返回值为null，则remove(key)
    public V computeIfPresent(K key,
                              BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        Node<K,V> e; V oldValue;
        int hash = hash(key);
        if ((e = getNode(hash, key)) != null &&
            (oldValue = e.value) != null) {
            V v = remappingFunction.apply(key, oldValue);
            if (v != null) {
                e.value = v;
                afterNodeAccess(e);
                return v;
            }
            else
                removeNode(hash, key, null, false, true);
        }
        return null;
    }

    // 将BiFunction的返回值与key建立mapping
    // 如果BiFunction的返回值为null：
    // 1. key存在：key对应value不为null，移除该k-v对，返回null
    // 2. key不存在：直接返回null
    @Override
    public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        V oldValue = (old == null) ? null : old.value;
        V v = remappingFunction.apply(key, oldValue);
        if (old != null) {
            if (v != null) {
                old.value = v;
                afterNodeAccess(old);
            }
            else
                removeNode(hash, key, null, false, true);
        }
        else if (v != null) {
            if (t != null)
                t.putTreeVal(this, tab, hash, key, v);
            else {
                tab[i] = newNode(hash, key, v, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
        }
        return v;
    }

    @Override
    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (value == null)
            throw new NullPointerException();
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        if (old != null) {
            V v;
            if (old.value != null)
                v = remappingFunction.apply(old.value, value);
            else
                v = value;
            if (v != null) {
                old.value = v;
                afterNodeAccess(old);
            }
            else
                removeNode(hash, key, null, false, true);
            return v;
        }
        if (value != null) {
            if (t != null)
                t.putTreeVal(this, tab, hash, key, value);
            else {
                tab[i] = newNode(hash, key, value, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
        }
        return value;
    }

    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Node<K,V>[] tab;
        if (function == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    e.value = function.apply(e.key, e.value);
                }
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    /* ------------------------------------------------------------ */
    // Cloning and serialization

    /**
     * 返回HashMap的浅拷贝，原有的key和value并不会被复制
     * 但HashMap中的新buckets不是指向同一地址，而是buckets里面的bins指向同一地址
     * 新克隆的HashMap值改变会影响到原有的HashMap
     *
     * @return a shallow copy of this map
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

    // These methods are also used when serializing HashSets
    final float loadFactor() { return loadFactor; }
    final int capacity() {
        return (table != null) ? table.length :
            (threshold > 0) ? threshold :
            DEFAULT_INITIAL_CAPACITY;
    }

    /**
     * 序列化HashMapp
     *
     * @serialData The <i>capacity</i> of the HashMap (the length of the
     *             bucket array) is emitted (int), followed by the
     *             <i>size</i> (an int, the number of key-value
     *             mappings), followed by the key (Object) and value (Object)
     *             for each key-value mapping.  The key-value mappings are
     *             emitted in no particular order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity();
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();
        s.writeInt(buckets);
        s.writeInt(size);
        internalWriteEntries(s);
    }

    /**
     * 反序列化HashMap
     */
    private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultReadObject();
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // Read and ignore number of buckets
        int mappings = s.readInt(); // Read number of mappings (size)
        if (mappings < 0)
            throw new InvalidObjectException("Illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (if zero, use defaults)
            // Size the table using given load factor only if within
            // range of 0.25...4.0
            float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
            float fc = (float)mappings / lf + 1.0f;
            int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                       DEFAULT_INITIAL_CAPACITY :
                       (fc >= MAXIMUM_CAPACITY) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor((int)fc));
            float ft = (float)cap * lf;
            threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                         (int)ft : Integer.MAX_VALUE);
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;

            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) {
                @SuppressWarnings("unchecked")
                    K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

    /* ------------------------------------------------------------ */
    // iterators

    abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

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

        public final boolean hasNext() {
            return next != 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;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

    /* ------------------------------------------------------------ */
    // spliterators

    static class HashMapSpliterator<K,V> {
        final HashMap<K,V> map;
        Node<K,V> current;          // current node
        int index;                  // current index, modified on advance/split
        int fence;                  // one past last index
        int est;                    // size estimate
        int expectedModCount;       // for comodification checks

        HashMapSpliterator(HashMap<K,V> m, int origin,
                           int fence, int est,
                           int expectedModCount) {
            this.map = m;
            this.index = origin;
            this.fence = fence;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getFence() { // initialize fence and size on first use
            int hi;
            if ((hi = fence) < 0) {
                HashMap<K,V> m = map;
                est = m.size;
                expectedModCount = m.modCount;
                Node<K,V>[] tab = m.table;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            return hi;
        }

        public final long estimateSize() {
            getFence(); // force init
            return (long) est;
        }
    }

    static final class KeySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<K> {
        KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                       int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public KeySpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
                                        expectedModCount);
        }

        public void forEachRemaining(Consumer<? super K> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.key);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super K> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        K k = current.key;
                        current = current.next;
                        action.accept(k);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }
    }

    static final class ValueSpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<V> {
        ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public ValueSpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        public void forEachRemaining(Consumer<? super V> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.value);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super V> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        V v = current.value;
                        current = current.next;
                        action.accept(v);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
        }
    }

    static final class EntrySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<Map.Entry<K,V>> {
        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public EntrySpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        Node<K,V> e = current;
                        current = current.next;
                        action.accept(e);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }
    }

    /* ------------------------------------------------------------ */
    // LinkedHashMap support


    /*
     * The following package-protected methods are designed to be
     * overridden by LinkedHashMap, but not by any other subclass.
     * Nearly all other internal methods are also package-protected
     * but are declared final, so can be used by LinkedHashMap, view
     * classes, and HashSet.
     */

    // Create a regular (non-tree) node
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

    // For conversion from TreeNodes to plain nodes
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

    // Create a tree bin node
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        return new TreeNode<>(hash, key, value, next);
    }

    // For treeifyBin
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

    /**
     * Reset to initial default state.  Called by clone and readObject.
     */
    void reinitialize() {
        table = null;
        entrySet = null;
        keySet = null;
        values = null;
        modCount = 0;
        threshold = 0;
        size = 0;
    }

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

    // Called only from writeObject, to ensure compatible ordering.
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K,V>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    }

    /* ------------------------------------------------------------ */
    // Tree bins

    /**
     * 红黑树
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    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;
            }
        }

        /**
         * 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;
                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;
                    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;
                }
                assert checkInvariants(root);
            }
        }

        /**
         * Finds the node starting at root p with the given hash and key.
         * The kc argument caches comparableClassFor(key) upon first use
         * comparing keys.
         */
        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;
        }

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

        /**
         * Tie-breaking utility for ordering insertions when equal
         * hashCodes and non-comparable. We don't require a total
         * order, just a consistent insertion rule to maintain
         * equivalence across rebalancings. Tie-breaking further than
         * necessary simplifies testing a bit.
         */
        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;
        }

        /**
         * Forms tree of the nodes linked from this node.
         * @return root of tree
         */
        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);
        }

        /**
         * Returns a list of non-TreeNodes replacing those linked from
         * this node.
         */
        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);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        /**
         * Tree version of putVal.
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            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 || (pk != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        TreeNode<K,V> 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;
                    }
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    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;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        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;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                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);
        }

        /**
         * Splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. Called only from resize;
         * see above discussion about split bits and indices.
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // 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)
                    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);
                }
            }
        }

        /* ------------------------------------------------------------ */
        // Red-black tree methods, all adapted from CLR

        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }

        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;)  {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = 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;
        }
    }

}