欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java HashMap源码分析(JDK8)

程序员文章站 2022-06-04 19:57:32
...
前言

HashMap底层是由数组、链表、红黑树实现的,如果对链表、树以及红黑树结构不是很清楚的,可以查看我的另外几篇博客:Java数据结构之链表Java数据结构之二叉树Java数据结构之AVL树Java数据结构之红黑树

知识点小结
  1. HashMap是实现了Map接口的哈希表,HashMap实现了Map的所有操作并且key和value均允许为NULL。
  2. HashMap与HashTable相比:前者是非线程安全的,后者是线程安全的。
  3. 有两个参数会影响HashMap实例的性能:
    (1) 初始化capacity的大小
    capacity是指:哈希表拥有的bucket的数量.而初始化的capacity就是哈希表创建时的capacity.
    (2) 负载因子的大小.
    负载因子是指:它其实是HashMap实例的capacity自动增长的指标.
    当哈希表的条目超过了负载因子和capacity二者的乘积,哈希表会被rehash(也就是说,哈希表的内部数据结构会被重建),这样才能保证哈希表的bucket 的个数大约增长为之前的2倍大小。
  4. HashMap存储元素是没有顺序的,根据“(n - 1) & hash”当n为2的N次幂时,类似取余操作,因此也不能保证现有的顺序随着时间的推移不会发生变化。
  5. HashMap桶中节点其实为红黑树以及双向链表结构。
相关默认值
  1. 默认初始化容量 DEFAULT_INITIAL_CAPACITY16
  2. 允许最大容量DEFAULT_INITIAL_CAPACITY2^30
  3. 默认加载因子DEFAULT_LOAD_FACTOR0.75f
  4. 桶节点中链表转化为红黑树阈值TREEIFY_THRESHOLD8
  5. 桶节点中红黑树转化为链表阈值UNTREEIFY_THRESHOLD6
  6. 发生链表转为红黑树最小桶数MIN_TREEIFY_CAPACITY64
	public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    /**
     * HashMap的初始化,默认容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * HashMap的最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认加载因子为0.75,这个数字是在时间和空间的损耗上面做了一个平衡的值.较大的负载因子虽然
     * 会提升空间利用率,但是却提升了查找成本(查找成本在HashMap类中主要体现的操作就是get和put).
     * 当初始化一个HashMap的capacity的时候,条目的个数和负载因子这两个因素都应该被考虑进去,从而
     * 尽量减少resize(扩容)的次数.如果初始化的capacity比最多条目数除以负载因子的值还大,
     * 那么resize的操作绝不会出现.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表转化为红黑树的阈值
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 红黑树转化为链表的阈值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 桶被转为树的最小容量默认为64
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
成员变量定义
  1. transient Node<K,V>[] table:桶数组,容量(数组长度)总为2的N次幂,序列化时,table为null。
  2. transient Set<Map.Entry<K,V>> entrySet:保存缓存的entrySet(),序列化时,entrySet为null。
  3. transient int size:map中键值对的个数,序列化时,size没有值。
  4. transient int modCount:map结构的更改(键值对个数发生改变 or 其它改变map内部结构的操作,如resize时)的次数。
  5. int threshold:下一次resize的阈值大小:阈值=map容量负载因子.(threshold=capacityload factor)。
  6. final float loadFactor: 哈希表的负载因子,final类型字段,构造器给定后,不可更改。
   /* ---------------- Fields -------------- */
    /**
     * table在第一次使用时,进行初始化,如果有必要会有resize的操作(添加数据初始化情况?).
     * 当分配好大小后,table的大小总是2的整数次幂.
     * transient类型变量,序列化时,table=null
     */
    transient Node<K,V>[] table;

    /**
     * 保存缓存的entrySet()。请注意,AbstractMap字段用于keySet()和values()
     * transient类型  序列化时,entrySet=null
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * map中键值对的个数
     * transient 类型 序列化时,size没有值
     */
    transient int size;

    /**
     * map结构的更改次数.结构更改是:键值对个数发生改变 or 其它改变map内部结构的操作,如resize时.
     * 这又是一个transient类型的域
     */
    transient int modCount;

    /**
     * 下一次resize的阈值大小:阈值=map容量*负载因子.(threshold=capacity*load factor)
     */
    int threshold;

    /**
     * 哈希表的负载因子
     * final类型字段,构造器给定后,不可更改
     */
    final float loadFactor;
