/*

     * 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.

     *

     * HashMap常被描述为带bins的Hash表。但是bins变大的时候将装换成红黑树，结构像java.util.TreeMap。

     * 绝大多数方法使用普通的扁平的bins。但节点的数到达一定的阀值之后，变成红黑树的方法。

     * 红黑树的bins跟普通的扁平的bins没有差别，只是在数据量多的时候能够快速查找。

     * 大多数情况下，bins的数量不会很多。所以在内部实现上也对于bins数量的检查也会滞后。

     *

     * 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.)

     *

     * 红黑树的bins主要是根据该bin的hashCode排序，但是当两个元素是同一个实现了Comparable接口的对象，

     * 那么排序方式是通过该对象的compareTo方法决定排序。（每一个对象都会进行映射检查）

     * 在理想情况下（元素有不同的hashCode或者排序的）转化成红黑树的复杂运算是值得的。

     *

     * 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.

     *

     * 内部方法中都接受一个hash code的参数，避免每次重复计算

     *

     * 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.)

     *

     * 当bin树化，拆分，非树化，都会保持相同的访问顺序，

     * 通过LinkedHashMap实现树化和扁平化的转换，在插入、删除、访问都会回调LinkedHashMap的实现方法

     *

     * The concurrent-programming-like SSA-based coding style helps

     * avoid aliasing errors amid all of the twisty pointer operations.

     */