总结：
1.HashMap中有一个叫table的Node数组。
2.这个数组存储了Node类的对象。HashMap类有一个叫做Node的内部类。这个Node类包含了key-value作为实例变量。
3.每当往Hashmap里面存放key-value对的时候，都会为它们实例化一个Node对象，这个Node对象就会存储在前面提到的Node数组table中。根据key的hashcode()方法计算出来的hash值来决定。 hash值用来计算key在Entry数组的索引。
2.2.3 resize
//不使用红黑树的阀值
static final int UNTREEIFY_THRESHOLD =
6;
//使用红黑树的阀值
static final int TREEIFY_THRESHOLD =
8;
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) {
//hash表达到最大时，返回旧的hash表。
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
//初始化带指定容量因子和碰撞因子的hashmap。
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;
@SuppressWarnings({
"rawtypes",
"unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])
new Node[newCap];
table = newTab;
if (oldTab !=
null) {
//循环遍历，将旧的hash表中的数据复制到新的hash表中。
for (
int j =
0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) !=
null) {
oldTab[j] =
null;
if (e.next ==
null)
newTab[e.hash & (newCap -
1)] = e;
else if (e
instanceof TreeNode)
((TreeNode<K,V>)e).split(
this, newTab, j, oldCap);
else {
// preserve order
//拆分链表
Node<K,V> loHead =
null, loTail =
null;
Node<K,V> hiHead =
null, hiTail =
null;
Node<K,V> next;
do {
next = e.next;
//用(e.hash & oldCap)规则切割链表，为零在loHead，否则在hiHead
if ((e.hash & oldCap) ==
0) {
if (loTail ==
null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail ==
null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
}
while ((e = next) !=
null);
if (loTail !=
null) {
loTail.next =
null;
newTab[j] = loHead;
}
if (hiTail !=
null) {
hiTail.next =
null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
//拆分红黑树
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) {
//UNTREEIFY_THRESHOLD 使用红黑树的阀值
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);
}
}
}
//链表构造法
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;
}
//红黑树的构造方法
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);
}