巧妙设计之(n - 1)&hash理解

这里设计很巧妙,就是n为2的N次幂时候,(n - 1)&hash 与 hash%n是一样的结果,并且恒成立,当n不为2的N次幂时候,(n - 1)&hash 与 hash%n就会有不相同的情况出现。
那么为什么不直接用取余(%)呢? 因为在计算机运算中,&为位运算,效率远高于%
Java HashMap源码分析(JDK8)

节点类关系

HashMap.Node<K,V> 节点类实现了 Map.Entry<K,V>,同时也是 LinkedHashMap.Entry<K,V> 的父类,HashMap中红黑树的HashMap.TreeNode<K,V>继承LinkedHashMap.Entry<K,V>

  1. HashMap.Node<K,V>定义
       /** 节点类定义*/
      static class Node<K,V> implements Map.Entry<K,V> {
       
           final int hash;//该键值对的哈希值
           final K key;//键
           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;
           }
           
           /*** 获取key值*/
           public final K getKey()        { return key; }
           /*** 获取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值,返回原值*/
           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;
           }
       }
  1. HashMap.TreeNode<K,V>定义
    /**
     * 红黑树实体,继承自LinkedHashMap.Entry, 然而LinkedHashMap.Entry 继承自HashMap.Node,
     * 因此可以用作普通或扩展的链表节点(转为HashMap.Node)。
     * 
     * 改红黑树除了是一个红黑树结构外,还是一个双向链表结构
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        
        TreeNode<K,V> parent;  // 红黑树连接点
        TreeNode<K,V> left;    // 左子节点 
        TreeNode<K,V> right;   // 右子节点
        TreeNode<K,V> prev;    // 删除节点时,断开连接,记录删除节点的前一个节点
        boolean red;           // 节点颜色标识
        /**
         *  除了上面的成员变量外,还有HashMap.Node中的 hash/key/value/next
         */
        
        /**
         * 构造防范,实际调用的是HashMap.Node的构造方法
         */
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * 返回红黑树的根节点
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * 确保table数据的桶中的节点为红黑树的根节点
         */
        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];
                /**
                 * 如果根节点不是桶中的节点,直接用root节点覆盖桶的第一个节点,]
                 * 在原链表中删除root节点,原first节点作为root节点的next节点 
                 */
                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;
                    // first节点存在,first的前驱节点指向根节点
                    if (first != null)
                        first.prev = root;
                    // 根节点的后驱节点指向first节点
                    root.next = first;
                    // 根节点的前驱节点置空
                    root.prev = null;
                }
                // 再次校验红黑树是否符合红黑树规则
                assert checkInvariants(root);
            }
        }

        /**
         * 根据指定的 hash以及key从根节点开始查找,
         * kc变量的意义在于:第一次使用时,缓存可比较的key.这样下次一样的key,则可以迅速找到该节点(当然map不能改变)
         */
        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;
                // 查找节点hash值小于p节点的hash值,向p的左子节点查找
                if ((ph = p.hash) > h)
                    p = pl;
                // 查找节点hash值大于p节点的hash值,向p的右子节点查找
                else if (ph < h)
                    p = pr;
                // 查找到,返回改节点
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                // p没有左子节点,从p的右子节点查找
                else if (pl == null)
                    p = pr;
                // p没有右子节点,从p的左子节点查找
                else if (pr == null)
                    p = pl;
                // 有kc,
                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);
        }

        /**
        * 用这个方法来比较两个对象,返回值要么大于0,要么小于0,不会为0
        * 也就是说这一步一定能确定要插入的节点要么是树的左节点,要么是右节点,不然就无法继续满足二叉树结构了
        * 
        * 先比较两个对象的类名,类名是字符串对象,就按字符串的比较规则
        * 如果两个对象是同一个类型,那么调用本地方法为两个对象生成hashCode值,再进行比较,hashCode相等的话返回-1
        */
        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;
        }
        
        /**
         * 参数为HashMap的元素数组
         */
        final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null; // 定义树的根节点
            for (TreeNode<K,V> x = this, next; x != null; x = next) { // 遍历链表,x指向当前节点、next指向下一个节点
                next = (TreeNode<K,V>)x.next; // 下一个节点
                x.left = x.right = null; // 设置当前节点的左右节点为空
                if (root == null) { // 如果还没有根节点
                    x.parent = null; // 当前节点的父节点设为空
                    x.red = false; // 当前节点的红色属性设为false(把当前节点设为黑色)
                    root = x; // 根节点指向到当前节点
                }
                else { // 如果已经存在根节点了
                    K k = x.key; // 取得当前链表节点的key
                    int h = x.hash; // 取得当前链表节点的hash值
                    Class<?> kc = null; // 定义key所属的Class
                    for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历,此遍历没有设置边界,只能从内部跳出
                        // GOTO1
                        int dir, ph; // dir 标识方向(左右)、ph标识当前树节点的hash值
                        K pk = p.key; // 当前树节点的key
                        if ((ph = p.hash) > h) // 如果当前树节点hash值 大于 当前链表节点的hash值
                            dir = -1; // 标识当前链表节点会放到当前树节点的左侧
                        else if (ph < h)
                            dir = 1; // 右侧
         
                        /*
                         * 如果两个节点的key的hash值相等,那么还要通过其他方式再进行比较
                         * 如果当前链表节点的key实现了comparable接口,并且当前树节点和链表节点是相同Class的实例,那么通过comparable的方式再比较两者。
                         * 如果还是相等,最后再通过tieBreakOrder比较一次
                         */
                        else if ((kc == null &&
                                    (kc = comparableClassFor(k)) == null) ||
                                    (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);
         
                        TreeNode<K,V> xp = p; // 保存当前树节点
         
                        /*
                         * 如果dir 小于等于0 : 当前链表节点一定放置在当前树节点的左侧,但不一定是该树节点的左孩子,也可能是左孩子的右孩子 或者 更深层次的节点。
                         * 如果dir 大于0 : 当前链表节点一定放置在当前树节点的右侧,但不一定是该树节点的右孩子,也可能是右孩子的左孩子 或者 更深层次的节点。
                         * 如果当前树节点不是叶子节点,那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己(当前链表节点)的位置
                         * 如果当前树节点就是叶子节点,那么根据dir的值,就可以把当前链表节点挂载到当前树节点的左或者右侧了。
                         * 挂载之后,还需要重新把树进行平衡。平衡之后,就可以针对下一个链表节点进行处理了。
                         */
                        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;
                        }
                    }
                }
            }
         
            // 把所有的链表节点都遍历完之后,最终构造出来的树可能经历多个平衡操作,根节点目前到底是链表的哪一个节点是不确定的
            // 因为我们要基于树来做查找,所以就应该把 tab[N] 得到的对象一定根节点对象,而目前只是链表的第一个节点对象,所以要做相应的处理。
            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;
        }
        /**
         * 当存在hash碰撞的时候,且元素数量大于8个时候,就会以红黑树的方式将这些元素组织起来
         * map 当前节点所在的HashMap对象
         * tab 当前HashMap对象的元素数组
         * h   指定key的hash值
         * k   指定key
         * v   指定key上要写入的值
         * 返回:指定key所匹配到的节点对象,针对这个对象去修改V(返回空说明创建了一个新节点)
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                        int h, K k, V v) {
            Class<?> kc = null; // 定义k的Class对象
            boolean searched = false; // 标识是否已经遍历过一次树,未必是从根节点遍历的,但是遍历路径上一定已经包含了后续需要比对的所有节点。
            TreeNode<K,V> root = (parent != null) ? root() : this; // 父节点不为空那么查找根节点,为空那么自身就是根节点
            for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历,没有终止条件,只能从内部退出
                int dir, ph; K pk; // 声明方向、当前节点hash值、当前节点的键对象
                if ((ph = p.hash) > h) // 如果当前节点hash 大于 指定key的hash值
                    dir = -1; // 要添加的元素应该放置在当前节点的左侧
                else if (ph < h) // 如果当前节点hash 小于 指定key的hash值
                    dir = 1; // 要添加的元素应该放置在当前节点的右侧
                else if ((pk = p.key) == k || (k != null && k.equals(pk))) // 如果当前节点的键对象 和 指定key对象相同
                    return p; // 那么就返回当前节点对象,在外层方法会对v进行写入
         
                // 走到这一步说明 当前节点的hash值  和 指定key的hash值  是相等的,但是equals不等
                else if ((kc == null &&
                            (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0) {
         
                    // 走到这里说明:指定key没有实现comparable接口   或者   实现了comparable接口并且和当前节点的键对象比较之后相等(仅限第一次循环)
                
         
                    /*
                     * searched 标识是否已经对比过当前节点的左右子节点了
                     * 如果还没有遍历过,那么就递归遍历对比,看是否能够得到那个键对象equals相等的的节点
                     * 如果得到了键的equals相等的的节点就返回
                     * 如果还是没有键的equals相等的节点,那说明应该创建一个新节点了
                     */
                    if (!searched) { // 如果还没有比对过当前节点的所有子节点
                        TreeNode<K,V> q, ch; // 定义要返回的节点、和子节点
                        searched = true; // 标识已经遍历过一次了
                        /*
                         * 红黑树也是二叉树,所以只要沿着左右两侧遍历寻找就可以了
                         * 这是个短路运算,如果先从左侧就已经找到了,右侧就不需要遍历了
                         * find 方法内部还会有递归调用。参见:find方法解析
                         */
                        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; // 找到了指定key键对应的
                    }
         
                    // 走到这里就说明,遍历了所有子节点也没有找到和当前键equals相等的节点
                    dir = tieBreakOrder(k, pk); // 再比较一下当前节点键和指定key键的大小
                }
         
                TreeNode<K,V> xp = p; // 定义xp指向当前节点
                /*
                * 如果dir小于等于0,那么看当前节点的左节点是否为空,如果为空,就可以把要添加的元素作为当前节点的左节点,如果不为空,还需要下一轮继续比较
                * 如果dir大于等于0,那么看当前节点的右节点是否为空,如果为空,就可以把要添加的元素作为当前节点的右节点,如果不为空,还需要下一轮继续比较
                * 如果以上两条当中有一个子节点不为空,这个if中还做了一件事,那就是把p已经指向了对应的不为空的子节点,开始下一轮的比较
                */
                if ((p = (dir <= 0) ? p.left : p.right) == null) {  
                    // 如果恰好要添加的方向上的子节点为空,此时节点p已经指向了这个空的子节点
                    Node<K,V> xpn = xp.next; // 获取当前节点的next节点
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个新的树节点
                    if (dir <= 0)
                        xp.left = x;  // 左孩子指向到这个新的树节点
                    else
                        xp.right = x; // 右孩子指向到这个新的树节点
                    xp.next = x; // 链表中的next节点指向到这个新的树节点
                    x.parent = x.prev = xp; // 这个新的树节点的父节点、前节点均设置为 当前的树节点
                    if (xpn != null) // 如果原来的next节点不为空
                        ((TreeNode<K,V>)xpn).prev = x; // 那么原来的next节点的前节点指向到新的树节点
                    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);
                }
            }
        }
        
        /**
        * 节点左旋
        * root 根节点
        * p 要左旋的节点
        */
       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
                   rl.parent = p; // 设置rl和要左旋的节点的父子关系【之前只是爹认了孩子,孩子还没有答应,这一步孩子也认了爹】
        
               // 将要左旋的节点的右孩子的父节点  指向 要左旋的节点的父节点,相当于右孩子提升了一层,
               // 此时如果父节点为空, 说明r 已经是顶层节点了,应该作为root 并且标为黑色
               if ((pp = r.parent = p.parent) == null) 
                   (root = r).red = false;
               else if (pp.left == p) // 如果父节点不为空 并且 要左旋的节点是个左孩子
                   pp.left = r; // 设置r和父节点的父子关系【之前只是孩子认了爹,爹还没有答应,这一步爹也认了孩子】
               else // 要左旋的节点是个右孩子
                   pp.right = r; 
               r.left = p; // 要左旋的节点  作为 他的右孩子的左节点
               p.parent = r; // 要左旋的节点的右孩子  作为  他的父节点
           }
           return root; // 返回根节点
       }
        
       /**
        * 节点右旋
        * root 根节点
        * p 要右旋的节点
        */
       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
                   lr.parent = p; // 设置lr和要右旋的节点的父子关系【之前只是爹认了孩子,孩子还没有答应,这一步孩子也认了爹】
        
               // 将要右旋的节点的左孩子的父节点  指向 要右旋的节点的父节点,相当于左孩子提升了一层,
               // 此时如果父节点为空, 说明l 已经是顶层节点了,应该作为root 并且标为黑色
               if ((pp = l.parent = p.parent) == null) 
                   (root = l).red = false;
               else if (pp.right == p) // 如果父节点不为空 并且 要右旋的节点是个右孩子
                   pp.right = l; // 设置l和父节点的父子关系【之前只是孩子认了爹,爹还没有答应,这一步爹也认了孩子】
               else // 要右旋的节点是个左孩子
                   pp.left = l; // 同上
               l.right = p; // 要右旋的节点 作为 他左孩子的右节点
               p.parent = l; // 要右旋的节点的父节点 指向 他的左孩子
           }
           return root;
       }


       /**
        * 红黑树插入节点后,需要重新平衡
        * root 当前根节点
        * x 新插入的节点
        * 返回重新平衡后的根节点
        */
       static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                           TreeNode<K,V> x) {
           x.red = true; // 新插入的节点标为红色
        
           /*
            * 这一步即定义了变量,又开起了循环,循环没有控制条件,只能从内部跳出
            * xp:当前节点的父节点、xpp:爷爷节点、xppl:左叔叔节点、xppr:右叔叔节点
            */
           for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 
        
               // 如果父节点为空、说明当前节点就是根节点,那么把当前节点标为黑色,返回当前节点
               if ((xp = x.parent) == null) { // L1
                   x.red = false;
                   return x;
               }
        
               // 父节点不为空
               // 如果父节点为黑色 或者 【(父节点为红色 但是 爷爷节点为空) -> 这种情况何时出现?】
               else if (!xp.red || (xpp = xp.parent) == null) // L2
                   return root;
               if (xp == (xppl = xpp.left)) { // 如果父节点是爷爷节点的左孩子  // L3
                   if ((xppr = xpp.right) != null && xppr.red) { // 如果右叔叔不为空 并且 为红色  // L3_1
                       xppr.red = false; // 右叔叔置为黑色
                       xp.red = false; // 父节点置为黑色
                       xpp.red = true; // 爷爷节点置为红色
                       x = xpp; // 运行到这里之后,就又会进行下一轮的循环了,将爷爷节点当做处理的起始节点 
                   }
                   else { // 如果右叔叔为空 或者 为黑色 // L3_2
                       if (x == xp.right) { // 如果当前节点是父节点的右孩子 // L3_2_1
                           root = rotateLeft(root, x = xp); // 父节点左旋,见下文左旋方法解析
                           xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                       }
                       if (xp != null) { // 如果父节点不为空 // L3_2_2
                           xp.red = false; // 父节点 置为黑色
                           if (xpp != null) { // 爷爷节点不为空
                               xpp.red = true; // 爷爷节点置为 红色
                               root = rotateRight(root, xpp);  //爷爷节点右旋,见下文右旋方法解析
                           }
                       }
                   }
               }
               else { // 如果父节点是爷爷节点的右孩子 // L4
                   if (xppl != null && xppl.red) { // 如果左叔叔是红色 // L4_1
                       xppl.red = false; // 左叔叔置为 黑色
                       xp.red = false; // 父节点置为黑色
                       xpp.red = true; // 爷爷置为红色
                       x = xpp; // 运行到这里之后,就又会进行下一轮的循环了,将爷爷节点当做处理的起始节点 
                   }
                   else { // 如果左叔叔为空或者是黑色 // L4_2
                       if (x == xp.left) { // 如果当前节点是个左孩子 // L4_2_1
                           root = rotateRight(root, x = xp); // 针对父节点做右旋,见下文右旋方法解析
                           xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
                       }
                       if (xp != null) { // 如果父节点不为空 // L4_2_4
                           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;
        }
    }
静态方法
  1. static final int hash(Object key) : HashMap中的hash函数。
  2. static Class<?> comparableClassFor(Object x): 判断参数x是否实现了Comparable接口。
  3. static int compareComparables(Class<?> kc, Object k, Object x): 如果x和kc类型相同,则返回k.compareTo(x)结果;否则返回0。
  4. static final int tableSizeFor(int cap): 返回大于等于该值的最近一个2的整数次幂的数。
   /**
     * hash求值,为key的hashCode值h与 h右移16位的值异或求值, 
     * 右移16将key的高位移到低位位置与低位进行异或运算,也是出于出于“均衡“考虑
     * 右移16位的16为位数也是除以时间空间性能考虑定的
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * 如果传入参数x实现了Comparable接口,则返回类x,否则返回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;
    }
非静态方法
构造方法
	 /**
     * 有初始化容量以及加载因子构造
     * initialCapacity 最大为 MAXIMUM_CAPACITY  加载因子一般来说大于0小于1
     */
    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)构造
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 空构造, 使用默认初始化容量(16)以及默认加载因子(0.75)
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 带Map数据构造,使用默认加载因子,容量根据Map数据条数具体进行初始化
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
putMapEntries(Map<? extends K, ? extends V> m, boolean evict)
    /**
     * 实现了Map.putAll和Map构造
     * 初始化map是evict为false,其余为true
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { 
                // 根据 threshold = capacity * loadFactor关系,算出s条数据对应的阈值,然后比对,如果结结果大于当前阈值,覆盖map阈值
                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)
                // 算出s条数据对应的阈值,然后比对,如果结结果大于当前阈值,进行扩容
                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);
            }
        }
    }
size()
isEmpty()

    /**
     * 返回map数据条数
     */
    public int size() {
        return size;
    }

    /**
     * 返回map是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }
get(Object key)
getNode(int hash, Object key)
containsKey(Object key)
    /**
     * Map.get()方法,返回结果有两种:null 以及 e.value,
     * 返回结果为null并不代表key不存在,可能e.value本身就为null(HashMap的key和value均可以为null), 
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * 实现Map.get()以及相关算法
     * (n - 1) & hash 理解: 
     *                  当n(n=tab.length)为2的N次幂时,(n - 1) & hash 相当于  hash % n
     *                  具体理解可以看:https://www.cnblogs.com/ysocean/p/9054804.html
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 总是从初始节点判断,基于性能考虑,有冲突的才会有下一个节点,
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    // 节点类型为红黑树节点,从红黑树中取值
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 链表取值
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
	 /**
     * 判断是否包含某key, 直接用某key去获取对应节点,节点为空则不包含该key
     */
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
put(K key, V value)
putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
putAll(Map<? extends K, ? extends V> m)
   

    /**
     * 添加元素方法, 如果map中已经包含了key, 那么该key的value值直接被覆盖掉
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * 实现了Map.put()以及相关方法
     * @param onlyIfAbsent 为true时,则不覆盖key对应的value值,但是put在调用这个方法时,赋值false,说明覆盖原始value.
     * @param evict 为false时,table处于创建模式.
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            // 如果table为null 或者 table.length == 0 主数组没有初始化, 进行扩容
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 数组对应索引节点为null, 直接添加未当前节点
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                // p为红黑树节点,调用红黑树插入元素方法
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // p为链表节点
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 链表末端插入数据
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 链表元素个数大于转化红黑树阈值,转为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //如果插入节点和原链表中的某个key具有相同的hash且key相同,停止查找.
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // 替换原value值
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //map结构更改次数+1
        ++modCount;
        //键值对个数>阈值,扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
   /**
     * 将指定m中的键值对映射到调用putAll方法的map中.如果key有重复,则value值被覆盖.ll
     */
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
resize() : table数组初始化或者扩容
    /**
     * 初始化table的大小,或者进行扩容操作(大小增加一倍)
     * table为null,将table大小
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //以前的容量大于0,也就是hashMap中已经有元素了,或者new对象的时候设置了初始容量
        if (oldCap > 0) {
            //如果以前的容量大于限制的最大容量1<<30,则设置临界值为int的最大值2^31-1
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            /**
             * 如果以前容量的2倍小于限制的最大容量,同时大于或等于默认的容量16,则设置临界值为以前临界值的2
             * 倍,因为threshold = loadFactor*capacity,capacity扩大了2倍,loadFactor不变,
             * threshold自然也扩大2倍。
             */
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        /**
         * 在HashMap构造器Hash(int initialCapacity, float loadFactor)中有一句代码,this.threshold      
         * = tableSizeFor(initialCapacity), 表示在调用构造器时,默认是将初始容量暂时赋值给了
         * threshold临界值,因此此处相当于将上一次的初始容量赋值给了新的容量。什么情况下会执行到这句?当调用     
         * 了HashMap(int initialCapacity)构造器,还没有添加元素时
         */
        else if (oldThr > 0) 
            newCap = oldThr;
        /**
         * 调用了默认构造器,初始容量没有设置,因此使用默认容量DEFAULT_INITIAL_CAPACITY(16),临界值
         * 就是16*0.75
         */
        else {               
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //对临界值做判断,确保其不为0,因为在上面第二种情况(oldThr > 0),并没有计算newThr
        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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //将刚创建的新表赋值给table
        table = newTab;
        if (oldTab != null) {
            //遍历将原来table中的数据放到扩容后的新表中来
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //没有链表Node节点,直接放到新的table中下标为【e.hash & (newCap - 1)】位置即可
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果是treeNode节点,则树上的节点放到newTab中
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果e后面还有链表节点,则遍历e所在的链表,
                    else { // 保证顺序
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            //记录下一个节点
                            next = e.next;
                            /**
                             * newTab的容量是以前旧表容量的两倍,因为数组table下标并不是根据循环逐步递增
                             * 的,而是通过(table.length-1)& hash计算得到,因此扩容后,存放的位置就
                             * 可能发生变化,那么到底发生怎样的变化呢,就是由下面的算法得到.
                             *
                             * 通过e.hash & oldCap来判断节点位置通过再次hash算法后,是否会发生改变,如
                             * 果为0表示不会发生改变,如果为1表示会发生改变。到底怎么理解呢,举个例子:
                             * e.hash = 13 二进制:0000 1101
                             * oldCap = 32 二进制:0001 0000
                             *     &运算:  0 二进制:0000 0000
                             * 结论:元素位置在扩容后不会发生改变
                             */
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            /**
                             * e.hash = 18 二进制:0001 0010
                             * oldCap = 32 二进制:0001 0000
                             *    &运算:  32 二进制:0001 0000
                             * 结论:元素位置在扩容后会发生改变,那么如何改变呢?
                             * newCap = 64 二进制:0010 0000
                             * 通过(newCap-1)&hash
                             * 即0001 1111 
                             * &0001 0010 
                             * 得0001 0010,32+18 = 50
                             */
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            /**
                             * 若(e.hash & oldCap) == 0,下标不变,将原表某个下标的元素放到扩容表同样
                             * 下标的位置上
                             */
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            /**
                             * 若(e.hash & oldCap) != 0,将原表某个下标的元素放到扩容表中
                             * [下标+增加的扩容量]的位置上
                             */
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
treeifyBin(Node<K,V>[] tab, int hash) : 将桶数据的链表转化为红黑树
    /**
     * 将桶数据的链表转化为红黑树
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            // table 为null 或者 table数组太小,不转为红黑树,只进行初始化或者库扩容
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // 符合链表转为红黑树条件,且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);
        }
    }
remove(Object key) {
removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)
    /**
     *  删除指定key的数据
     */
    public V remove(Object key) {
        Node<K,V> e;
        /**
         * null:显然传入的value=null,说明需要忽略value,所以matchValue必定为false.
         * true:删除当前节点时,会移动其它节点.
         */
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    /**
     * Map.remove方法及其相关方法的实现
     * @param matchValue 如果为true,则删除一个node的条件是:key和value都一致,才删除.
     * @param 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;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            // 上面判断条件是table存在,且已经初始化,且key在table中节点不为null,代表key真实存在
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 删除节点为桶中链表第一个节点
                node = p;
            else if ((e = p.next) != null) {
                // 删除节点不为桶的链表第一个节点
                if (p instanceof TreeNode)
                    // 桶中节点为红黑树节点,查找该节点
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 桶中节点为链表节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            // 查找到删除节点,复制
                            node = e;
                            break;
                        }
                        // 记录删除节点的上级节点
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 删除节点存在,且不必对value值
                if (node instanceof TreeNode)
                    // 删除节点为红黑树节点, 使用红黑树删除节点方法
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    // 删除节点为桶的第一个节点,直接用删除节点下一个节点替换
                    tab[index] = node.next;
                else
                    // 删除node节点
                    p.next = node.next;
                //结构更改次数+1
                ++modCount;
                //键值对个数-1
                --size;
                //回调函数
                afterNodeRemoval(node);
                //返回删除节点
                return node;
            }
        }
        return null;
    }
clear()
    /**
     * 清空map,元素个数为0, 结构变化次数加一, table
     */
    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                // gc
                tab[i] = null;
        }
    }
containsValue(Object value)
   /**
     * 判断是否包含某值,使用双重循环,加链表.next实现
     */
    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;
    }
keySet()
    /**
     * 返回map中key的集合视图.
     * 这一集合由map做后台支撑,因此map中key的更改会影响key的Set集合,反之亦然.
     * 如果在key的集合迭代过程中,map中key被更改了,会产生什么结果并未定义.
     * 这一set支持删除元素,通过Iterator.remove(), Set.remove(),
     * removeAll(), retainAll(), clear()方法,会从map中删除整个条目.
     * 这一set不支持add()和addAll()方法.
     */
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
KeySet类
   /**
     * 继承于set骨架,实现的内部类
     */
    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();
            }
        }
    }

