学习JDK1.8集合源码之--HashMap

1. HashMap简介

　　HashMap是一种key-value结构存储数据的集合，是map集合的经典哈希实现。

　　HashMap允许存储null键和null值，但null键最多只能有一个（HashSet就是以HashMap实现的，通过HashMap的key存储元素，所以HashSet也最多允许存储一个null值并且其中的元素不可重复）。

　　HashMap是非线程安全的实现，在多线程环境下会出现数据丢失的情况，与JDK1.8以前不同的是并不会出现死循环的情况。在多线程情况下最好使用ConcurrentHashMap来代替。

　　需要注意的是，本文主要针对JDK8版本进来分析，JDK8以前的HashMap是数组+链表的简单实现，但在JDK8后，当链表中的元素超过8个后就会采用红黑树来进行存储，为了避免链表中数据量太大造成的查找效率低下的问题。因为链表的查询时间复杂度是O(n)，即随着链表中元素个数的增加，当数据增大n倍时，耗时增大n倍；而红黑树的查询时间复杂度为O(logn)，即当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。

2. HashMap实现

1. 核心参数

    //默认初始容量16，1左移4位相当于2^4
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //由链表转换成树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    //由树转换成链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    //当桶中的bin被树化时最小的hash表容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    //Node数组存储元素
    transient Node<K,V>[] table;
    //内部entry实体的集合
    transient Set<Map.Entry<K,V>> entrySet;
    //map大小
    transient int size;
    //修改次数
    transient int modCount;
    //需要进行扩容的阈值，capacity * loadFactor，如果没有进行扩容过，则threshold的值可能为0，也可能等于底层数组的容量
    int threshold;
    //加载因子，表明存储元素的最大饱和度
    final float loadFactor;
    //静态内部类，实现了Map.Entry接口，用于存储每个节点的数据
    static class Node<K,V> implements Map.Entry<K,V> {
        //key的hashcode值
        final int hash;
        //Map的key
        final K key;
        //Map的value
        V value;
        //下一个节点
        Node<K,V> next;

        //唯一构造方法
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        //返回map的key
        public final K getKey()        { return key; }
        //返回map的value
        public final V getValue()      { return value; }
        //重写toString方法
        public final String toString() { return key + "=" + 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;
        }
        //重写equals方法
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

   //红黑树节点，由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性
　 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
      //红黑树的颜色，true为red，false为black
　　  boolean red;
　 }

　　从上面可以看出，HashMap底层首先是由数组来存储的，存储的元素为Entry实体，Entry中包含hashCode、key、value、next四个属性。理想情况下，数组中每个位置最多存储一个Entry实体，数组中每个Entry实体的hashCode、key都是不同的，next都是null。但如果出现了hash碰撞（两个Entry实体的通过hash运算得到的下标相同），则会以链表形式存储hashCode相同的元素，而链表的头部都存在数组里面。所以当出现hash碰撞时，不会把新的Entry实体插入数组，而是根据hashCode找到数组中存储的链表头，然后根据链表头的next指针依次遍历链表，直到找到next为null的Entry实体，把新加的实体赋给next为null的Entry实体的next，这样就完成了一次插入过程。JDK8之前这样就结束了，但是在JDK8里，当链表超过8个，就会改用红黑树来存储，至于是如何通过红黑树存储的，下面再做分析。

2. 构造方法

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

    //传入一个初始容量，默认加载因子0.75，初始容量必须是2的次幂，若不是则会使用比传入初始容量大的最小2的次幂
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //传入初始容量和默认加载因子，初始容量必须是2的次幂，若不是则会使用比传入初始容量大的最小2的次幂
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量不能小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        //初始容量不能大于2^30，因为2^31大于int最大值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //加载因子不能小于等于0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        //计算初始容量，为了保证容量为2的次幂
        this.threshold = tableSizeFor(initialCapacity);
    }

    //传入一个map，使用默认加载因子0.75，并把map中的元素存入HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

　　构造方法主要以初始容量和加载因子为主，因为这两个参数是HashMap构造的最核心的参数，并且有参构造的初始容量是赋值给threshold的，构造期间没有进行底层数据的实例化。这里和ArrayList一样，都是在添加元素的时候才会实例化一个数组，而实例化时数组的容量就取threshold的值，无参构造构造的话就会取定义的默认初始容量16。这也就解释了threshold值可能存在的三种情况：0，capacity，capacity * loadFactor。

3. 核心方法

