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

JDK8中的HashMap源码

程序员文章站 2022-06-05 17:33:29
背景 很久以前看过源码,但是猛一看总感觉挺难的,很少看下去。当时总感觉是水平不到。工作中也遇到一些想看源码的地方,但是遇到写的复杂些的心里就打退堂鼓了。 最近在接手同事的代码时,有一些很长的python脚本,没有一行注释。就硬着头皮一行一行的读,把理解的都加上注释,这样一行行看下来,终于知道代码的意 ......

背景

        很久以前看过源码,但是猛一看总感觉挺难的,很少看下去。当时总感觉是水平不到。工作中也遇到一些想看源码的地方,但是遇到写的复杂些的心里就打退堂鼓了。

        最近在接手同事的代码时,有一些很长的python脚本,没有一行注释。就硬着头皮一行一行的读,把理解的都加上注释,这样一行行看下来,终于知道代码的意思了。这对于我算是一种进步。

        很久之前用了公司的一个分布式id生成的组件,该组件表明生成的id是增加的。但是实际使用过程中出现了id变小的情况,大致看了下代码,没有看懂。咨询了组件的负责人,负责人表示不会变小。前段时间,我就又硬着头皮一行行仔细看了好几遍,终于看明白了。对着之前异常id的日志,推理了一下代码流程,感觉会出现id变小的可能。于是在该组件的页面下面阐述了我的观点。(目前还没有回复,应该还没看到)现在快要过年了,手上的活没有那么紧了,所以趁机修炼内功,重新开始看jdk源码。

hashmap源码阅读

注释主要集中在get、put、resize三个方法上。

/*
 * 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
 */
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.
     */
    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.
     */
    static final int maximum_capacity = 1 << 30;

    /**
     * the load factor used when none specified in constructor.
     */
    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.
     */
    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.
     */
    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.)
     */
    static class node<k,v> implements map.entry<k,v> {
        final int hash;
        final k key;
        v value;
        node<k,v> next;

        node(int hash, k key, v value, node<k,v> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final k getkey()        { return key; }
        public final v getvalue()      { return value; }
        public final string tostring() { return key + "=" + value; }

        public final int hashcode() {
            return objects.hashcode(key) ^ objects.hashcode(value);
        }

        public final v setvalue(v newvalue) {
            v oldvalue = value;
            value = newvalue;
            return oldvalue;
        }

        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;
        //取hash,为什么 先右移,然后进行与运算呢?
        //https://www.cnblogs.com/wang-meng/p/9b6c35c4b2ef7e5b398db9211733292d.html
        //上面说,这样运算有利于将hash打散,就是分散效果更好
        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().
     */
    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;
        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)
     */
    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;
        //表不为null,且长度>0,且hash槽不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //先比较第1个,first已经在if里赋值了
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //有第2个
            if ((e = first.next) != null) {
                if (first instanceof treenode)//treenode类型,进行二叉树查找
                    return ((treenode<k,v>)first).gettreenode(hash, key);
                do {//遍历,比较
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 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.
     */
    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;
        //tab为空,或者长度是0,就进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果hash处为空,就直接在该处赋值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newnode(hash, key, value, null);
        else {
            node<k,v> e; k k;
            //比较第一个值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof treenode) //如果是treenode类型,就调用treenode的添加方法
                e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
            else {
                for (int bincount = 0; ; ++bincount) {
                    //p的next是空,添加值,并结束
                    if ((e = p.next) == null) {
                        //赋值next
                        p.next = newnode(hash, key, value, null);
                        //如果计算超过8个,就转为二叉树结构
                        if (bincount >= treeify_threshold - 1) // -1 for 1st
                            treeifybin(tab, hash);
                        break;
                    }
                    //前面已经对e赋过值
                    //如果当前节点比对成功,就结束
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //对p赋值,进行下一轮循环
                    p = e;
                }
            }
            //key存在,替换旧值
            if (e != null) { // existing mapping for key
                v oldvalue = e.value;
                if (!onlyifabsent || oldvalue == null)
                    e.value = value;
                afternodeaccess(e);
                //返回旧值
                return oldvalue;
            }
        }
        ++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) {
                threshold = integer.max_value;
                return oldtab;
            }
            else if ((newcap = oldcap << 1) < maximum_capacity &&
                     oldcap >= default_initial_capacity)
                newthr = oldthr << 1; // double threshold
        }
        else if (oldthr > 0) // initial capacity was placed in threshold
            newcap = oldthr;
        else {               // zero initial threshold signifies using defaults
            newcap = default_initial_capacity;
            newthr = (int)(default_load_factor * default_initial_capacity);
        }
        if (newthr == 0) {
            float ft = (float)newcap * loadfactor;
            newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?
                      (int)ft : integer.max_value);
        }
        threshold = newthr;
        //定义新tab
        @suppresswarnings({"rawtypes","unchecked"})
            node<k,v>[] newtab = (node<k,v>[])new node[newcap];
        table = newtab;
        //迁移kv
        if (oldtab != null) {
            for (int j = 0; j < oldcap; ++j) {
                node<k,v> e;
                if ((e = oldtab[j]) != null) {
                    oldtab[j] = null;
                    //e没有下一个,直接hash赋值
                    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;
                        //此处参考:https://www.cnblogs.com/williamjie/p/9358291.html
                        //找到待迁移元素和该元素的上游
                        do {
                            next = e.next;
                            //与运算后值不变,说明后续的位置不变
                            if ((e.hash & oldcap) == 0) {
                                if (lotail == null)
                                    lohead = e;
                                else
                                    lotail.next = e;
                                lotail = e;
                            }
                            else {//位置需要加上oldcap
                                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;
        if (tab == null || (n = tab.length) < min_treeify_capacity)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            treenode<k,v> hd = null, tl = null;
            do {
                treenode<k,v> p = replacementtreenode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    /**
     * 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
     */
    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)))) {
                if (node instanceof treenode)
                    ((treenode<k,v>)node).removetreenode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modcount;
                --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;
            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
     */
    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
     */
    public set<k> keyset() {
        set<k> ks = keyset;
        if (ks == null) {
            ks = new keyset();
            keyset = ks;
        }
        return 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)
                        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
     */
    public collection<v> values() {
        collection<v> vs = values;
        if (vs == null) {
            vs = new values();
            values = vs;
        }
        return 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.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
     */
    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.accept(e);
                }
                if (modcount != mc)
                    throw new concurrentmodificationexception();
            }
        }
    }

    // overrides of jdk8 map extension methods

    @override
    public v getordefault(object key, v defaultvalue) {
        node<k,v> e;
        return (e = getnode(hash(key), key)) == null ? defaultvalue : e.value;
    }

    @override
    public v putifabsent(k key, v value) {
        return putval(hash(key), key, value, true, true);
    }

    @override
    public boolean remove(object key, object value) {
        return removenode(hash(key), key, value, true, true) != null;
    }

    @override
    public boolean replace(k key, v oldvalue, v newvalue) {
        node<k,v> e; v v;
        if ((e = getnode(hash(key), key)) != null &&
            ((v = e.value) == oldvalue || (v != null && v.equals(oldvalue)))) {
            e.value = newvalue;
            afternodeaccess(e);
            return true;
        }
        return false;
    }

    @override
    public v replace(k key, v value) {
        node<k,v> e;
        if ((e = getnode(hash(key), key)) != null) {
            v oldvalue = e.value;
            e.value = value;
            afternodeaccess(e);
            return oldvalue;
        }
        return null;
    }

    @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;
            }
        }
        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) {
            v v;
            if (old.value != null)
                v = remappingfunction.apply(old.value, value);
            else
                v = value;
            if (v != null) {
                old.value = v;
                afternodeaccess(old);
            }
            else
                removenode(hash, key, null, false, true);
            return v;
        }
        if (value != null) {
            if (t != null)
                t.puttreeval(this, tab, hash, key, value);
            else {
                tab[i] = newnode(hash, key, value, first);
                if (bincount >= treeify_threshold - 1)
                    treeifybin(tab, hash);
            }
            ++modcount;
            ++size;
            afternodeinsertion(true);
        }
        return value;
    }

    @override
    public void foreach(biconsumer<? super k, ? super v> action) {
        node<k,v>[] tab;
        if (action == null)
            throw new nullpointerexception();
        if (size > 0 && (tab = table) != null) {
            int mc = modcount;
            for (int i = 0; i < tab.length; ++i) {
                for (node<k,v> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modcount != mc)
                throw new concurrentmodificationexception();
        }
    }

    @override
    public void replaceall(bifunction<? super k, ? super v, ? extends v> function) {
        node<k,v>[] tab;
        if (function == null)
            throw new nullpointerexception();
        if (size > 0 && (tab = table) != null) {
            int mc = modcount;
            for (int i = 0; i < tab.length; ++i) {
                for (node<k,v> e = tab[i]; e != null; e = e.next) {
                    e.value = function.apply(e.key, e.value);
                }
            }
            if (modcount != mc)
                throw new concurrentmodificationexception();
        }
    }

    /* ------------------------------------------------------------ */
    // cloning and serialization

    /**
     * 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.
     */
    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).
     */
    private void readobject(java.io.objectinputstream s)
        throws ioexception, classnotfoundexception {
        // read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultreadobject();
        reinitialize();
        if (loadfactor <= 0 || float.isnan(loadfactor))
            throw new invalidobjectexception("illegal load factor: " +
                                             loadfactor);
        s.readint();                // read and ignore number of buckets
        int mappings = s.readint(); // read number of mappings (size)
        if (mappings < 0)
            throw new invalidobjectexception("illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (if zero, use defaults)
            // size the table using given load factor only if within
            // range of 0.25...4.0
            float lf = math.min(math.max(0.25f, loadfactor), 4.0f);
            float fc = (float)mappings / lf + 1.0f;
            int cap = ((fc < default_initial_capacity) ?
                       default_initial_capacity :
                       (fc >= maximum_capacity) ?
                       maximum_capacity :
                       tablesizefor((int)fc));
            float ft = (float)cap * lf;
            threshold = ((cap < maximum_capacity && ft < maximum_capacity) ?
                         (int)ft : integer.max_value);
            @suppresswarnings({"rawtypes","unchecked"})
                node<k,v>[] tab = (node<k,v>[])new node[cap];
            table = tab;

            // read the keys and values, and put the mappings in the hashmap
            for (int i = 0; i < mappings; i++) {
                @suppresswarnings("unchecked")
                    k key = (k) s.readobject();
                @suppresswarnings("unchecked")
                    v value = (v) s.readobject();
                putval(hash(key), key, value, false, false);
            }
        }
    }

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

    abstract class hashiterator {
        node<k,v> next;        // next entry to return
        node<k,v> current;     // current entry
        int expectedmodcount;  // for fast-fail
        int index;             // current slot

        hashiterator() {
            expectedmodcount = modcount;
            node<k,v>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasnext() {
            return next != null;
        }

        final node<k,v> nextnode() {
            node<k,v>[] t;
            node<k,v> e = next;
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            if (e == null)
                throw new nosuchelementexception();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            node<k,v> p = current;
            if (p == null)
                throw new illegalstateexception();
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            current = null;
            k key = p.key;
            removenode(hash(key), key, null, false, false);
            expectedmodcount = modcount;
        }
    }

    final class keyiterator extends hashiterator
        implements iterator<k> {
        public final k next() { return nextnode().key; }
    }

    final class valueiterator extends hashiterator
        implements iterator<v> {
        public final v next() { return nextnode().value; }
    }

    final class entryiterator extends hashiterator
        implements iterator<map.entry<k,v>> {
        public final map.entry<k,v> next() { return nextnode(); }
    }

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

    static class hashmapspliterator<k,v> {
        final hashmap<k,v> map;
        node<k,v> current;          // current node
        int index;                  // current index, modified on advance/split
        int fence;                  // one past last index
        int est;                    // size estimate
        int expectedmodcount;       // for comodification checks

        hashmapspliterator(hashmap<k,v> m, int origin,
                           int fence, int est,
                           int expectedmodcount) {
            this.map = m;
            this.index = origin;
            this.fence = fence;
            this.est = est;
            this.expectedmodcount = expectedmodcount;
        }

        final int getfence() { // initialize fence and size on first use
            int hi;
            if ((hi = fence) < 0) {
                hashmap<k,v> m = map;
                est = m.size;
                expectedmodcount = m.modcount;
                node<k,v>[] tab = m.table;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            return hi;
        }

        public final long estimatesize() {
            getfence(); // force init
            return (long) est;
        }
    }

    static final class keyspliterator<k,v>
        extends hashmapspliterator<k,v>
        implements spliterator<k> {
        keyspliterator(hashmap<k,v> m, int origin, int fence, int est,
                       int expectedmodcount) {
            super(m, origin, fence, est, expectedmodcount);
        }

        public keyspliterator<k,v> trysplit() {
            int hi = getfence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new keyspliterator<>(map, lo, index = mid, est >>>= 1,
                                        expectedmodcount);
        }

        public void foreachremaining(consumer<? super k> action) {
            int i, hi, mc;
            if (action == null)
                throw new nullpointerexception();
            hashmap<k,v> m = map;
            node<k,v>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedmodcount = m.modcount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedmodcount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                node<k,v> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.key);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modcount != mc)
                    throw new concurrentmodificationexception();
            }
        }

        public boolean tryadvance(consumer<? super k> action) {
            int hi;
            if (action == null)
                throw new nullpointerexception();
            node<k,v>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getfence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        k k = current.key;
                        current = current.next;
                        action.accept(k);
                        if (map.modcount != expectedmodcount)
                            throw new concurrentmodificationexception();
                        return true;
                    }
                }
            }
            return false;
        }

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

    static final class valuespliterator<k,v>
        extends hashmapspliterator<k,v>
        implements spliterator<v> {
        valuespliterator(hashmap<k,v> m, int origin, int fence, int est,
                         int expectedmodcount) {
            super(m, origin, fence, est, expectedmodcount);
        }

        public valuespliterator<k,v> trysplit() {
            int hi = getfence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new valuespliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedmodcount);
        }

        public void foreachremaining(consumer<? super v> action) {
            int i, hi, mc;
            if (action == null)
                throw new nullpointerexception();
            hashmap<k,v> m = map;
            node<k,v>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedmodcount = m.modcount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedmodcount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                node<k,v> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p.value);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modcount != mc)
                    throw new concurrentmodificationexception();
            }
        }

        public boolean tryadvance(consumer<? super v> action) {
            int hi;
            if (action == null)
                throw new nullpointerexception();
            node<k,v>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getfence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        v v = current.value;
                        current = current.next;
                        action.accept(v);
                        if (map.modcount != expectedmodcount)
                            throw new concurrentmodificationexception();
                        return true;
                    }
                }
            }
            return false;
        }

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

    static final class entryspliterator<k,v>
        extends hashmapspliterator<k,v>
        implements spliterator<map.entry<k,v>> {
        entryspliterator(hashmap<k,v> m, int origin, int fence, int est,
                         int expectedmodcount) {
            super(m, origin, fence, est, expectedmodcount);
        }

        public entryspliterator<k,v> trysplit() {
            int hi = getfence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new entryspliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedmodcount);
        }

        public void foreachremaining(consumer<? super map.entry<k,v>> action) {
            int i, hi, mc;
            if (action == null)
                throw new nullpointerexception();
            hashmap<k,v> m = map;
            node<k,v>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedmodcount = m.modcount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedmodcount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                node<k,v> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modcount != mc)
                    throw new concurrentmodificationexception();
            }
        }

        public boolean tryadvance(consumer<? super map.entry<k,v>> action) {
            int hi;
            if (action == null)
                throw new nullpointerexception();
            node<k,v>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getfence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        node<k,v> e = current;
                        current = current.next;
                        action.accept(e);
                        if (map.modcount != expectedmodcount)
                            throw new concurrentmodificationexception();
                        return true;
                    }
                }
            }
            return false;
        }

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

    /* ------------------------------------------------------------ */
    // linkedhashmap support


    /*
     * the following package-protected methods are designed to be
     * overridden by linkedhashmap, but not by any other subclass.
     * nearly all other internal methods are also package-protected
     * but are declared final, so can be used by linkedhashmap, view
     * classes, and hashset.
     */

    // create a regular (non-tree) node
    node<k,v> newnode(int hash, k key, v value, node<k,v> next) {
        return new node<>(hash, key, value, next);
    }

    // for conversion from treenodes to plain nodes
    node<k,v> replacementnode(node<k,v> p, node<k,v> next) {
        return new node<>(p.hash, p.key, p.value, next);
    }

    // create a tree bin node
    treenode<k,v> newtreenode(int hash, k key, v value, node<k,v> next) {
        return new treenode<>(hash, key, value, next);
    }

    // for treeifybin
    treenode<k,v> replacementtreenode(node<k,v> p, node<k,v> next) {
        return new treenode<>(p.hash, p.key, p.value, next);
    }

    /**
     * reset to initial default state.  called by clone and readobject.
     */
    void reinitialize() {
        table = null;
        entryset = null;
        keyset = null;
        values = null;
        modcount = 0;
        threshold = 0;
        size = 0;
    }

    // callbacks to allow linkedhashmap post-actions
    void afternodeaccess(node<k,v> p) { }
    void afternodeinsertion(boolean evict) { }
    void afternoderemoval(node<k,v> p) { }

    // called only from writeobject, to ensure compatible ordering.
    void internalwriteentries(java.io.objectoutputstream s) throws ioexception {
        node<k,v>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (node<k,v> e = tab[i]; e != null; e = e.next) {
                    s.writeobject(e.key);
                    s.writeobject(e.value);
                }
            }
        }
    }

    /* ------------------------------------------------------------ */
    // tree bins

    /**
     * entry for tree bins. extends linkedhashmap.entry (which in turn
     * extends node) so can be used as extension of either regular or
     * linked node.
     */
    static final class treenode<k,v> extends linkedhashmap.entry<k,v> {
        treenode<k,v> parent;  // red-black tree links
        treenode<k,v> left;
        treenode<k,v> right;
        treenode<k,v> prev;    // needed to unlink next upon deletion
        boolean red;
        treenode(int hash, k key, v val, node<k,v> next) {
            super(hash, key, val, next);
        }

        /**
         * returns root of tree containing this node.
         */
        final treenode<k,v> root() {
            for (treenode<k,v> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * ensures that the given root is the first node of its bin.
         */
        static <k,v> void moveroottofront(node<k,v>[] tab, treenode<k,v> root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;
                treenode<k,v> first = (treenode<k,v>)tab[index];
                if (root != first) {
                    node<k,v> rn;
                    tab[index] = root;
                    treenode<k,v> rp = root.prev;
                    if ((rn = root.next) != null)
                        ((treenode<k,v>)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                assert checkinvariants(root);
            }
        }

        /**
         * finds the node starting at root p with the given hash and key.
         * the kc argument caches comparableclassfor(key) upon first use
         * comparing keys.
         */
        final treenode<k,v> find(int h, object k, class<?> kc) {
            treenode<k,v> p = this;
            do {
                int ph, dir; k pk;
                treenode<k,v> pl = p.left, pr = p.right, q;
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableclassfor(k)) != null) &&
                         (dir = comparecomparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

        /**
         * calls find for root node.
         */
        final treenode<k,v> gettreenode(int h, object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        /**
         * tie-breaking utility for ordering insertions when equal
         * hashcodes and non-comparable. we don't require a total
         * order, just a consistent insertion rule to maintain
         * equivalence across rebalancings. tie-breaking further than
         * necessary simplifies testing a bit.
         */
        static int tiebreakorder(object a, object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getclass().getname().
                 compareto(b.getclass().getname())) == 0)
                d = (system.identityhashcode(a) <= system.identityhashcode(b) ?
                     -1 : 1);
            return d;
        }

        /**
         * forms tree of the nodes linked from this node.
         * @return root of tree
         */
        final void treeify(node<k,v>[] tab) {
            treenode<k,v> root = null;
            for (treenode<k,v> x = this, next; x != null; x = next) {
                next = (treenode<k,v>)x.next;
                x.left = x.right = null;
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    k k = x.key;
                    int h = x.hash;
                    class<?> kc = null;
                    for (treenode<k,v> p = root;;) {
                        int dir, ph;
                        k pk = p.key;
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableclassfor(k)) == null) ||
                                 (dir = comparecomparables(kc, k, pk)) == 0)
                            dir = tiebreakorder(k, pk);

                        treenode<k,v> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            root = balanceinsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveroottofront(tab, root);
        }

        /**
         * returns a list of non-treenodes replacing those linked from
         * this node.
         */
        final node<k,v> untreeify(hashmap<k,v> map) {
            node<k,v> hd = null, tl = null;
            for (node<k,v> q = this; q != null; q = q.next) {
                node<k,v> p = map.replacementnode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        /**
         * tree version of putval.
         */
        final treenode<k,v> puttreeval(hashmap<k,v> map, node<k,v>[] tab,
                                       int h, k k, v v) {
            class<?> kc = null;
            boolean searched = false;
            treenode<k,v> root = (parent != null) ? root() : this;
            for (treenode<k,v> p = root;;) {
                int dir, ph; k pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableclassfor(k)) == null) ||
                         (dir = comparecomparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        treenode<k,v> q, ch;
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            return q;
                    }
                    dir = tiebreakorder(k, pk);
                }

                treenode<k,v> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    node<k,v> xpn = xp.next;
                    treenode<k,v> x = map.newtreenode(h, k, v, xpn);
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((treenode<k,v>)xpn).prev = x;
                    moveroottofront(tab, balanceinsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * removes the given node, that must be present before this call.
         * this is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. so instead we swap the tree
         * linkages. if the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (the test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        final void removetreenode(hashmap<k,v> map, node<k,v>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            treenode<k,v> first = (treenode<k,v>)tab[index], root = first, rl;
            treenode<k,v> succ = (treenode<k,v>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            treenode<k,v> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
                treenode<k,v> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                treenode<k,v> sr = s.right;
                treenode<k,v> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else {
                    treenode<k,v> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                treenode<k,v> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }

            treenode<k,v> r = p.red ? root : balancedeletion(root, replacement);

            if (replacement == p) {  // detach
                treenode<k,v> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveroottofront(tab, r);
        }

        /**
         * splits nodes in a tree bin into lower and upper tree bins,
         * or untreeifies if now too small. called only from resize;
         * see above discussion about split bits and indices.
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        final void split(hashmap<k,v> map, node<k,v>[] tab, int index, int bit) {
            treenode<k,v> b = this;
            // relink into lo and hi lists, preserving order
            treenode<k,v> lohead = null, lotail = null;
            treenode<k,v> hihead = null, hitail = null;
            int lc = 0, hc = 0;
            for (treenode<k,v> e = b, next; e != null; e = next) {
                next = (treenode<k,v>)e.next;
                e.next = null;
                if ((e.hash & bit) == 0) {
                    if ((e.prev = lotail) == null)
                        lohead = e;
                    else
                        lotail.next = e;
                    lotail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hitail) == null)
                        hihead = e;
                    else
                        hitail.next = e;
                    hitail = e;
                    ++hc;
                }
            }

            if (lohead != null) {
                if (lc <= untreeify_threshold)
                    tab[index] = lohead.untreeify(map);
                else {
                    tab[index] = lohead;
                    if (hihead != null) // (else is already treeified)
                        lohead.treeify(tab);
                }
            }
            if (hihead != null) {
                if (hc <= untreeify_threshold)
                    tab[index + bit] = hihead.untreeify(map);
                else {
                    tab[index + bit] = hihead;
                    if (lohead != null)
                        hihead.treeify(tab);
                }
            }
        }

        /* ------------------------------------------------------------ */
        // red-black tree methods, all adapted from clr

        static <k,v> treenode<k,v> rotateleft(treenode<k,v> root,
                                              treenode<k,v> p) {
            treenode<k,v> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }

        static <k,v> treenode<k,v> rotateright(treenode<k,v> root,
                                               treenode<k,v> p) {
            treenode<k,v> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }

        static <k,v> treenode<k,v> balanceinsertion(treenode<k,v> root,
                                                    treenode<k,v> x) {
            x.red = true;
            for (treenode<k,v> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateleft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateright(root, xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateright(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateleft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

        static <k,v> treenode<k,v> balancedeletion(treenode<k,v> root,
                                                   treenode<k,v> x) {
            for (treenode<k,v> xp, xpl, xpr;;)  {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateleft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        treenode<k,v> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateright(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateleft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateright(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        treenode<k,v> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateleft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateright(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

        /**
         * recursive invariant check
         */
        static <k,v> boolean checkinvariants(treenode<k,v> t) {
            treenode<k,v> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (treenode<k,v>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkinvariants(tl))
                return false;
            if (tr != null && !checkinvariants(tr))
                return false;
            return true;
        }
    }

}

阅后感

咱主要是写java中,理论上代码咱应该都认识,但是为什么咋一看会觉得看不懂呢?看不懂,意思是看了一遍,不知道代码想干什么。或者知道代码想干什么,但是不知道为什么那么干。

看不懂,一部分是因为一些不常见的操作太多,而且连在一起,所以产生了畏难情绪。比如一些与操作、移位运算。

一部分是因为运用了一些算法,对该算法不太了解,自然不太能看懂那段代码是想干什么。比如将链表转为红黑树。

总结:看代码要一行一行看,看一行注释一行,不明白的多搜索相关资料,不要图快。

代码感受

map在进行扩容时,直接通过计算得到元素是应该不动还是应该移动n个位置,这里确实很精妙。