values()
    /**
     * 获取map中values的一个Collection视图.
     * 这个collection是以map作为后台支撑的,所以map中value的更改会影响这个collection,反之亦然.
     * 当迭代这个collection时,如果map发生了改变,迭代结果会受到什么影响并未定义.
     * 这个collection支持元素的删除,通过Iterator.remove(),
     * Collection.remove(), removeAll(),
     * retainAll(),clear()方法,均可进行删除,此时删除的是一个条目.
     * 这个collection不支持元素的添加,即为不支持add()和addAll()方法.
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }
Values类
    /**
     * 继续collection骨架,实现的内部类
     *
     */
    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();
            }
        }
    }
entrySet()
    /**
     * 返回map中条目的一个set.
     * 这个set后台由map支撑,故在结构上,二者互相影响.
     * 支持删除操作,不支持添加操作.
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
EntrySet类
    /**
     * 继承于set骨架,实现的内部类
     */
    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();
            }
        }
    }
clone()
    /**
     * 返回map实例的浅拷贝:key和value本身不会被clone,因为key和value均为对象.
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
        //将result实例的一些域进行赋值,要么为null,要么为0,这里的result将和map共享map的table,
        result.reinitialize();
        //使用map初始化result
        result.putMapEntries(this, false);
        return result;
    }
loadFactor()
  /**
   * 这些方法在序列化HasSet时,同样适用.
   */
  final float loadFactor() { return loadFactor; }
capacity()
 /**
  * 如果table不为null,返回容量为table的长度;
  * 如果table为null,如果阈值>0,返回容量为阈值;如果阈值<=0,返回默认初始化容量.
  */
 final int capacity() {
     return (table != null) ? table.length :
             (threshold > 0) ? threshold :
                     DEFAULT_INITIAL_CAPACITY;
 }
writeObject(java.io.ObjectOutputStream s)
readObject(java.io.ObjectInputStream s)
      /**
   * 保存当前HashMap实例到流中(如序列化时)
   * 序列化数据格式:
   * 1.HashMap的容量(=桶数组的长度).
   * 2.size(键值对个数)
   * 3.键值对(顺序不确定)
   */
  private void writeObject(java.io.ObjectOutputStream s)
          throws IOException {
      int buckets = capacity();
      // Write out the threshold, loadfactor, and any hidden stuff
      //写入:阈值,负载因子,其它隐藏信息
      s.defaultWriteObject();
      //写入:bucket个数(容量)
      s.writeInt(buckets);
      //写入size
      s.writeInt(size);
      //写入:键值对
      internalWriteEntries(s);
  }

  /**
   * 从流重建HashMap(如反序列化时)
   */
  private void readObject(java.io.ObjectInputStream s)
          throws IOException, ClassNotFoundException {
      //读取:阈值(忽略),负载因子,其它隐藏信息
      s.defaultReadObject();
      //初始化map,对HashMap的一些域初始化.
      reinitialize();
      //如果负载因子<=0 or 为非数字值,则抛出异常.
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new InvalidObjectException("Illegal load factor: " +
                  loadFactor);
      /**
       *读取buckets值,且忽略.
       * 忽略是什么意思?
       * 因为stream的读取必须是一个个二进制位的读取,所以读入顺序同序列化顺序一致.比如,必须先读取bucket才能读取size.
       * 所以虽然读取了bucket的值,但是只是为了整个流的读取,不会对这个值进行处理.
       */
      s.readInt();
      //读取size,并保存
      int mappings = s.readInt();
      //如果键值对个数<0,则抛出异常.
      if (mappings < 0)
          throw new InvalidObjectException("Illegal mappings count: " +
                  mappings);
      //如果键值对个数>0
      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;
          //根据fc进一步确定容量cap
          int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                  DEFAULT_INITIAL_CAPACITY :
                  (fc >= MAXIMUM_CAPACITY) ?
                          MAXIMUM_CAPACITY :
                          tableSizeFor((int)fc));
          //阈值=容量*负载因子
          float ft = (float)cap * lf;
          //根据ft确定阈值
          threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                  (int)ft : Integer.MAX_VALUE);
          //为table申请内存空间个数:cap
          @SuppressWarnings({"rawtypes","unchecked"})
          Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
          table = tab;

          //table建好后,将键值对拷贝到table中.
          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);
          }
      }
  }