　  HashMap内部的核心方法包括hash、tableSizeFor、putMapEntries、putVal、getNode、resize、treeifyBin、removeNode等方法。

　　hash：HashMap没有采用Object类的hashCode函数，而是内部实现的hash函数，通过key的hashcode高16位不变，然后低16位采用高16位于低16位进行异或运算的结果，来减少hash碰撞。

　　tableSizeFor：保证了HashMap初始化的时候容量为2的次幂，这是HashMap的实现核心基础。因为HashMap底层基于数组实现的，数组是一种通过索引机制来进行数组存储的，所以在查询时效率比较高，但是HashMap是一种以key-value形式存储的数据结构，想要通过key快速找到对应的value就要利用数组的索引机制，可是该如何利用呢？答案是根据key的hashCode与元素的length-1进行与运算得到数组的索引，Hashmap在进行存储、查找、删除等操作时都是通过这种方式的。

　　putMapEntries：向HashMap中添加一个map中的所有元素。putMapEntries实际上也是通过putVal来进行元素添加的。

　　putVal：向HashMap中添加元素的实现方法。每次添加元素根据key的hashCode与元素的length-1进行与运算得到数组的索引，如果该索引位置为空则添加的时间复杂度为O(1)，这也是HashMap最理想的状态（不存在hash碰撞）。之所以HashMap采用数组+链表的结构存储是为了解决hash碰撞的问题，当出现hash碰撞时就要用链表来存储，因为链表的时间复杂度是O(n)，故当出现hash碰撞时的时间复杂度是O(n)。在JDK1.8以前HashMap最差的情况下时间复杂度是O(n)，但是在JDK1.8里加入红黑树来进行了优化。当链表中的元素个数大于8个的时候就会采用红黑树代替链表来进行存储，因为红黑树的时间复杂度为O(logn)，所以当链表中元素大于8的时候putVal的时间复杂度为O(logn)，不过因为putVal方法还涉及到扩容、链表转红黑树等操作，情况比较复杂。

　　getNode：根据key获取对应节点。跟putVal差不多，根据key的hashCode与元素的length-1进行与运算得到数组的索引，如果该索引位置的key就是需要查找的key则查找的时间复杂度为O(1)；若不是则要看该索引位置的节点是不是树形节点，如果是树形节点则说明是由红黑树存储的，这时的查找时间复杂度为O(logn)；若不是树形节点则说明是由链表存储，这时的时间复杂度为O(n)。

　　resize：HashMap核心扩容算法。该方法会把原数组扩容1倍并进行reHash，将原来的存储结构（链表和红黑树）打乱重新构造，使新数组数组尽量的分布均匀。至于是如何实现的，请看下面的resize方法注释。当是红黑树存储时，会调用红黑树的split函数进行处理，如果是链表则会把key的hashCode与原数组的容量进行与运算，结果为0则在新数组位置不变，否则在新数组的位置为原数组容量+原数组下标。

　　treeifyBin：树形化，链表转为红黑树的核心处理逻辑。实际上是调用内部类TreeNode的treeify方法来构建红黑树。

