精华内容
下载资源
问答
  • HashMap 源代码

    千次阅读 2015-11-18 16:50:36
    通过查看HashMap源代码,了解它的初始化容量、加载因子及最大容量,初始化机制,扩容机制,及底层实现,底层实现是桶/链表和桶/红黑树一起结合的

    1、简单介绍HashMap

    HashMap 的实例有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。

    加载因子:是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,

    则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。

    默认加载因子 (默认为0.75f): 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本
    (在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。
    在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。
    如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。


    2、初始化容量、加载因子及最大容量

        /**
         * The default initial capacity - MUST be a power of two.
         */
        //默认的初始化容量,为16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         */
        //最大容量为 2^30
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * The load factor used when none specified in constructor.
         */
        //默认加载因子为 0.75f
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

    3、初始化机制

    初始化的容量一定为2的n次方,比如:cap为65个,则初始化容量为2^n,n满足 2^(n-1) < cap <=2^n

    代码如下

        /**
         * Returns a power of two size for the given target capacity.
         */
        //初始化机制
        static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

    4、扩容机制

    源代码中有个阀值 threshold = cap * loadFactor,当插入键值对后,当前容量超过threshold,则扩容, 扩容为原来的2倍

    newCap = oldCap << 1

    5、底层实现

    JDK8中新增的特性,以前都是用桶/链表来实现HashMap的,现在添加一个键值对,当添加的桶的个数到达TREEIFY_THRESHOLD(8),则检测HashMap中桶数,如果到达MIN_TREEIFY_CAPACITY(64),则底层改为桶/红黑树来实现

    代码如下

        /**
         * The bin count threshold for using a tree rather than list for a
         * bin.  Bins are converted to trees when adding an element to a
         * bin with at least this many nodes. The value must be greater
         * than 2 and should be at least 8 to mesh with assumptions in
         * tree removal about conversion back to plain bins upon
         * shrinkage.
         */
        //当桶中的键值对数量到达8个,且桶数量大于等于64,则将底层实现从链表转为红黑树
        // 如果桶中的键值对到达该阀值,则检测桶数量
        static final int TREEIFY_THRESHOLD = 8;
        /**
         * The smallest table capacity for which bins may be treeified.
         * (Otherwise the table is resized if too many nodes in a bin.)
         * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
         * between resizing and treeification thresholds.
         */
        //当所有键值对到达64个的时候,则将链表转为红黑树
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            //如果同数量大于阀值,则调用treeifyBin方法,当桶数量大于64则需要将底层实现改为红黑树,
            // 如果桶数量不到64则重构一下链表
            treeifyBin(tab, hash);
    
        /**
         * Replaces all linked nodes in bin at index for given hash unless
         * table is too small, in which case resizes instead.
         */
        //当桶的数量太多的时候,底层则改为红黑树实现
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            //当桶的数量有 MIN_TREEIFY_CAPACITY (64)个时才将链表改为红黑树
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                //节点太少则resize()
                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);
            }
        }


    6、红黑树源代码

    里面的插入、删除,情况几的标记是结合维基百科中的红黑树文章中的插入、删除分的几种情况,该文链接:维基百科中的红黑树

     /* ------------------------------------------------------------ */
        // 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.
         */
        /*
        性质1. 节点是红色或黑色。
        性质2. 根是黑色。
        性质3. 所有叶子都是黑色(叶子是NIL节点)。
        性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
        性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
         */
        //红黑树实现类
        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表示红节点,false表示黑节点
            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.
             */
            //确保root是桶中的第一个元素
            //将root移到中中的第一个
            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) {
                        //root不是桶中第一个元素
                        Node<K,V> rn;
                        //将桶中的第一个元素设置为root
                        tab[index] = root;
                        TreeNode<K,V> rp = root.prev;
                        //将结点root删掉,rn.prev = rp; rp.next = rn;
                        if ((rn = root.next) != null)
                            ((TreeNode<K,V>)rn).prev = rp;
                        if (rp != null)
                            rp.next = rn;
                        //将first插入到root后面
                        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.
             */
            //查找hash为h,key为k的节点
            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)
                        //h小于节点的hash值,则找左节点
                        p = pl;
                    else if (ph < h)
                        //h大于结点的hash值,则找右节点
                        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.
             */
            //比较2个对象的大小
            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)))
                        //键值对为root,则返回
                        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) {
                        //插入 情形1:插入的是根节点,将颜色设为黑色,其他不用处理
                        x.red = false;
                        return x;
                    }
                    else if (!xp.red || (xpp = xp.parent) == null)
                        //插入 情形2:插入的节点的父节点是黑色,不用处理
                        return root;
                    if (xp == (xppl = xpp.left)) {
                        //对称的,该部分是插入到左边的树
                        if ((xppr = xpp.right) != null && xppr.red) {
                            //插入 情形3:将父节点和叔节点设为黑色,将祖父设为红色
                            xppr.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            if (x == xp.right) {
                                //插入 情形4:需要左旋转一次
                                root = rotateLeft(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            if (xp != null) {
                                //插入 情形5:需要右旋一次
                                xp.red = false;
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateRight(root, xpp);
                                }
                            }
                        }
                    }
                    else {
                        //对称的,该部分是插入到右边的树
                        if (xppl != null && xppl.red) {
                            //插入 情形3
                            xppl.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            if (x == xp.left) {
                                //插入 情形4
                                root = rotateRight(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            if (xp != null) {
                                //插入 情形5
                                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)
                        //删除 情况1:根节点,不需要调整
                        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) {
                            //删除 情况2
                            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)) {
                                //删除 情况3
                                xpr.red = true;
                                x = xp;
                            }
                            else {
                                if (sr == null || !sr.red) {
                                    //删除 情况5
                                    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) {
                                    //删除 情况6
                                    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;
            }
        }



    7、源代码


    /*
     * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
     * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     *
     */
    
    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;
    
    /**
     * Hash table based implementation of the <tt>Map</tt> interface.  This
     * implementation provides all of the optional map operations, and permits
     * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
     * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
     * unsynchronized and permits nulls.)  This class makes no guarantees as to
     * the order of the map; in particular, it does not guarantee that the order
     * will remain constant over time.
     *
     * <p>This implementation provides constant-time performance for the basic
     * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
     * disperses the elements properly among the buckets.  Iteration over
     * collection views requires time proportional to the "capacity" of the
     * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
     * of key-value mappings).  Thus, it's very important not to set the initial
     * capacity too high (or the load factor too low) if iteration performance is
     * important.
     *
     * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
     * performance: <i>initial capacity</i> and <i>load factor</i>.  The
     * <i>capacity</i> is the number of buckets in the hash table, and the initial
     * capacity is simply the capacity at the time the hash table is created.  The
     * <i>load factor</i> is a measure of how full the hash table is allowed to
     * get before its capacity is automatically increased.  When the number of
     * entries in the hash table exceeds the product of the load factor and the
     * current capacity, the hash table is <i>rehashed</i> (that is, internal data
     * structures are rebuilt) so that the hash table has approximately twice the
     * number of buckets.
     *
     * <p>As a general rule, the default load factor (.75) offers a good
     * tradeoff between time and space costs.  Higher values decrease the
     * space overhead but increase the lookup cost (reflected in most of
     * the operations of the <tt>HashMap</tt> class, including
     * <tt>get</tt> and <tt>put</tt>).  The expected number of entries in
     * the map and its load factor should be taken into account when
     * setting its initial capacity, so as to minimize the number of
     * rehash operations.  If the initial capacity is greater than the
     * maximum number of entries divided by the load factor, no rehash
     * operations will ever occur.
     *
     * <p>If many mappings are to be stored in a <tt>HashMap</tt>
     * instance, creating it with a sufficiently large capacity will allow
     * the mappings to be stored more efficiently than letting it perform
     * automatic rehashing as needed to grow the table.  Note that using
     * many keys with the same {@code hashCode()} is a sure way to slow
     * down performance of any hash table. To ameliorate impact, when keys
     * are {@link Comparable}, this class may use comparison order among
     * keys to help break ties.
     *
     * <p><strong>Note that this implementation is not synchronized.</strong>
     * If multiple threads access a hash map concurrently, and at least one of
     * the threads modifies the map structurally, it <i>must</i> be
     * synchronized externally.  (A structural modification is any operation
     * that adds or deletes one or more mappings; merely changing the value
     * associated with a key that an instance already contains is not a
     * structural modification.)  This is typically accomplished by
     * synchronizing on some object that naturally encapsulates the map.
     *
     * If no such object exists, the map should be "wrapped" using the
     * {@link Collections#synchronizedMap Collections.synchronizedMap}
     * method.  This is best done at creation time, to prevent accidental
     * unsynchronized access to the map:<pre>
     *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
     *
     * <p>The iterators returned by all of this class's "collection view methods"
     * are <i>fail-fast</i>: if the map is structurally modified at any time after
     * the iterator is created, in any way except through the iterator's own
     * <tt>remove</tt> method, the iterator will throw a
     * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
     * modification, the iterator fails quickly and cleanly, rather than risking
     * arbitrary, non-deterministic behavior at an undetermined time in the
     * future.
     *
     * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
     * as it is, generally speaking, impossible to make any hard guarantees in the
     * presence of unsynchronized concurrent modification.  Fail-fast iterators
     * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
     * Therefore, it would be wrong to write a program that depended on this
     * exception for its correctness: <i>the fail-fast behavior of iterators
     * should be used only to detect bugs.</i>
     *
     * <p>This class is a member of the
     * <a href="{@docRoot}/../technotes/guides/collections/index.html">
     * Java Collections Framework</a>.
     *
     * @param <K> the type of keys maintained by this map
     * @param <V> the type of mapped values
     *
     * @author  Doug Lea
     * @author  Josh Bloch
     * @author  Arthur van Hoff
     * @author  Neal Gafter
     * @see     Object#hashCode()
     * @see     Collection
     * @see     Map
     * @see     TreeMap
     * @see     Hashtable
     * @since   1.2
     */
    /*
    基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。
    (除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,
    特别是它不保证该顺序恒久不变。
    
    此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。
    迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。
    所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。
    
    HashMap 的实例有两个参数影响其性能:初始容量 和加载因子。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。
    加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,
    则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
    
    通常,默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本
    (在大多数 HashMap 类的操作中,包括 get 和 put 操作,都反映了这一点)。
    在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。
    如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。
    
    如果很多映射关系要存储在 HashMap 实例中,则相对于按需执行自动的 rehash 操作以增大表的容量来说,
    使用足够大的初始容量创建它将使得映射关系能更有效地存储。
    
    注意,此实现不是同步的。如果多个线程同时访问一个哈希映射,而其中至少一个线程从结构上修改了该映射,
    则它必须 保持外部同步。(结构上的修改是指添加或删除一个或多个映射关系的任何操作;
    仅改变与实例已经包含的键关联的值不是结构上的修改。)这一般通过对自然封装该映射的对象进行同步操作来完成。
    如果不存在这样的对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
    最好在创建时完成这一操作,以防止对映射进行意外的非同步访问,如下所示:
    
       Map m = Collections.synchronizedMap(new HashMap(...));
    由所有此类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,
    如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,
    迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,
    而不冒在将来不确定的时间发生任意不确定行为的风险。
    
    注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,
    不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。
    因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
     */
    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
    
        private static final long serialVersionUID = 362498820763181265L;
    
        /*
         * Implementation notes.
         *
         * This map usually acts as a binned (bucketed) hash table, but
         * when bins get too large, they are transformed into bins of
         * TreeNodes, each structured similarly to those in
         * java.util.TreeMap. Most methods try to use normal bins, but
         * relay to TreeNode methods when applicable (simply by checking
         * instanceof a node).  Bins of TreeNodes may be traversed and
         * used like any others, but additionally support faster lookup
         * when overpopulated. However, since the vast majority of bins in
         * normal use are not overpopulated, checking for existence of
         * tree bins may be delayed in the course of table methods.
         *
         * Tree bins (i.e., bins whose elements are all TreeNodes) are
         * ordered primarily by hashCode, but in the case of ties, if two
         * elements are of the same "class C implements Comparable<C>",
         * type then their compareTo method is used for ordering. (We
         * conservatively check generic types via reflection to validate
         * this -- see method comparableClassFor).  The added complexity
         * of tree bins is worthwhile in providing worst-case O(log n)
         * operations when keys either have distinct hashes or are
         * orderable, Thus, performance degrades gracefully under
         * accidental or malicious usages in which hashCode() methods
         * return values that are poorly distributed, as well as those in
         * which many keys share a hashCode, so long as they are also
         * Comparable. (If neither of these apply, we may waste about a
         * factor of two in time and space compared to taking no
         * precautions. But the only known cases stem from poor user
         * programming practices that are already so slow that this makes
         * little difference.)
         *
         * Because TreeNodes are about twice the size of regular nodes, we
         * use them only when bins contain enough nodes to warrant use
         * (see TREEIFY_THRESHOLD). And when they become too small (due to
         * removal or resizing) they are converted back to plain bins.  In
         * usages with well-distributed user hashCodes, tree bins are
         * rarely used.  Ideally, under random hashCodes, the frequency of
         * nodes in bins follows a Poisson distribution
         * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
         * parameter of about 0.5 on average for the default resizing
         * threshold of 0.75, although with a large variance because of
         * resizing granularity. Ignoring variance, the expected
         * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
         * factorial(k)). The first values are:
         *
         * 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
         * more: less than 1 in ten million
         *
         * The root of a tree bin is normally its first node.  However,
         * sometimes (currently only upon Iterator.remove), the root might
         * be elsewhere, but can be recovered following parent links
         * (method TreeNode.root()).
         *
         * All applicable internal methods accept a hash code as an
         * argument (as normally supplied from a public method), allowing
         * them to call each other without recomputing user hashCodes.
         * Most internal methods also accept a "tab" argument, that is
         * normally the current table, but may be a new or old one when
         * resizing or converting.
         *
         * When bin lists are treeified, split, or untreeified, we keep
         * them in the same relative access/traversal order (i.e., field
         * Node.next) to better preserve locality, and to slightly
         * simplify handling of splits and traversals that invoke
         * iterator.remove. When using comparators on insertion, to keep a
         * total ordering (or as close as is required here) across
         * rebalancings, we compare classes and identityHashCodes as
         * tie-breakers.
         *
         * The use and transitions among plain vs tree modes is
         * complicated by the existence of subclass LinkedHashMap. See
         * below for hook methods defined to be invoked upon insertion,
         * removal and access that allow LinkedHashMap internals to
         * otherwise remain independent of these mechanics. (This also
         * requires that a map instance be passed to some utility methods
         * that may create new nodes.)
         *
         * The concurrent-programming-like SSA-based coding style helps
         * avoid aliasing errors amid all of the twisty pointer operations.
         */
    
        /**
         * The default initial capacity - MUST be a power of two.
         */
        //默认的初始化容量,为16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         */
        //最大容量为 2^30
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * The load factor used when none specified in constructor.
         */
        //默认加载因子为 0.75f
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         * The bin count threshold for using a tree rather than list for a
         * bin.  Bins are converted to trees when adding an element to a
         * bin with at least this many nodes. The value must be greater
         * than 2 and should be at least 8 to mesh with assumptions in
         * tree removal about conversion back to plain bins upon
         * shrinkage.
         */
        //当桶中的键值对数量到达8个,且桶数量大于等于64,则将底层实现从链表转为红黑树
        // 如果桶中的键值对到达该阀值,则检测桶数量
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * The bin count threshold for untreeifying a (split) bin during a
         * resize operation. Should be less than TREEIFY_THRESHOLD, and at
         * most 6 to mesh with shrinkage detection under removal.
         */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /**
         * The smallest table capacity for which bins may be treeified.
         * (Otherwise the table is resized if too many nodes in a bin.)
         * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
         * between resizing and treeification thresholds.
         */
        //当桶数量到达64个的时候,则将链表转为红黑树
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        /**
         * Basic hash bin node, used for most entries.  (See below for
         * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
         */
        //HashMap中节点的类
        static class Node<K,V> implements Map.Entry<K,V> {
            //结点的哈希值,不可变
            final int hash;
            //结点的key,不可变
            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;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            //将key和value的哈希值去异或
            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;
            }
    
            //判断2个结点是否相同
            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;
            }
        }
    
        /* ---------------- Static utilities -------------- */
    
        /**
         * Computes key.hashCode() and spreads (XORs) higher bits of hash
         * to lower.  Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         */
        static final int hash(Object key) {
            int h;
            //将key的哈希值h 与 h右移16位的值 去异或
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
        /**
         * Returns x's Class if it is of the form "class C implements
         * Comparable<C>", else null.
         */
        static Class<?> comparableClassFor(Object x) {
            if (x instanceof Comparable) {
                Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
                if ((c = x.getClass()) == String.class) // bypass checks
                    return c;
                if ((ts = c.getGenericInterfaces()) != null) {
                    for (int i = 0; i < ts.length; ++i) {
                        if (((t = ts[i]) instanceof ParameterizedType) &&
                            ((p = (ParameterizedType)t).getRawType() ==
                             Comparable.class) &&
                            (as = p.getActualTypeArguments()) != null &&
                            as.length == 1 && as[0] == c) // type arg is c
                            return c;
                    }
                }
            }
            return null;
        }
    
        /**
         * Returns k.compareTo(x) if x matches kc (k's screened comparable
         * class), else 0.
         */
        @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
        static int compareComparables(Class<?> kc, Object k, Object x) {
            return (x == null || x.getClass() != kc ? 0 :
                    ((Comparable)k).compareTo(x));
        }
    
        /**
         * Returns a power of two size for the given target capacity.
         */
        //初始化机制
        static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    
        /* ---------------- Fields -------------- */
    
        /**
         * The table, initialized on first use, and resized as
         * necessary. When allocated, length is always a power of two.
         * (We also tolerate length zero in some operations to allow
         * bootstrapping mechanics that are currently not needed.)
         */
        //存放节点的缓冲,哈希表的桶
        transient Node<K,V>[] table;
    
        /**
         * Holds cached entrySet(). Note that AbstractMap fields are used
         * for keySet() and values().
         */
        //指向调用entrySet()返回的对象
        transient Set<Map.Entry<K,V>> entrySet;
    
        /**
         * The number of key-value mappings contained in this map.
         */
        //键值对的容量
        transient int size;
    
        /**
         * The number of times this HashMap has been structurally modified
         * Structural modifications are those that change the number of mappings in
         * the HashMap or otherwise modify its internal structure (e.g.,
         * rehash).  This field is used to make iterators on Collection-views of
         * the HashMap fail-fast.  (See ConcurrentModificationException).
         */
        //检测并发修改的标志参数
        transient int modCount;
    
        /**
         * The next size value at which to 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;
    
        /**
         * The load factor for the hash table.
         *
         * @serial
         */
        //加载因子
        final float loadFactor;
    
        /* ---------------- Public operations -------------- */
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and load factor.
         *
         * @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);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        /**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         *
         * @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;
            //将m的键值对赋到本HashMap中
            putMapEntries(m, false);
        }
    
        /**
         * Implements Map.putAll and Map constructor
         *
         * @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);
                }
            }
        }
    
        /**
         * Returns the number of key-value mappings in this map.
         *
         * @return the number of key-value mappings in this map
         */
        //返回键值对的数量
        public int size() {
            return size;
        }
    
        /**
         * Returns <tt>true</tt> if this map contains no key-value mappings.
         *
         * @return <tt>true</tt> if this map contains no key-value mappings
         */
        //判断是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * Returns the value to which the specified key is mapped,
         * or {@code null} if this map contains no mapping for the key.
         *
         * <p>More formally, if this map contains a mapping from a key
         * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
         * key.equals(k))}, then this method returns {@code v}; otherwise
         * it returns {@code null}.  (There can be at most one such mapping.)
         *
         * <p>A return value of {@code null} does not <i>necessarily</i>
         * indicate that the map contains no mapping for the key; it's also
         * possible that the map explicitly maps the key to {@code null}.
         * The {@link #containsKey containsKey} operation may be used to
         * distinguish these two cases.
         *
         * @see #put(Object, Object)
         */
        //根据key获取相应的value
        public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
        /**
         * Implements Map.get and related methods
         *
         * @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;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    //那个桶的第一个键值对,检测一下是否就是这个元素
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        //如果是TreeNode,则调用getTreeNode
                        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;
        }
    
        /**
         * Returns <tt>true</tt> if this map contains a mapping for the
         * specified key.
         *
         * @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.
         */
        //判断map是否有key的键
        public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }
    
        /**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @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);
        }
    
        /**
         * Implements Map.put and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @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;
            if ((tab = table) == null || (n = tab.length) == 0)
                //如果table为空,则初始化
                n = (tab = resize()).length;
    
            if ((p = tab[i = (n - 1) & hash]) == null)
                //第i个桶没有元素,直接添加到tab[i]
                tab[i] = newNode(hash, key, value, null);
            else {
                //tab[i]有元素,则需要遍历结点后再添加
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    //刚好桶顶是key相同的值
                    e = p;
                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) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                //如果桶中结点数量(也即是链表的长度)大于阀值,则调用treeifyBin方法,当桶数量大于64则需要将底层实现改为红黑树,
                                // 如果数量不到64则重构一下链表
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    //存在有键为key的键值对,重新设值value
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //并发标志参数+1
            ++modCount;
            //添加后再检测是否到了阀值
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
        /**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new 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;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    //如果容量大于最大容量,则阀值设置为Integer.MAX_VALUE
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //阀值设置为原来2倍
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                //阀值大于0,则将新的容量newCap设为阀值
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                //初始化时为默认
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                //新阀值为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 = newTab;
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        //将旧的桶设为空,方便垃圾回收器回收
                        oldTab[j] = null;
                        //如果该桶只有一个元素,则直接赋到新的桶里面
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            //如果是红黑树,则调用红黑树自己的封装方法
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            //桶中有多个元素,遍历将它们链接到相应的位置
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    //还是在原来的桶的键值对
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    //不在原来桶的键值对
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {
                                //放在原来的桶
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                //放在非原来的桶
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }
    
        /**
         * Replaces all linked nodes in bin at index for given hash unless
         * table is too small, in which case resizes instead.
         */
        //当桶的数量太多的时候,底层则改为红黑树实现
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            //当桶的数量有 MIN_TREEIFY_CAPACITY (64)个时才将链表改为红黑树
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                //桶太少则resize()
                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);
            }
        }
    
        /**
         * Copies all of the mappings from the specified map to this map.
         * These mappings will replace any mappings that this map had for
         * any of the keys currently in the specified map.
         *
         * @param m mappings to be stored in this map
         * @throws NullPointerException if the specified map is null
         */
        //将m的键值对添加到当前的map
        public void putAll(Map<? extends K, ? extends V> m) {
            putMapEntries(m, true);
        }
    
        /**
         * Removes the mapping for the specified key from this map if present.
         *
         * @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;
        }
    
        /**
         * Implements Map.remove and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to match if matchValue, else ignored
         * @param matchValue if true only remove if value is equal
         * @param movable if false do not move other nodes while removing
         * @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;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
                //找到对应的桶
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    //等于桶第一个键值对
                    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)))) {
                    //找到了要remove的键值对
                    if (node instanceof TreeNode)
                        //底层结构为红黑树
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        //要remove的键值对为桶第一个元素
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    //容量减1
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }
    
        /**
         * Removes all of the mappings from this map.
         * The map will be empty after this call returns.
         */
        //清除掉键值对
        public void clear() {
            Node<K,V>[] tab;
            modCount++;
            if ((tab = table) != null && size > 0) {
                size = 0;
                //将桶清为null,桶中的链表也就成为垃圾了,因为根据可达性分析,链表都已经是不可达了
                for (int i = 0; i < tab.length; ++i)
                    tab[i] = null;
            }
        }
    
        /**
         * Returns <tt>true</tt> if this map maps one or more keys to the
         * specified value.
         *
         * @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
         */
        //判断是否包含值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;
        }
    
        /**
         * Returns a {@link Set} view of the keys contained in this map.
         * The set is backed by the map, so changes to the map are
         * reflected in the set, and vice-versa.  If the map is modified
         * while an iteration over the set is in progress (except through
         * the iterator's own <tt>remove</tt> operation), the results of
         * the iteration are undefined.  The set supports element removal,
         * which removes the corresponding mapping from the map, via the
         * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
         * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
         * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
         * operations.
         *
         * @return a set view of the keys contained in this map
         */
        //返回所有键组成的Set
        public Set<K> keySet() {
            Set<K> ks;
            return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
        }
    
        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)
                            //遍历将每一个key都传都到action中
                            action.accept(e.key);
                    }
                    if (modCount != mc)
                        throw new ConcurrentModificationException();
                }
            }
        }
    
        /**
         * Returns a {@link Collection} view of the values contained in this map.
         * The collection is backed by the map, so changes to the map are
         * reflected in the collection, and vice-versa.  If the map is
         * modified while an iteration over the collection is in progress
         * (except through the iterator's own <tt>remove</tt> operation),
         * the results of the iteration are undefined.  The collection
         * supports element removal, which removes the corresponding
         * mapping from the map, via the <tt>Iterator.remove</tt>,
         * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
         * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
         * support the <tt>add</tt> or <tt>addAll</tt> operations.
         *
         * @return a view of the values contained in this map
         */
        //将所有value都存到集合里面
        public Collection<V> values() {
            Collection<V> vs;
            return (vs = values) == null ? (values = new Values()) : vs;
        }
    
        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
                            action.accept(e.value);
                    }
                    if (modCount != mc)
                        throw new ConcurrentModificationException();
                }
            }
        }
    
        /**
         * Returns a {@link Set} view of the mappings contained in this map.
         * The set is backed by the map, so changes to the map are
         * reflected in the set, and vice-versa.  If the map is modified
         * while an iteration over the set is in progress (except through
         * the iterator's own <tt>remove</tt> operation, or through the
         * <tt>setValue</tt> operation on a map entry returned by the
         * iterator) the results of the iteration are undefined.  The set
         * supports element removal, which removes the corresponding
         * mapping from the map, via the <tt>Iterator.remove</tt>,
         * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
         * <tt>clear</tt> operations.  It does not support the
         * <tt>add</tt> or <tt>addAll</tt> operations.
         *
         * @return a set view of the mappings contained in this map
         */
        //将所有键值对转为Set
        public Set<Map.Entry<K,V>> entrySet() {
            Set<Map.Entry<K,V>> es;
            return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
        }
    
        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
                            action.accept(e);
                    }
                    if (modCount != mc)
                        throw new ConcurrentModificationException();
                }
            }
        }
    
        // Overrides of JDK8 Map extension methods
    
        //找键为key的值value
        @Override
        public V getOrDefault(Object key, V defaultValue) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
        }
    
        //将键值对put到map中
        @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;
        }
    
        @Override
        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;
                }
            }
            //如果没有该key的键值对
            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;
        }
    
        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;
        }
    
        @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) {
                //有该key的键值对
                V v;
                if (old.value != null)
                    //通过oldValue和value计算得到新value
                    v = remappingFunction.apply(old.value, value);
                else
                    v = value;
                if (v != null) {
                    //设置新value
                    old.value = v;
                    afterNodeAccess(old);
                }
                else
                    //新value为null,则remove键值对
                    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
                        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
    
        /**
         * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
         * values themselves are not cloned.
         *
         * @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;
        }
    
        /**
         * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
         * serialize it).
         *
         * @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.
         */
        //序列化 writeObject
        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);
        }
    
        /**
         * Reconstitute the {@code HashMap} instance from a stream (i.e.,
         * deserialize it).
         */
        //序列化 readObject
        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> {
            //获取下一个key
            public final K next() { return nextNode().key; }
        }
    
        final class ValueIterator extends HashIterator
            implements Iterator<V> {
            //获取下一个value
            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.
         */
        /*
        性质1. 节点是红色或黑色。
        性质2. 根是黑色。
        性质3. 所有叶子都是黑色(叶子是NIL节点)。
        性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
        性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
         */
        //红黑树实现类
        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表示红节点,false表示黑节点
            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.
             */
            //确保root是桶中的第一个元素
            //将root移到中中的第一个
            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) {
                        //root不是桶中第一个元素
                        Node<K,V> rn;
                        //将桶中的第一个元素设置为root
                        tab[index] = root;
                        TreeNode<K,V> rp = root.prev;
                        //将结点root删掉,rn.prev = rp; rp.next = rn;
                        if ((rn = root.next) != null)
                            ((TreeNode<K,V>)rn).prev = rp;
                        if (rp != null)
                            rp.next = rn;
                        //将first插入到root后面
                        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.
             */
            //查找hash为h,key为k的节点
            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)
                        //h小于节点的hash值,则找左节点
                        p = pl;
                    else if (ph < h)
                        //h大于结点的hash值,则找右节点
                        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.
             */
            //比较2个对象的大小
            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)))
                        //键值对为root,则返回
                        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) {
                        //插入 情形1:插入的是根节点,将颜色设为黑色,其他不用处理
                        x.red = false;
                        return x;
                    }
                    else if (!xp.red || (xpp = xp.parent) == null)
                        //插入 情形2:插入的节点的父节点是黑色,不用处理
                        return root;
                    if (xp == (xppl = xpp.left)) {
                        //对称的,该部分是插入到左边的树
                        if ((xppr = xpp.right) != null && xppr.red) {
                            //插入 情形3:将父节点和叔节点设为黑色,将祖父设为红色
                            xppr.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            if (x == xp.right) {
                                //插入 情形4:需要左旋转一次
                                root = rotateLeft(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            if (xp != null) {
                                //插入 情形5:需要右旋一次
                                xp.red = false;
                                if (xpp != null) {
                                    xpp.red = true;
                                    root = rotateRight(root, xpp);
                                }
                            }
                        }
                    }
                    else {
                        //对称的,该部分是插入到右边的树
                        if (xppl != null && xppl.red) {
                            //插入 情形3
                            xppl.red = false;
                            xp.red = false;
                            xpp.red = true;
                            x = xpp;
                        }
                        else {
                            if (x == xp.left) {
                                //插入 情形4
                                root = rotateRight(root, x = xp);
                                xpp = (xp = x.parent) == null ? null : xp.parent;
                            }
                            if (xp != null) {
                                //插入 情形5
                                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)
                        //删除 情况1:根节点,不需要调整
                        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) {
                            //删除 情况2
                            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)) {
                                //删除 情况3
                                xpr.red = true;
                                x = xp;
                            }
                            else {
                                if (sr == null || !sr.red) {
                                    //删除 情况5
                                    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) {
                                    //删除 情况6
                                    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;
            }
        }
    
    }
    


    展开全文
  • HashMap源代码

    2016-05-30 20:21:19
    HashMap是最常使用的类,所以学习它的源码很重要。 HashMap的结构如下: /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table = (Entry[]) EMPTY_TABLE...

    HashMap是最常使用的类,所以学习它的源码很重要。

    HashMap的结构如下:


    /**
         * The table, resized as necessary. Length MUST Always be a power of two.
         */
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

    由Entry[] table负责存储数据。其中Entry是它的静态内部类,Entry结构如下:

    static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
    很明显可以看出,Entry就是一个链表,所以HashMap的结构其实就是一个数组,然后数组里面的元素是链表,如下图所示:


    HashMap中最常使用的方法是get和put,首先看下put方法

    public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)//允许null key
                return putForNullKey(value);
            int hash = hash(key);//对key进行hash
            int i = indexFor(hash, table.length);//通过hash值找到对应存储位置
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {//遍历链元素,查找链表中有没有相同的key,如果有就替换
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//先比较hash,如果hash值相等,再比较具体的key值
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);//如果没有key,就做插入
            return null;
        }

    private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {//大体过程与普通put操作一样,只不过要注意如果是null key就存储在0位置
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }

    get方法:

    public V get(Object key) {
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
    
            return null == entry ? null : entry.getValue();
        }
    private V getForNullKey() {
            if (size == 0) {
                return null;
            }
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {//没什么好说的,就要注意null key的值存储在0位置
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
    final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
                return null;
            }
    
            int hash = (key == null) ? 0 : hash(key);//再次证明null key 在0位置
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }






    展开全文
  • JDK1.7-HashMap源代码注释版

    千次阅读 多人点赞 2020-07-05 09:19:19
    JDK1.7-HashMap源代码注释版

    我已加入CSDN合伙人计划

    亲爱的各位粉丝:可以添加我的CSDN官方企业微信号,和我近距离互动聊天,为您答疑解惑

    直接使用微信扫码即可,不用下载企业微信

    订阅之后,博主所有的专栏都可以学习查看,加入微信群有优惠哦,加入之后,找我返现哦
    在这里插入图片描述

    一、前言

    在学习java源码中,全是英文,看起来就有点费劲了,所以就把这些注释翻译了一遍。

    采用机器翻译,多少会有不准的地方。意思能看明白就可以了。

    这是我自己学习Hashmap源码的时候做的一件事。

    压缩包里存放着的和原来的是一样的:
    在这里插入图片描述

    二、效果

    在这里插入图片描述
    在这里插入图片描述

    中英对照:

    可以学英语,又可以学代码,两全其美
    在这里插入图片描述

    三、如何得到

    (一)有力的可用此方式

    有力的可以到这里下载:https://download.csdn.net/download/qq_17623363/12578222

    (二)无力的可用此方式

    无力的可以加入此微信群下载哦(完全免费提供给大家):

    我已加入CSDN合伙人计划

    亲爱的各位粉丝:可以添加我的CSDN官方企业微信号,和我近距离互动聊天,为您答疑解惑

    直接使用微信扫码即可,不用下载企业微信

    在这里插入图片描述

    四、关键代码实例

    
    /**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         *
         * 使用与指定Map相同的映射构造一个新的HashMap。
         * 使用默认的负载因子(0.75)和足以将映射保存在指定Map中的初始容量创建HashMap。
         *
         * @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(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                          DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
            inflateTable(threshold);
    
            putAllForCreate(m);
        }
    
        /*
        Integer.highestOneBit(15) = 8 :找到一个小于等于这个数的二的次方数
       为什么先把传入的值减一呢?
       如果传入的number是8,那么直接返回的就是8了,如果减一的话,number就等于7
       7: 0000 0111
       7 << 1 =  14 = 0001 0100  翻了一倍,这样的话,返回的结果就是翻倍后的这个数的最小的二次幂
        演算:
          0001 0100
          0001 0100 >> 1 = 0000 1010 ;
    
          0001 0100
      |   0000 1010
      =   0001 1110
    
          0001 1110 >> 2 =  0000 0111
    
          0001 1110
         |0000 0111
         =0001 1111
    
          0001 1111 >>> 1 =  0000 1111
    
          0001 1111
         -0000 1111
          0001 0000
    
          最终结果:(2)0001 0000 = (10)16
    
       */
        //向上舍入为2的幂
        private static int roundUpToPowerOf2(int number) {
            // assert number >= 0 : "number must be non-negative";
            return number >= MAXIMUM_CAPACITY
                    ? MAXIMUM_CAPACITY
                    : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
        }
    /**
     * Inflates the table.
     * 初始化table数组
     */
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize  找一个 2 >= toSize的2的次方数
        int capacity = roundUpToPowerOf2(toSize);
    
        //扩容要用到的值
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //使用计算出来的值,初始化存储数据的数组
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }
    
    
        /**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         * 将指定值与该映射中的指定键相关联。
         * 如果该映射先前包含该key的映射,则将替换旧值。
         *
         * @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) {
            //先判断数组是不是一个空的,代表数组还未初始化;
            //类似懒加载,或者说是初始化,只有在put存元素的时候,才会真正的初始化里面的数组
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);//初始化的方法
            }
    
            if (key == null)
                return putForNullKey(value);
    
            int hash = hash(key);//计算一个哈希值
    
            int i = indexFor(hash, table.length);//计算索引位置 索引始终保持在0-table.length之间
    
            //for():为了查找是不是重复的,如果key是重复的,就去覆盖掉旧的key的值,把原来的key的值给返回
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            //如果没有重复的就继续执行
            modCount++;
            //      key的hash值,key,val,索引
            addEntry(hash, key, value, i);
            return null;
        }
    
    

    五、如何使用

    下载下来之后,需要先解压出来:
    在这里插入图片描述

    创建一个普通的java项目,把下载的src中的文件解压到这个项目中的src包下:
    在这里插入图片描述

    如果你是idea:
    在这里插入图片描述

    选择jdk1.7版本:

    在这里插入图片描述
    只需要按下面配置即可:
    在这里插入图片描述

    这样的话,就可以随时进行编辑了,想怎么注释就可以怎么注释。

    展开全文
  • Java HashMap源代码详解

    2019-10-08 04:09:44
    Java HashMap源代码详解 HashMap链地址法确定存储位置  将所有关键字为同义词的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间[0,m-1]上,则设立一个指针型向量Chain Chain Hash[m]; 其每个分量...

    Java HashMap源代码详解

    HashMap链地址法确定存储位置

      将所有关键字为同义词的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间[0,m-1]上,则设立一个指针型向量Chain Chain Hash[m];

    其每个分量的初始状态都是空指针。凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在列表中的插入位置可以在表头或表尾;也可以在中间,以保持同义词在同一线性表中按关键字有序。

      例如:已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),则按哈希函数H(key)=key MOD 13 和链地址法处理冲突构造所得的哈希表,如下图所示:

                               

    Hash map=New HashMap();

    HashMap基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor,以调整容器的性能。

    说明:

      数据存放在数组中,但物理存储是链式存储

      数组成员成为格子,且每个格子的hash值的唯一的

      每个格子可存放hash值相同的多对K-V,每对被称为桶(每个桶是唯一的即Map存放数据不可重复)

      格子中的桶与桶之间是通过指针连接的(Map是无序的)

    处理流程:

      1、创建默认初始容量16,加载因子 (0.75)

      2、通过public V put(K key, V value);先计算key的hash值,确定key所在的格子(如果为空则需要创建一个新桶存放K-V,不为空则覆盖旧桶)

      3、每次创建一个桶则size大小进行记录,并在创建新桶后进行判断size与threshold阈值变量比较,如果size>threshold则需要扩充格子容量原来的2倍。

    HashMap源码

      1 package java2.util2;
      2 
      3 import java.io.IOException;
      4 import java.io.Serializable;
      5 import java.util.AbstractCollection;
      6 import java.util.AbstractSet;
      7 import java.util.Collection;
      8 import java.util.ConcurrentModificationException;
      9 import java.util.Iterator;
     10 import java.util.NoSuchElementException;
     11 import java.util.Set;
     12 /**
     13  * HashMap
     14  * @author wwl
     15  *
     16  * @param <K>
     17  * @param <V>
     18  */
     19 public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
     20         Cloneable, Serializable {
     21 
     22     // 系统默认初始容量,必须是2的n次幂,这是出于优化考虑的
     23     static final int DEFAULT_INITIAL_CAPACITY = 16;
     24 
     25     // 系统默认最大容量2的30次幂1073741824
     26     static final int MAXIMUM_CAPACITY = 1 << 30;
     27 
     28     // 系统默认负载因子,可在构造函数中指定
     29     static final float DEFAULT_LOAD_FACTOR = 0.75f;
     30 
     31     // 用于存储的表,长度可以调整,且必须是2的n次幂
     32     transient Entry[] table;
     33 
     34     // 当前map的key-value映射数,也就是当前size  
     35     transient int size;
     36 
     37     /**
     38      * 表示HashMap所能容纳的key-value对极限,如果存储的size数大于了threshold,则需要扩容了
     39      * 阈值 
     40      * @serial
     41      */
     42     int threshold;
     43 
     44     /**
     45      * 哈希表的负载因子  
     46      * loadFactor是负载因子,增大值时可以减少Hash表(也就是Entry数组)所占用的内存空间,
     47      * 但会增加查询数据时时间的开销,而查询是最频繁的操作,减小值时会提高数据查询的性能, 但是会增大Hash表所占用的内存空间,所以一般是默认的0.75
     48      * 
     49      * @serial
     50      */
     51     final float loadFactor;
     52 
     53     /**
     54      * 用于确保使用迭代器的时候,HashMap并未进行更改 
     55      */
     56     transient volatile int modCount;
     57 
     58     /**
     59      * 构造一个带指定初始容量和加载因子的空 HashMap
     60      * 
     61      * @param initialCapacity
     62      *            初始容量
     63      * @param loadFactor
     64      *            加载因子
     65      * @throws IllegalArgumentException
     66      *             if the initial capacity is negative or the load factor is
     67      *             nonpositive
     68      */
     69     public HashMap(int initialCapacity, float loadFactor) {
     70         // 如果指定初始容量小于0,抛错 
     71         if (initialCapacity < 0)
     72             throw new IllegalArgumentException("Illegal initial capacity: "
     73                     + initialCapacity);
     74         // 如果初始容量大于系统默认最大容量,则初始容量为最大容量 
     75         if (initialCapacity > MAXIMUM_CAPACITY)
     76             initialCapacity = MAXIMUM_CAPACITY;
     77         // 如果loadFactor小于0,或loadFactor是NaN,则抛错  
     78         if (loadFactor <= 0 || Float.isNaN(loadFactor))
     79             throw new IllegalArgumentException("Illegal load factor: "
     80                     + loadFactor);
     81         // 寻找一个2的k次幂capacity恰好大于initialCapacity
     82         int capacity = 1;
     83         while (capacity < initialCapacity)
     84             // 计算出大于initialCapacity的最小的2的n次方值
     85             capacity <<= 1;
     86 
     87         this.loadFactor = loadFactor;
     88         threshold = (int) (capacity * loadFactor);// 设置容量极限
     89         // 创建一个capacity长度的数组用于保存数据
     90         table = new Entry[capacity];
     91         init();
     92     }
     93 
     94     /**
     95      * 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
     96      * 
     97      * @param initialCapacity
     98      *            初始容量
     99      * @throws IllegalArgumentException
    100      *             if the initial capacity is negative.
    101      */
    102     public HashMap(int initialCapacity) {
    103         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    104     }
    105 
    106     /**
    107      * 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap
    108      */
    109     public HashMap() {
    110         this.loadFactor = DEFAULT_LOAD_FACTOR;
    111         threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    112         table = new Entry[DEFAULT_INITIAL_CAPACITY];
    113         init();
    114     }
    115 
    116     /**
    117      * 构造一个映射关系与指定 Map 相同的新 HashMap
    118      * 
    119      */
    120     public HashMap(Map<? extends K, ? extends V> m) {
    121         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
    122                 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    123         putAllForCreate(m);
    124     }
    125     /**
    126      * 初始化
    127      */
    128     void init() {
    129     }
    130 
    131     /**
    132      * HashMap的哈希函数
    133      * 预处理hash值,避免较差的离散hash序列
    134      * @param h
    135      * @return
    136      */
    137     static int hash(int h) {
    138         h ^= (h >>> 20) ^ (h >>> 12);
    139         return h ^ (h >>> 7) ^ (h >>> 4);
    140     }
    141 
    142     /**
    143      *  返回对应hash值得索引
    144      *  根据key的hash值获取哈希地址
    145      * @param h
    146      * @param length
    147      * @return
    148      */
    149     static int indexFor(int h, int length) {
    150         //由于length是2的n次幂,所以h & (length-1)相当于h % length
    151         return h & (length - 1);
    152     }
    153 
    154     /**
    155      * 返回当前map的key-value映射数,也就是当前size
    156      */
    157     public int size() {
    158         return size;
    159     }
    160     /**
    161      * 该HashMap是否是空的,如果size为0,则为空
    162      */
    163     public boolean isEmpty() {
    164         return size == 0;
    165     }
    166     /**
    167      * 返回指定键所映射的值;如果对于该键来说,此映射不包含任何映射关系,则返回 null
    168      * 先根据输入的key计算hash值,得出index,找到对应数组节点,在节点内的链表结构中遍历寻找所求数据
    169      */
    170     public V get(Object key) {
    171         if (key == null)
    172             return getForNullKey();
    173         int hash = hash(key.hashCode());
    174         // 得到对应的hash值的桶,如果这个桶不是,就通过next获取下一个桶
    175         for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    176             Object k;
    177             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    178                 return e.value;
    179         }
    180         return null;
    181     }
    182     /**
    183      * 如果要得到key为null的值,则通过这个获取
    184      * @return
    185      */
    186     private V getForNullKey() {
    187         for (Entry<K, V> e = table[0]; e != null; e = e.next) {
    188             if (e.key == null)
    189                 return e.value;
    190         }
    191         return null;
    192     }
    193 
    194     /**
    195      * 如果此映射包含对于指定键的映射关系,则返回 true
    196      */
    197     public boolean containsKey(Object key) {
    198         return getEntry(key) != null;
    199     }
    200 
    201     /**
    202      * 通过key获取一个value 
    203      */
    204     final Entry<K, V> getEntry(Object key) {
    205         // 如果key为null,则hash为0,否则用hash函数预处理
    206         int hash = (key == null) ? 0 : hash(key.hashCode());
    207         // 先得到对应的hash值的桶,再比较key值如果这个桶不是,就通过next获取下一个桶
    208         for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    209             Object k;
    210             if (e.hash == hash
    211                     && ((k = e.key) == key || (key != null && key.equals(k))))
    212                 return e;
    213         }
    214         return null;
    215     }
    216 
    217     /**
    218      * 存放K-V
    219      * 采用链地址法
    220      * 哈希值[0,m-1],先计算hash根据哈希存放到对应hash值桶中,可以存放多个相同的hash
    221      * 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系,则旧值被替换
    222      */
    223     public V put(K key, V value) {
    224         if (key == null)
    225             return putForNullKey(value);
    226         int hash = hash(key.hashCode());
    227         int i = indexFor(hash, table.length);
    228         // 先得到对应的hash值的格子,判断该hash值的格子中下是否已经存储数据,若不为空则已存在,则新数据需要通过next获取下一个桶
    229         for (Entry<K, V> e = table[i]; e != null; e = e.next) {
    230             Object k;
    231             // 如果hash相同并且key相同 ,则旧值被替换
    232             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    233                 V oldValue = e.value;
    234                 e.value = value;
    235                 e.recordAccess(this);
    236                 return oldValue;
    237             }
    238         }
    239 
    240         modCount++;
    241         addEntry(hash, key, value, i);
    242         return null;
    243     }
    244 
    245     /**
    246      * 当key为空时进行存放
    247      * 物理存储采用链表结构
    248      */
    249     private V putForNullKey(V value) {
    250         for (Entry<K, V> e = table[0]; e != null; e = e.next) {
    251             if (e.key == null) {
    252                 V oldValue = e.value;
    253                 e.value = value;
    254                 e.recordAccess(this);
    255                 return oldValue;
    256             }
    257         }
    258         modCount++;
    259         addEntry(0, null, value, 0);
    260         return null;
    261     }
    262 
    263     /**
    264      * 检查当前已创建的桶是存在
    265      */
    266     private void putForCreate(K key, V value) {
    267         int hash = (key == null) ? 0 : hash(key.hashCode());
    268         int i = indexFor(hash, table.length);
    269 
    270         // 遍历所有桶  
    271         for (Entry<K, V> e = table[i]; e != null; e = e.next) {
    272             Object k;
    273              // 如果有hash相同,且key相同,那么则不需要创建新的桶,退出
    274             if (e.hash == hash
    275                     && ((k = e.key) == key || (key != null && key.equals(k)))) {
    276                 e.value = value;
    277                 return;
    278             }
    279         }
    280         //否则,不存在hash值桶需要创建新的桶
    281         createEntry(hash, key, value, i);
    282     }
    283     /**
    284      * 根据Map创建所有对应的桶  
    285      * @param m
    286      */
    287     private void putAllForCreate(Map<? extends K, ? extends V> m) {
    288         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
    289                 .entrySet().iterator(); i.hasNext();) {
    290             Map.Entry<? extends K, ? extends V> e = i.next();
    291             putForCreate(e.getKey(), e.getValue());
    292         }
    293     }
    294 
    295     /**
    296      * 根据新的容量来resize这个HashMap
    297      * @param newCapacity
    298      */
    299     void resize(int newCapacity) {
    300         Entry[] oldTable = table;
    301         int oldCapacity = oldTable.length;
    302         if (oldCapacity == MAXIMUM_CAPACITY) {
    303             threshold = Integer.MAX_VALUE;
    304             return;
    305         }
    306         // 根据新的容量新建一个table
    307         Entry[] newTable = new Entry[newCapacity];
    308         // 将table转换成newTable
    309         transfer(newTable);
    310         // 将table设置newTable 
    311         table = newTable;
    312         // 设置阈值
    313         threshold = (int) (newCapacity * loadFactor);
    314     }
    315 
    316     /**
    317      * 动态扩展后,将所有格子里的桶都放到新的table中 
    318      */
    319     void transfer(Entry[] newTable) {
    320         Entry[] src = table;
    321         int newCapacity = newTable.length;
    322         for (int j = 0; j < src.length; j++) {
    323             Entry<K, V> e = src[j];
    324             if (e != null) {
    325                 src[j] = null;
    326                 do {
    327                     Entry<K, V> next = e.next;
    328                     int i = indexFor(e.hash, newCapacity);
    329                     e.next = newTable[i];
    330                     newTable[i] = e;
    331                     e = next;
    332                 } while (e != null);
    333             }
    334         }
    335     }
    336 
    337     /**
    338      * 将另一个Map对象copy到当前对象
    339      * 将指定映射的所有映射关系复制到此映射中,这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系  
    340      */
    341     public void putAll(Map<? extends K, ? extends V> m) {
    342         // 需要复制多少个映射关系 
    343         int numKeysToBeAdded = m.size();
    344         if (numKeysToBeAdded == 0)
    345             return;
    346 
    347         // 如果要复制的映射关系比阈值还要多
    348         if (numKeysToBeAdded > threshold) {
    349             // 重新计算新的容量先resize 
    350             int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
    351             if (targetCapacity > MAXIMUM_CAPACITY)
    352                 targetCapacity = MAXIMUM_CAPACITY;
    353             int newCapacity = table.length;
    354             while (newCapacity < targetCapacity)
    355                 newCapacity <<= 1;
    356             if (newCapacity > table.length)
    357                 resize(newCapacity);
    358         }
    359         // 迭代将key-value映射放进该HashMap
    360         for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
    361                 .entrySet().iterator(); i.hasNext();) {
    362             Map.Entry<? extends K, ? extends V> e = i.next();
    363             put(e.getKey(), e.getValue());
    364         }
    365     }
    366 
    367     /**
    368      * 从此映射中移除指定键的映射关系(如果存在)
    369      */
    370     public V remove(Object key) {
    371         Entry<K, V> e = removeEntryForKey(key);
    372         return (e == null ? null : e.value);
    373     }
    374 
    375     /**
    376      * 根据key删除桶,并返回对应value
    377      */
    378     final Entry<K, V> removeEntryForKey(Object key) {
    379         int hash = (key == null) ? 0 : hash(key.hashCode());
    380         int i = indexFor(hash, table.length);
    381         // 找到对应的格子
    382         Entry<K, V> prev = table[i];
    383         Entry<K, V> e = prev;
    384         // 遍历所有桶 
    385         while (e != null) {
    386             Entry<K, V> next = e.next;
    387             Object k;
    388             // 如果找到对应的桶 
    389             if (e.hash == hash
    390                     && ((k = e.key) == key || (key != null && key.equals(k)))) {
    391                 modCount++;
    392                 size--;
    393                 // 如果第一个就是要删的桶
    394                 if (prev == e)
    395                     // 则table[i]等于下一个桶
    396                     table[i] = next;
    397                 else
    398                     // 否则上一个桶的下一个等于下一个桶
    399                     prev.next = next;
    400                 e.recordRemoval(this);
    401                 return e;
    402             }
    403             prev = e;
    404             e = next;
    405         }
    406 
    407         return e;
    408     }
    409 
    410     /**
    411      * 根据桶来删除map里的值
    412      */
    413     final Entry<K, V> removeMapping(Object o) {
    414         // 如果o不是Map.Entry的实例,则退出返回null
    415         if (!(o instanceof Map.Entry))
    416             return null;
    417         // 将o转成Map.Entry 
    418         Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
    419         Object key = entry.getKey();
    420         int hash = (key == null) ? 0 : hash(key.hashCode());
    421         int i = indexFor(hash, table.length);
    422         Entry<K, V> prev = table[i];
    423         Entry<K, V> e = prev;
    424 
    425         while (e != null) {
    426             Entry<K, V> next = e.next;
    427             if (e.hash == hash && e.equals(entry)) {
    428                 modCount++;
    429                 size--;
    430                 if (prev == e)
    431                     table[i] = next;
    432                 else
    433                     prev.next = next;
    434                 e.recordRemoval(this);
    435                 return e;
    436             }
    437             prev = e;
    438             e = next;
    439         }
    440 
    441         return e;
    442     }
    443 
    444     /**
    445      * 从此映射中移除所有映射关系。此调用返回后,映射将为空
    446      */
    447     public void clear() {
    448         modCount++;
    449         Entry[] tab = table;
    450         // 遍历table中的所有格子,然偶后设为nul
    451         for (int i = 0; i < tab.length; i++)
    452             tab[i] = null;
    453         size = 0;
    454     }
    455 
    456     /**
    457      * 如果此映射将一个或多个键映射到指定值,则返回 true 
    458      */
    459     public boolean containsValue(Object value) {
    460         // 如果value为空,则返回containsNullValue函数的返回值
    461         if (value == null)
    462             return containsNullValue();
    463 
    464         Entry[] tab = table;
    465         // 遍历table所有格子(链表)
    466         for (int i = 0; i < tab.length; i++)
    467             // 遍历链表中的每个桶
    468             for (Entry e = tab[i]; e != null; e = e.next)
    469                 // 如果值相同,则返回true 
    470                 if (value.equals(e.value))
    471                     return true;
    472         return false;
    473     }
    474 
    475     /**
    476      * 对value为null的处理
    477      */
    478     private boolean containsNullValue() {
    479         Entry[] tab = table;
    480         for (int i = 0; i < tab.length; i++)
    481             for (Entry e = tab[i]; e != null; e = e.next)
    482                 if (e.value == null)
    483                     return true;
    484         return false;
    485     }
    486 
    487     /**
    488      * 返回此 HashMap 实例的浅表副本:并不复制键和值本身
    489      */
    490     public Object clone() {
    491         HashMap<K, V> result = null;
    492         try {
    493             result = (HashMap<K, V>) super.clone();
    494         } catch (CloneNotSupportedException e) {
    495             // assert false;
    496         }
    497         result.table = new Entry[table.length];
    498         result.entrySet = null;
    499         result.modCount = 0;
    500         result.size = 0;
    501         result.init();
    502         result.putAllForCreate(this);
    503 
    504         return result;
    505     }
    506     /**
    507      * 内置class输入对象,也就是桶
    508      * @author wwl
    509      *
    510      * @param <K>
    511      * @param <V>
    512      */
    513     static class Entry<K, V> implements Map.Entry<K, V> {
    514         final K key;
    515         V value;
    516         Entry<K, V> next;
    517         final int hash;
    518 
    519         /**
    520          *  构造函数
    521          */
    522         Entry(int h, K k, V v, Entry<K, V> n) {
    523             value = v;
    524             next = n;
    525             key = k;
    526             hash = h;
    527         }
    528         /**
    529          * 返回key
    530          */
    531         public final K getKey() {
    532             return key;
    533         }
    534         /**
    535          * 返回value
    536          */
    537         public final V getValue() {
    538             return value;
    539         }
    540         /**
    541          * 设置value
    542          */
    543         public final V setValue(V newValue) {
    544             V oldValue = value;
    545             value = newValue;
    546             return oldValue;
    547         }
    548         /**
    549          * 是否相同,比对的是key与value
    550          */
    551         public final boolean equals(Object o) {
    552              // 如果o不是Map.Entry的实例,那么肯定不相同了
    553             if (!(o instanceof Map.Entry))
    554                 return false;
    555             // 将o转成Map.Entry
    556             Map.Entry e = (Map.Entry) o;
    557             // 得到key和value对比是否相同,相同则为true
    558             Object k1 = getKey();
    559             Object k2 = e.getKey();
    560             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
    561                 Object v1 = getValue();
    562                 Object v2 = e.getValue();
    563                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
    564                     return true;
    565             }
    566             return false;
    567         }
    568 
    569         public final int hashCode() {
    570             return (key == null ? 0 : key.hashCode())
    571                     ^ (value == null ? 0 : value.hashCode());
    572         }
    573 
    574         public final String toString() {
    575             return getKey() + "=" + getValue();
    576         }
    577 
    578         /**
    579          * 使用该方法证明该key已经在该map中
    580          */
    581         void recordAccess(HashMap<K, V> m) {
    582         }
    583 
    584         /**
    585          * 该方法记录该key已经被移除了
    586          */
    587         void recordRemoval(HashMap<K, V> m) {
    588         }
    589     }
    590 
    591     /**
    592      * 添加一个新的桶来保存该key和value
    593      */
    594     void addEntry(int hash, K key, V value, int bucketIndex) {
    595         Entry<K, V> e = table[bucketIndex];
    596         table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    597         if (size++ >= threshold)
    598             resize(2 * table.length);
    599     }
    600 
    601     /**
    602      * 新建一个桶,该方法不需要判断是否超过阈值 
    603      */
    604     void createEntry(int hash, K key, V value, int bucketIndex) {
    605         Entry<K, V> e = table[bucketIndex];
    606         table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    607         size++;
    608     }
    609     /**
    610      * 内部class HashIterator迭代器
    611      * @author wwl
    612      *
    613      * @param <E>
    614      */
    615     private abstract class HashIterator<E> implements Iterator<E> {
    616         Entry<K, V> next; // 下一个桶
    617         int expectedModCount; // 保护HashMap没有变更
    618         int index; // 当前的索引
    619         Entry<K, V> current; // 当前的桶
    620 
    621         HashIterator() {
    622              // 保存modCount,因为如果HashMap进行了任何操作modCount都会增加,所以如果发现modCount变化了,就可以抛出失败
    623             expectedModCount = modCount;
    624             if (size > 0) { // 进入第一个桶 
    625                 Entry[] t = table;
    626                 while (index < t.length && (next = t[index++]) == null)
    627                     ;
    628             }
    629         }
    630         /**
    631          * 判断有没有下一个桶 
    632          */
    633         @Override
    634         public final boolean hasNext() {
    635             return next != null;
    636         }
    637         /**
    638          * 获取下一个桶 
    639          * @return
    640          */
    641         final Entry<K, V> nextEntry() {
    642             if (modCount != expectedModCount)
    643                 throw new ConcurrentModificationException();
    644             Entry<K, V> e = next;
    645             // 如果next为空,抛出失败
    646             if (e == null)
    647                 throw new NoSuchElementException();
    648             // 如果next.next为空,将next定义为下一个格子中的桶,否则为该格子的下一个桶
    649             if ((next = e.next) == null) {
    650                 Entry[] t = table;
    651                 while (index < t.length && (next = t[index++]) == null)
    652                     ;
    653             }
    654             current = e;
    655             return e;
    656         }
    657         /**
    658          * 删除
    659          */
    660         @Override
    661         public void remove() {
    662             // 如果当前为空,抛出
    663             if (current == null)
    664                 throw new IllegalStateException();
    665             // modCount变化了,抛出失败
    666             if (modCount != expectedModCount)
    667                 throw new ConcurrentModificationException();
    668             // 获得当前的key
    669             Object k = current.key;
    670              // 设置current为null 
    671             current = null;
    672             // 删除掉对应key的元素
    673             HashMap.this.removeEntryForKey(k);
    674             // 重置expectedModCount
    675             expectedModCount = modCount;
    676         }
    677 
    678     }
    679     /**
    680      * 内部class ValueIterator迭代器,重写next方法
    681      * @author wwl
    682      *
    683      */
    684     private final class ValueIterator extends HashIterator<V> {
    685         @Override
    686         public V next() {
    687             return nextEntry().value;
    688         }
    689     }
    690     /**
    691      * 内部class KeyIterator迭代器,重写next方法
    692      * @author wwl
    693      *
    694      */
    695     private final class KeyIterator extends HashIterator<K> {
    696         public K next() {
    697             return nextEntry().getKey();
    698         }
    699     }
    700     /**
    701      * 内部class EntryIterator迭代器,重写next方法
    702      * @author wwl
    703      *
    704      */
    705     private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
    706         public Map.Entry<K, V> next() {
    707             return nextEntry();
    708         }
    709     }
    710 
    711     /**
    712      * 定义对应的 iterator() 方法
    713      * @return
    714      */
    715     Iterator<K> newKeyIterator() {
    716         return new KeyIterator();
    717     }
    718     /**
    719      * 定义对应的 iterator() 方法
    720      * @return
    721      */
    722     Iterator<V> newValueIterator() {
    723         return new ValueIterator();
    724     }
    725     /**
    726      * 定义对应的 iterator() 方法
    727      * @return
    728      */
    729     Iterator<Map.Entry<K, V>> newEntryIterator() {
    730         return new EntryIterator();
    731     }
    732 
    733     // Views
    734 
    735     private transient Set<Map.Entry<K, V>> entrySet = null;
    736 
    737     /**
    738      * 返回此映射中所包含的键的 Set 视图
    739      */
    740     public Set<K> keySet() {
    741         Set<K> ks = keySet;
    742         return (ks != null ? ks : (keySet = new KeySet()));
    743     }
    744 
    745     /**
    746      * 内部类KeySet对象
    747      * @author wwl
    748      * 
    749      */
    750     private final class KeySet extends AbstractSet<K> {
    751         public Iterator<K> iterator() {
    752             return newKeyIterator();
    753         }
    754         
    755         public int size() {
    756             return size;
    757         }
    758 
    759         public boolean contains(Object o) {
    760             return containsKey(o);
    761         }
    762 
    763         public boolean remove(Object o) {
    764             return HashMap.this.removeEntryForKey(o) != null;
    765         }
    766 
    767         public void clear() {
    768             HashMap.this.clear();
    769         }
    770     }
    771 
    772     /**
    773      * 返回此映射所包含的值的 Collection 视图
    774      */
    775     public Collection<V> values() {
    776         Collection<V> vs = values;
    777         return (vs != null ? vs : (values = new Values()));
    778     }
    779 
    780     /**
    781      * 内部类Values 
    782      * 
    783      * @author wwl
    784      * 
    785      */
    786     private final class Values extends AbstractCollection<V> {
    787         public Iterator<V> iterator() {
    788             return newValueIterator();
    789         }
    790 
    791         public int size() {
    792             return size;
    793         }
    794 
    795         public boolean contains(Object o) {
    796             return containsValue(o);
    797         }
    798 
    799         public void clear() {
    800             HashMap.this.clear();
    801         }
    802     }
    803 
    804     /**
    805      * 返回此映射所包含的映射关系的 Set 视图
    806      */
    807     public Set<Map.Entry<K, V>> entrySet() {
    808         return entrySet0();
    809     }
    810 
    811     private Set<Map.Entry<K, V>> entrySet0() {
    812         Set<Map.Entry<K, V>> es = entrySet;
    813         return es != null ? es : (entrySet = new EntrySet());
    814     }
    815 
    816     /**
    817      *  内部类EntrySet对象
    818      * 
    819      * @author wwl
    820      * 
    821      */
    822     private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
    823         public Iterator<Map.Entry<K, V>> iterator() {
    824             return newEntryIterator();
    825         }
    826 
    827         public boolean contains(Object o) {
    828             if (!(o instanceof Map.Entry))
    829                 return false;
    830             Map.Entry<K, V> e = (Map.Entry<K, V>) o;
    831             Entry<K, V> candidate = getEntry(e.getKey());
    832             return candidate != null && candidate.equals(e);
    833         }
    834 
    835         public boolean remove(Object o) {
    836             return removeMapping(o) != null;
    837         }
    838 
    839         public int size() {
    840             return size;
    841         }
    842 
    843         public void clear() {
    844             HashMap.this.clear();
    845         }
    846     }
    847 
    848     /**
    849      * 序列化方法
    850      */
    851     private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    852         Iterator<Map.Entry<K, V>> i = (size > 0) ? entrySet0().iterator()
    853                 : null;
    854 
    855         s.defaultWriteObject();
    856 
    857         s.writeInt(table.length);
    858 
    859         s.writeInt(size);
    860 
    861         if (i != null) {
    862             while (i.hasNext()) {
    863                 Map.Entry<K, V> e = i.next();
    864                 s.writeObject(e.getKey());
    865                 s.writeObject(e.getValue());
    866             }
    867         }
    868     }
    869 
    870     private static final long serialVersionUID = 362498820763181265L;
    871 
    872     /**
    873      * 通过序列读取对象
    874      */
    875     private void readObject(java.io.ObjectInputStream s) throws IOException,
    876             ClassNotFoundException {
    877         s.defaultReadObject();
    878 
    879         int numBuckets = s.readInt();
    880         table = new Entry[numBuckets];
    881 
    882         init(); 
    883 
    884         int size = s.readInt();
    885 
    886         for (int i = 0; i < size; i++) {
    887             K key = (K) s.readObject();
    888             V value = (V) s.readObject();
    889             putForCreate(key, value);
    890         }
    891     }
    892 
    893     int capacity() {
    894         return table.length;
    895     }
    896 
    897     float loadFactor() {
    898         return loadFactor;
    899     }
    900 }
    View Code

    Map源码

      1 package java2.util2;
      2 
      3 import java.util.Collection;
      4 import java.util.Set;
      5 /**
      6  * 重构Map接口
      7  * @author wwl
      8  *
      9  * @param <K>
     10  * @param <V>
     11  */
     12 public interface Map<K, V> {
     13     /**
     14      * 返回map中键值对映射关系的数量
     15      * 
     16      * @return
     17      */
     18     int size();
     19 
     20     /**
     21      * 如果此映射不包含键值的映射则返回true
     22      * 
     23      * @return
     24      */
     25     boolean isEmpty();
     26 
     27     /**
     28      * 如果此映射包含指定键的映射关系,则返回 true
     29      * 
     30      * @param key
     31      * @return
     32      */
     33     boolean containsKey(Object key);
     34 
     35     /**
     36      * 如果此映射将一个或多个键映射到指定值,则返回 true
     37      * 
     38      * @param value
     39      * @return
     40      */
     41     boolean containsValue(Object value);
     42 
     43     /**
     44      * 指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null
     45      * 允许null键null值
     46      * @param key
     47      * @return
     48      */
     49     V get(Object key);
     50 
     51     /**
     52      * 存放键值对
     53      * 
     54      * @param key
     55      * @param value
     56      * @return
     57      */
     58     V put(K key, V value);
     59 
     60     /**
     61      * 以前与 key 关联的值;如果没有 key 的映射关系,则返回 null。
     62      * 
     63      * @param key
     64      * @return
     65      */
     66     V remove(Object key);
     67 
     68     /**
     69      * 从此映射中移除所有映射关系
     70      */
     71     void clear();
     72 
     73     /**
     74      * 
     75      * @param m
     76      */
     77     void putAll(Map<? extends K, ? extends V> m);
     78 
     79     /**
     80      * 返回此映射中包含的键的 Set 视图
     81      * 
     82      * @return
     83      */
     84     Set<K> keySet();
     85 
     86     /**
     87      * 此映射中包含的值的 collection 视图
     88      * @return
     89      */
     90     Collection<V> values();
     91     
     92     /**
     93      * 此映射中包含的映射关系的 set 视图
     94      * @return
     95      */
     96     Set<Map.Entry<K, V>> entrySet();
     97 
     98     interface Entry<K, V> {
     99         /**
    100          * 获取key值
    101          * @return
    102          */
    103         K getKey();
    104 
    105         /**
    106          * 获取value值
    107          * @return
    108          */
    109         V getValue();
    110 
    111         /**
    112          * 设置value值
    113          * @param value
    114          * @return
    115          */
    116         V setValue(V value);
    117         /**
    118          * 如果指定的对象等于此映射项,则返回 true
    119          * @param o
    120          * @return
    121          */
    122         boolean equals(Object o);
    123         /**
    124          * 此映射的哈希码值
    125          * @return
    126          */
    127         int hashCode();
    128     }
    129     
    130     /**
    131      * 如果指定的对象等于此映射,则返回 true
    132      * @param o
    133      * @return
    134      */
    135     boolean equals(Object o);
    136     
    137     /**
    138      * 此映射的哈希码值
    139      * @return
    140      */
    141     int hashCode();
    142 }
    View Code

    AbstractMap源码

      1 package java2.util2;
      2 
      3 import java.util.AbstractCollection;
      4 import java.util.AbstractSet;
      5 import java.util.Collection;
      6 import java.util.Iterator;
      7 import java.util.Set;
      8 
      9 
     10 
     11 
     12 public abstract class AbstractMap<K,V> implements Map<K,V> {
     13     protected AbstractMap() {
     14     }
     15 
     16     @Override
     17     public void clear() {
     18         entrySet().clear();
     19     }
     20 
     21     @Override
     22     public boolean containsKey(Object key) {
     23         Iterator<Entry<K,V>> i= entrySet().iterator();
     24         if(key==null){
     25             while(i.hasNext()){
     26                 Entry<K,V> e=i.next();
     27                 if(e.getKey()==null)
     28                     return true;
     29             }
     30         }else{
     31             while(i.hasNext()){
     32                 Entry<K,V> e=i.next();
     33                 if(key.equals(e.getKey()))
     34                     return true;
     35             }
     36         }
     37         return false;
     38     }
     39 
     40     @Override
     41     public boolean containsValue(Object value) {
     42         Iterator<Entry<K,V>> i=entrySet().iterator();
     43         if(value==null){
     44             while(i.hasNext()){
     45                 Entry<K,V> e=i.next();
     46                 if(e.getValue()==null)
     47                     return true;
     48             }
     49         }else{
     50             while(i.hasNext()){
     51                 Entry<K, V> e=i.next();
     52                 if(value==e.getValue())
     53                     return true;
     54             }
     55         }
     56         return false;
     57     }
     58 
     59     @Override
     60     public abstract Set<java2.util2.Map.Entry<K, V>> entrySet();
     61 
     62     @Override
     63     //允许null键null值
     64     public V get(Object key) {
     65         Iterator<Entry<K, V>> i=entrySet().iterator();
     66         if(key==null){
     67             while(i.hasNext()){
     68                 Entry<K, V> e=i.next();
     69                 if(e.getKey()==null)
     70                     return e.getValue();
     71                 
     72             }
     73         }else{
     74             while(i.hasNext()){
     75                 Entry<K, V> e=i.next();
     76                 if(key.equals(e.getKey()))
     77                     return e.getValue();
     78             }
     79         }
     80         return null;
     81     }
     82 
     83     @Override
     84     public boolean isEmpty() {
     85         return size()==0;
     86     }
     87     //volatile也是变量修饰符,只能用来修饰变量。
     88     //volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。
     89     //而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。
     90     //即通过改变就提交实现线程同步
     91     
     92     //transient是类型修饰符,只能用来修饰字段。
     93     //在对象序列化的过程中,标记为transient的变量不会被序列化。
     94     transient volatile Set<K>        keySet = null;//此处进行定义,表示每次生成set集合都是最新的
     95     @Override
     96     public Set<K> keySet() {
     97         if(keySet==null){
     98             keySet=new AbstractSet<K>() {
     99                 @Override
    100                 public Iterator<K> iterator(){
    101                     return new Iterator<K>(){
    102                         private Iterator<Entry<K, V>> i=entrySet().iterator();
    103                         
    104                         public boolean hasNext(){
    105                             return i.hasNext();
    106                         }
    107                         public K next(){
    108                             return i.next().getKey();
    109                         }
    110                         public void remove(){
    111                             i.remove();
    112                         }
    113                     };
    114                 }
    115 
    116                 @Override
    117                 public int size() {
    118                     return AbstractMap.this.size();
    119                 }
    120                 @Override
    121                 public boolean contains(Object k) {
    122                     return AbstractMap.this.containsKey(k);
    123                 }
    124             };
    125         }
    126         return keySet;
    127     }
    128 
    129     @Override
    130     public V put(K key, V value) {
    131         throw new UnsupportedOperationException();
    132     }
    133 
    134     @Override
    135     public void putAll(Map<? extends K, ? extends V> m) {
    136         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
    137             put(e.getKey(), e.getValue());
    138     }
    139 
    140     @Override
    141     public V remove(Object key) {
    142         Iterator<Entry<K, V>> i=entrySet().iterator();
    143         Entry<K, V> correctEntry =null;
    144         if(key==null){
    145             while(i.hasNext()){
    146                 Entry<K, V> e=i.next();
    147                 if(e.getKey()==null)
    148                     correctEntry=e;//让引用指向空引用
    149             }
    150         }else{
    151             while(correctEntry==null&&i.hasNext()){
    152                 Entry<K, V> e=i.next();
    153                 if(key.equals(e.getKey()))
    154                     correctEntry=e;
    155             }
    156         }
    157         return null;
    158     }
    159 
    160     @Override
    161     public int size() {
    162         return entrySet().size();
    163     }
    164 
    165     transient volatile Collection<V> values = null;
    166     
    167     @Override
    168     public Collection<V> values() {
    169         if (values == null) {
    170             values = new AbstractCollection<V>() {
    171             public Iterator<V> iterator() {
    172                 return new Iterator<V>() {
    173                 private Iterator<Entry<K,V>> i = entrySet().iterator();
    174 
    175                 public boolean hasNext() {
    176                     return i.hasNext();
    177                 }
    178 
    179                 public V next() {
    180                     return i.next().getValue();
    181                 }
    182 
    183                 public void remove() {
    184                     i.remove();
    185                 }
    186                         };
    187                     }
    188 
    189             public int size() {
    190                 return AbstractMap.this.size();
    191             }
    192 
    193             public boolean contains(Object v) {
    194                 return AbstractMap.this.containsValue(v);
    195             }
    196             };
    197         }
    198         return values;
    199     }
    200 
    201     @Override
    202     public boolean equals(Object obj) {
    203         if(obj==this)
    204             return true;
    205         if(!(obj instanceof Map))
    206             return false;
    207         Map<K,V> m=(Map<K, V>) obj;
    208         if(m.size()!=size())
    209             return false;
    210         try {
    211             Iterator<Entry<K,V>> i = entrySet().iterator();
    212             while (i.hasNext()) {
    213                 Entry<K,V> e = i.next();
    214                 K key = e.getKey();
    215                 V value = e.getValue();
    216                 if (value == null) {
    217                     if (!(m.get(key)==null && m.containsKey(key)))
    218                         return false;
    219                 } else {
    220                     if (!value.equals(m.get(key)))
    221                         return false;
    222                 }
    223             }
    224         } catch (ClassCastException unused) {
    225             return false;
    226         } catch (NullPointerException unused) {
    227             return false;
    228         }
    229 
    230         return true;
    231     }
    232 
    233     @Override
    234     //所有map对象的hashcode相加
    235     public int hashCode() {
    236         int h = 0;
    237         Iterator<Entry<K,V>> i = entrySet().iterator();
    238         while (i.hasNext())
    239             h += i.next().hashCode();
    240         return h;
    241     }
    242 
    243     @Override
    244     public String toString() {
    245         Iterator<Entry<K,V>> i = entrySet().iterator();
    246         if (! i.hasNext())
    247             return "{}";
    248 
    249         StringBuilder sb = new StringBuilder();
    250         sb.append('{');
    251         for (;;) {
    252             Entry<K,V> e = i.next();
    253             K key = e.getKey();
    254             V value = e.getValue();
    255             sb.append(key   == this ? "(this Map)" : key);
    256             sb.append('=');
    257             sb.append(value == this ? "(this Map)" : value);
    258             if (! i.hasNext())
    259             return sb.append('}').toString();
    260             sb.append(", ");
    261         }
    262     }
    263 
    264     @Override
    265     protected Object clone() throws CloneNotSupportedException {
    266         AbstractMap<K,V> result = (AbstractMap<K,V>)super.clone();
    267         result.keySet = null;
    268         result.values = null;
    269         return result;
    270     }
    271     
    272 }
    View Code

     

    转载于:https://www.cnblogs.com/atwanli/articles/4116072.html

    展开全文
  • HashMap源代码解析

    2017-05-21 22:23:00
     之前有看过别人的HashMap源代码的分析,今天尝试自己来分析一波,纯属个人愚见。听一些老的程序员说过,当别人跟你说用某样技术到项目中去,而你按照别人的想法实现了的时候,你只能是一个码农,当你自己会想到用...
  • 一个delphi写的hashmap源代码, 包括TIntegerHashList, TStringHashList, TObjectHashList. 十万条记录查找只用 400毫秒.
  • (1)一个人只要自己不放弃自己,整个世界也不会放弃你. (2)天生我才必有大用 (3)不能忍受学习之苦就一定要忍受生活...文章目录Java SE 052 HashSet与HashMap源代码深度剖析1.HashSet底层源码分析1.1.HashSet底层.
  • HashMap源代码剖析

    2017-07-02 12:53:00
    源代码中都标了出来。jdk容器源代码还是挺简单的。 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //容量默认值 stati...
  • 本文主要介绍了HashMap源代码实现,包括哈希表的简介、HashMap底层数据结构、添加数据、获取数据等主要方法。
  • HashMap源代码分析

    2019-07-04 15:39:26
    感觉HashMap才是集大成者啊 继承关系简要图 ![这里写图片描述](https://img-blog.csdn.net/20180...
  • HashMap源代码详解

    2018-01-14 18:34:54
    package java.util;  ...public class HashMap   extends AbstractMap   implements Map, Cloneable, Serializable  {     // 系统默认初始容量,必须是2的n次幂,这是出于优
  • Hashmap源代码知识梳理

    2019-10-25 18:07:57
    ##Hashmap 是我们开发中最长用的类,透彻的掌握HashMap 也显的十分重要 jdk 1.8 HashMap 的数据结构 是数组加红黑树 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //如果一个较高的值...
  • Java HashMap 源代码分析

    2019-09-26 16:36:46
    Java HashMap jdk 1.8 Java8相对于java7来说HashMap变化比较大,在hash冲突严重的时候java7会退化为链表,Java8会退化为TreeMap 我们先来看一下类图: 可见,HashMap继承了AbstractMap,但是Map并没有扩展Collection...
  • 查看HashMap代码之前我们先来看一下关于HashMap数据结构的题目,并且这些问题的答案都能够在代码中找到。 P:HashMap的底层是怎么样的 Q:在JDK1.8之前 HashMap的数据结构是数组 + 链表,从JDK1.8开始它的数据...
  • HashMap源代码阅读

    2017-04-16 19:27:00
    Map类结构 Java的集合类主要由两个接口派生出来...HashMap 一种存储键/值关联的数据结构 Hashtable 一种用synchronized包裹其内部方法的映射表。保证线程安全 TreeMap 一种有序排列的映射表 E...
  • HashMap的底层源码 HashMap算是我被我当成对象最多...代码是在是太多了,不过没关系,看中文就行 package java.util; import java.io.IOException; import java.io.InvalidObjectException; import java.io.Seria...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,270
精华内容 508
关键字:

hashmap源代码