implements Map<K,V>, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L;

/*

//初始容量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

//负载因子默认值

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//bin(桶)容量大于等于8时，链表转化成红黑树

static final int TREEIFY_THRESHOLD = 8;

//bin(桶)容量小于等于6时，红黑树转化成链表

static final int UNTREEIFY_THRESHOLD = 6;

//容量最小64时才会转会成红黑树

static final int MIN_TREEIFY_CAPACITY = 64;

//用于fail-fast的，记录HashMap结构发生变化(数量变化或rehash)的数目

transient int modCount;

//HashMap 的实际大小，可能不准(因为当你拿到这个值的时候，可能又发生了变化)

transient int size;

// 扩容的门槛，如果初始化时，给定数组大小的话，通过tableSizeFor 方法计算，永远接近于 2 的幂次方

// 如果是通过 resize 方法进行扩容后，大小 = 数组容量 * 0.75

int threshold;

//存放数据的数组

transient Node<K,V>[] table;

//bin node 节点

static class Node<K,V> implements Map.Entry<K,V> {//Map.Entry是个接口

final int hash;//当前node的hash值

final K key;

V value;

Node<K,V> next;//指向当前node的下一个节点，构成单向链表

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() {

//Objects.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;

}

}

//Tree bins 红黑树

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);

}

//找到红黑树的根节点，根据根节点没有父节点来判断

final TreeNode<K,V> root() {

for (TreeNode<K,V> r = this, p;;) {

if ((p = r.parent) == null)

return r;

r = p;

}

}

//把给定的root放到根节点上去

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {

int n;

if (root != null && tab != null && (n = tab.length) > 0) {

int index = (n - 1) & root.hash;

TreeNode<K,V> first = (TreeNode<K,V>)tab[index];//找到当前树的根节点

//如果root不是根节点，就把root放到根节点上去，分成2步

//1:解决root下面节点的问题

//2:把root放到当前根节点first的左边去

if (root != first) {

Node<K,V> rn;

tab[index] = root;

TreeNode<K,V> rp = root.prev;

//下面的两个if是为了解决步骤1。

// 把root的next挂在自己prev的后面即可

// 就是把自己摘掉，后面一位和前面一位连接起来

if ((rn = root.next) != null)

((TreeNode<K,V>)rn).prev = rp;

if (rp != null)

rp.next = rn;

//这个if解决了步骤2 把root当作根节点，并且设置prev为null

if (first != null)

first.prev = root;

root.next = first;

root.prev = null;

}

assert checkInvariants(root);

}

}

//根据hash和key查找红黑树中节点是否已经存在。策略如下

//1：从根节点递归查找

//2：根据 hashcode，比较查找节点，左边节点，右边节点之间的大小，查找节点大于左边节点，取左边节点，查找小于右边节点，取右边节点。

//3：判断查找节点和 2 步取的节点是否相等，相等返回，不等重复 2，3 两步。

//4：2，3不中的话,如果key实现了Comparable接口，使用compareTo进行比较大小，重复2

//5: 判断节点位置时，需要关心一边节点为空的情况

//6：1~5如果都没有命中，默认从右边开始往下递归

//7：这样查找的好处就是比较快，最大的循环次数是树的最大深度

//如果树比较平衡，查询还是很快的。

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;

//1:如果key的hash值小于当前节点,取当前节点左边的节点

if ((ph = p.hash) > h)

p = pl;

//2:如果key的hash值大于当前节点,取当前节点右边的节点

else if (ph < h)

p = pr;

//2.1:这里没有判断相等的情况，因为相等时，p就是当前节点，不需要判断

//3:如果key的hash值等于当前节点，直接返回当前节点，结束递归查找

else if ((pk = p.key) == k || (k != null && k.equals(pk)))

return p;

//4:如果当前节点的左节点为空，说明左边已经查找完了，再去判断右节点

else if (pl == null)

p = pr;

//5:如果当前节点的右节点为空，说明右边已经查找完了，就再去判断左节点

//4和5防止左右一边为空，提前退出的情况

else if (pr == null)

p = pl;

//6: 不采用hashcode的判断大小的话，可以选择compareTo自定义的判断方法

//只需要自己实现key的Comparable就好了

else if ((kc != null ||

(kc = comparableClassFor(k)) != null) &&

(dir = compareComparables(kc, k, pk)) != 0)

p = (dir < 0) ? pl : pr;

//7:如果当前节点和key的hashcode相等，但是key的值不等，并且没有实现

//comparable的话，只能用最简单的方法，先匹配右边，匹配不到匹配左边

else if ((q = pr.find(h, k, kc)) != null)

return q;

//8:右节点找不到，再递归查找左节点

else

p = pl;

//如果p不为空需要一直递归循环

} while (p != null);

//如果找不到，返回null

return null;

}

/**

final TreeNode<K,V> getTreeNode(int h, Object k) {

return ((parent != null) ? root() : this).find(h, k, null);

}

/**

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;

}

/**

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);

}

/**

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;

}

//红黑树中加入节点

//在计算新增的节点挂在那个节点上，是线程不安全的，

//关键在于没有锁住tab,table可能是在动态的变化的

//1:首先判断新增的节点在红黑树上是不是已经存在。

//2:不在的话，根据hashcode，或者自定义的comparTo,递归找到要挂载的节点

//3:和要挂载的节点建立父子，前后关系

//4:判断是否需要着色，旋转。

//5:对红黑树的根节点进行校验

//h：key 的hash值

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;

// p hash 值大于 h，说明 p 在 h 的右边

if ((ph = p.hash) > h)

dir = -1;

// p hash 值小于 h，说明 p 在 h 的左边

else if (ph < h)

dir = 1;

//要放进去key在当前树中已经存在了(equals来判断)

else if ((pk = p.key) == k || (k != null && k.equals(pk)))

return p;

//自己实现的Comparable的话，不能用hashcode比较了，需要用compareTo

else if ((kc == null &&

//得到key的Class类型，如果key没有实现Comparable就是null

(kc = comparableClassFor(k)) == null) ||

//当前节点pk和入参k不等

(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;

//找到和当前hashcode值相近的节点(当前节点的左右子节点其中一个为空即可)

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;

//balanceInsertion 对红黑树进行着色或旋转，以达到更多的查找效率，着色或旋转的几种场景如下

//着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色；如果父亲是红色，那么必须通过重新

//着色或者旋转的方法，再次达到红黑树的5个约束条件

//旋转： 父亲是红色，叔叔是黑色时(前提是当前)

//如果当前节点是父亲的右节点，则进行左旋

//如果当前节点是父亲的左节点，则进行右旋

//moveRootToFront 方法是把算出来的root放到根节点上

moveRootToFront(tab, balanceInsertion(root, x));

return null;

}

}

}

/**

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);

}

/**

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;

}

}

}

}

}

/**

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;

}

}

/* ---------------- Static utilities -------------- */

/**

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

/**

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