　　removeNode：根据key移除对应节点。先查找到该节点，逻辑与getNode一致。然后判断该节点类型，如果是树形节点，则移除后重组红黑树；如果是链表，则移除后重组链表。

    //hash函数，高16bit不变，低16bit和高16bit做了一个异或，目的是减少hash碰撞。
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    //判断x是否实现了Comparable接口并且Comparable的泛型类型与x的类型相同
    //若是则返回x的Class类型，否则返回null
    static Class<?> comparableClassFor(Object x) {
        //如果x没有实现Comparable接口，则直接返回null
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            //x.getClass()返回x的class类型并赋值给c，同时判断c是否为String.class，是则将c返回
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            //将c中直接实现的所有接口赋值给ts
            //Type是Java 编程语言中所有类型的公共高级接口（官方解释），
            //Type体系中类型的包括：原始类型(Class)、参数化类型(ParameterizedType)、数组类型(GenericArrayType)、类型变量(TypeVariable)、基本类型(Class);
            //原始类型，不仅仅包含我们平常所指的类，还包括枚举、数组、注解等；
            //参数化类型，就是我们平常所用到的泛型List、Map；
            //数组类型，并不是我们工作中所使用的数组String[] 、byte[]，而是带有泛型的数组，即T[] ；
            //基本类型，也就是我们所说的java的基本类型，即int,float,double等
            if ((ts = c.getGenericInterfaces()) != null) {
                //遍历c中实现的接口类型
                for (int i = 0; i < ts.length; ++i) {
                    //如果当前类型属于参数化类型
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        //并且该类型是Comparable.class （getRawType返回声明了这个类型的类或接口）
                        ((p = (ParameterizedType)t).getRawType() == Comparable.class) &&
                        //并且该类型的泛型参数列表不为空 （getActualTypeArguments以数组的形式返回泛型参数列表）
                        (as = p.getActualTypeArguments()) != null &&
                        //并且该类型的泛型参数列表只有一个参数该参数就是c
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

    //比较两个实现了Comparable接口的同类型元素的大小，k比x大返回1，k比x小返回-1，x为null或不是同类型返回0
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

    //用于初始化HashMap时保证容量是2的次幂，这里的算法和ArrayDeque差不多，如果传入的容量不是2的次幂，则会通过一系列位运算得到大于传入容量的最小2的次幂
    //唯一的区别是ArrayDeque传入的容量是2的n次幂，会初始化一个2的n+1次幂的初始容量
    //而HashMap如果传入的容量是2的n次幂，会初始化一个2的n次幂的初始容量，只因为开始做了int n = cap - 1;
    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;
    }

    //Implements Map.putAll and Map constructor
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //取传入的map大小赋值给s
        int s = m.size();
        if (s > 0) {
            //如果HashMap为空，则计算需要
            if (table == null) { // pre-size
                //(ft - 1.0F) * loadFactor = s ;
                //ft为满足容纳s个元素的最小容量
                float ft = ((float)s / loadFactor) + 1.0F;
                //如果ft小于2^30则t=ft,否则t=2^30
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                //未被扩容的HashMap的threshold值等于容量
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //如果HashMap不为空且s大于需要扩容的阈值，则进行扩容
            else if (s > threshold)
                resize();
            //在这之前已经保证HashMap足够容纳传入的map，下面开始遍历传入的map
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                //依次获取map的key和value
                K key = e.getKey();
                V value = e.getValue();
                //通过putVal方法将key-value存入HashMap
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    //返回HashMap的大小
    public int size() {
        return size;
    }

    //返回HashMap的是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //根据key获取value
    public V get(Object key) {
        Node<K,V> e;
        //根据key和key的hashCode获取Node，若Node为空则返回null，否则根据Node获取value并返回
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    //实现了根据key和key的hashCode获取Node
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //将底层数组赋值给tab，底层数组容量赋值给n
        if ((tab = table) != null && (n = tab.length) > 0 &&
            //tab[(n - 1) & hash]来根据key的hashCode与底层数组的length-1通过与运算获取到对应的存储位置下标
            //这也是为什么数组的容量必须是2的次幂的原因，因为2的n次幂的二进制都是 1 + n个0 ，
            //length为2的4次幂的二进制为10000，这样length-1的二进制为01111
            //这样length-1与任何二进制数通过与运算的结果都会小于等于length-1，大于等于0，也就保证了不会出现数组越界的情况
            //并且可以通过key的hashCode与length-1通过与运算获取到对应的存储位置下标，真是一举多得啊！！！
            //因为HashMap是数组加链表（或红黑树）存储的，所以这里first取的是链表的头部或者红黑树的根节点
            (first = tab[(n - 1) & hash]) != null) {
            //检查first节点的hashCode值是否跟key的hashCode相同，如果相同且key与first.key相同，则直接将first节点返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果first节点的next节点不为空，则继续寻找key相同的节点，否则返回null
            if ((e = first.next) != null) {
                //如果first节点是树形节点，说明是红黑树实现的，则根据红黑树的算法查找节点
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //否则为链表实现，循环根据next指针遍历链表，直到找到key相同的节点并返回，找不到则返回null。
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    //判断HashMap中是否包含key，通过判断getNode是否为空实现
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

    //添加key-value结构数据，若key已存在则替换value
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    //添加元素的实现方法，若onlyIfAbsent为true则不会改变已经存在的value值，若evict为false则说明HashMap处于创建状态
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果HashMap为空则
        if ((tab = table) == null || (n = tab.length) == 0)
            //实例化底层数组
            n = (tab = resize()).length;
        //如果该元素计算出的下标位置没有元素，直接放入数组对应下标位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果传入的非空key已存在且与该位置的链表头节点的key相同，则将value替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果该位置的链表有节点是一个树形节点，则调用红黑树的插入方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //否则为链表结构
            else {
                for (int binCount = 0; ; ++binCount) {
                    //将链表遍历完后还没遇到相同的key，新建一个节点追加到链表尾节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果如果链表中的元素个数大于8个，则进行树形化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果遇到key与插入的key相同的节点，则将该节点value值替换
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //key在map中已存在，替换为新值并将旧值返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //key在map中不存在，插入次数+1
        ++modCount;
        //如果添加后的元素数量大于扩容阈值，则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    //核心扩容算法
    final Node<K,V>[] resize() {
        //把原底层数组备份一份
        Node<K,V>[] oldTab = table;
        //取原数组的容量大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //取原数组的扩容阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //非HashMap初始化阶段
        if (oldCap > 0) {
            //如果原数组的容量大于等于2^30,一般只会等于2^30，因为已经是最大容量，不支持再进行扩容了
            if (oldCap >= MAXIMUM_CAPACITY) {
                //将扩容阈值设为int最大值，这样threshold<oldCap就不会再扩容了
                threshold = Integer.MAX_VALUE;
                //直接将旧的数组返回
                return oldTab;
            }
            //否则将容量扩容1倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果扩容后的容量小于2^30且扩容前的容量大于等于默认初始容量，则将扩容阈值翻倍
                newThr = oldThr << 1; // double threshold
        }
        //HashMap初始化阶段，并且扩容阈值大于0，则把容量设为与扩容阈值一致，
        //除了无参构造，其他三个构造函数都会把threshold设为数组容量的值，然后在存入元素时才实例化一个数组，容量就取threshold的值
        else if (oldThr > 0)
            newCap = oldThr;
        //HashMap初始化阶段，无参构造只会初始化一个loadFactor
        else {
            //数组容量取默认初始容量16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //扩容阈值取 16 * 0.75 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //这里针对 oldCap > 0 && oldThr > 0 的情况做的处理，这时候的newCap = oldThr;
        //所以需要把threshold 变成 newCap * loadFactor，oldThr仅仅作为临时存储容量的容器
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //新建一个Node数组（如果oldCap == 0，这里就是首次创建底层数组的地方）
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //如果原本已经存储过数据，则把原来存储的数据
        if (oldTab != null) {
            //遍历旧数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //将就数组中的数据依次存入e，如果为空则继续取下一个数据
                if ((e = oldTab[j]) != null) {
                    //依次将就数组中存储的数据清空，方便GC回收旧数组
                    oldTab[j] = null;
                    //如果当前数据没有next节点，直接把e放入新数组
                    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;
                            //将元素的hashCode与原数组容量进行与运算
                            //结果为0则在新数组中的索引位置不变
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    //原数组中的链表头
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //结果不为0则将在原数组中的索引加上原数组的容量作为新数组中的索引
                            else {
                                if (hiTail == null)
                                    //新数组的链表头
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            //放入原索引位置
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            //放入新索引位置
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    //将链表树形化，转为红黑树存储
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //如果底层数组为空或者数组的长度小于树形化最小容量，则进行resize
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            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);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //如果指定位置的元素不为空，则将该位置的链表树形化
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    //将一个map中的所有元素存入HashMap
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    } 

    //将指定key从HashMap中移除
    public V remove(Object key) {
        Node<K,V> e;
        //若该key存在则将value返回，不存在则返回null
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    //移除指定节点，若matchValue为true则只有当该节点值与value匹配时才进行移除
    //若movable为false，则移除后不改变其他元素的位置
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //底层数组不为空且该通过与运算计算的索引位置存在元素，否则直接返回null
        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;
            //该索引位置的链表头节点的key与移除的key匹配，直接取出该节点，待后面判断需不需要删除
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //否则如果链表中不止一个元素则继续，否则返回null
            else if ((e = p.next) != null) {
                //如果是红黑树节点，则根据红黑树的规则找到key相同的节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                //否则遍历链表寻找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);
                }
            }
            //如果找到了key相同的节点，若matchValue为false则进行移除逻辑
            //若matchValue为true则只有当该节点值与value匹配时才进行移除
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果是树形节点，则根据红黑树的规则进行移除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果要移除的是链表头节点，则把链表头的下一节点作为链表头
                else if (node == p)
                    tab[index] = node.next;
                //否则将移除节点的next节点链接到移除节点的pre节点
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    //清空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)
                tab[i] = null;
        }
    }

    //判断HashMap中是否包含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集合
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    //返回HashMap中所有value的集合
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

    //返回HashMap中所有key-value实体的Set集合
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }