一、简介
Hashmap作为一个map，本文主要关注的还是Hashmap的get、put、remove方法实现，其他线程相关的本文就不探讨了，笔者太菜。哈希表的大致结构是数组+链表的形式，也就是
Hashmap.png
二、get和put源码分析
1、get方法
Hashmap get方法如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
可以看到get方法主要调用了getNode方法，并将hash(key)传给了它。
先来看看hash(key）方法：
/**
* 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;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
公式就这么短，hash方法上面的注释说，因为这个哈希表使用2的幂次的掩码，只有在高位有bit不同的哈希值会总是碰撞。（理解一下，因为最后放入的是第(n-1) & hash个槽，也就是hash值按位与n-1，如果有的哈希值只有高位不同，那他们与n-1按位与的结果是相同的）所以我们使用的一个变换使得高位的bit影响到低位，考虑到速度、质量等方面，我们选择使用与移位过后的哈希值按位异或原来的哈希值，这样就将高位影响移到了低位，减少冲突。
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
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;
}
主要就是，first等于tab[(n-1) & hash)]，即用hash函数计算出来的哈希值按位与上n-1，n为哈希表长度。按位与运算和模运算具有这样的联系：a % x = a & (x - 1)。这样就相当于用哈希值模哈希表长来将一个节点放到某个槽里去。得到该放到哪个槽里了之后，再分情况讨论。如果说这个槽是一个树形结构，则调用头节点的.getTreeNode去找到键值对应的节点，如果不是树形结构，就直接遍历这个槽的链表，找到键值Key相等的节点。
2、put方法
put方法如下，主要还是看putVal方法。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
putVal方法如下：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
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)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
大致流程为：
1、看看tab[i = (n - 1) & hash]这个位置存不存在节点，不存在建一个新的节点，next为null，赋给这个位置
2、如果存在节点，即这个该放的槽已经有节点了，就进行以下步骤：
（1）如果这个槽的头节点和要放的对象键值相等，就e=头节点
（2）如果头节点的键值不与要放的键值相等且头节点是一个树节点，也即这个槽的是一个树状结构，头节点调用putTreeVal插入值，然后再赋给e
（3）其他情况，找到链表的末尾，插入一个新节点。插入时如果这个槽的节点数大于等于TREEIFY_THRESHOLD，就调用treefyBin函数，转成红黑树结构。如果找到有节点的key值和要插入的key值相等，提前break。该过程e指向要赋值/新建的节点。
（4）最后是key值已经存在的情况，将新的value赋值给key所在的节点。
3、modCount+1
4、size加1，如果size大于threshold了，调用resize函数
三、bin中的红黑树结构
到现在我们知道，在哈希表中，有的槽是树形结构。树形结构是为了解决这个槽链表过长（冲突发生的多）。来看看TreeNode中的成员变量：
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;
...
有记录父母节点，左孩子，右孩子，以及红/黑标记（red变量）。
1、 treefyBin建树
接下来我们看一下本文二、put方法中提到的2.（3）步骤中调用的treefyBin是个啥玩意：
/**
* 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);
}
}
方法的注释说，将bin（一个槽）中的链表节点都替换成树节点，并且给每个节点记录前驱节点prev和后继节点next。除非表长小于MIN_TREEIFY_CAPACITY就调用resize。可以看到它主要就是先遍历列表，将Node专程TreeNode。最后再用头节点，调用一下treeify函数。
/**
* 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);
}
这段代码就是真正调整为红黑树结构的代码了，大概就是遍历链表，把头节点先作为根节点。有了根结点之后，看一下树结构，如果要插的哈希值大于根节点，就往右走，反之左走。以右走为例，如果根节点的右孩子为空，则将要插入的节点插到这，否则继续根这个右孩子比看往左走还是右走，直到找到一个能插入的位置为止。找到这个位置后，进行插入，插入的代码即为：
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;
}
插入后，还需要调用balanceInsertion方法，这个方法保证插入节点之后，这个树的红黑树性质得以保存，也就是红黑树的插入后的调整算法了。红黑树的性质、左旋右旋等基础可以参考博客：https://www.cnblogs.com/CarpenterLee/p/5503882.html
balanceInsertion
红黑树的性质有：
1.每个节点要么是红色，要么是黑色。
2.根节点必须是黑色
3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
红黑树在插入时为了保持红黑树的性质，需要进行一些调整，调整包括两种操作：（1）改变节点颜色（2）左旋或右旋操作。 这两种操作主要是为了保证3、4条件不被破坏。
根据条件4，新插入的节点必 为红色。
现在来看上文中提到的balanceInsertion方法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; //满足条件4
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);
}
}
}
}
}
}
其中root为根节点，x为当前考虑的红节点（最开始为新插入的节点），方法返回：xp代表x的父节点，xpp为爷爷节点，xppl为爷爷节点的左孩子，xppr为爷爷节点的右孩子，方法返回的是插入x后的树的根节点。代码主要逻辑为以下循环：
- 如果x是根节点，给x标记为黑色，返回x
- 如果x的父节点为黑色，直接返回root（显然此时插入一个红色节点不会破坏条件3，而插入新节点时、调整时也不会打破4条件）
剩下的就是父节点为红色的情况 - 如果父节点是爷爷节点的左孩子，分为几种情况：
-
如果爷爷节点的右孩子存在并且为红色，就把爷爷节点置为红色，把爷爷节点的左右孩子都弄成黑色，下一次循环考虑爷爷节点
情况1.png
-
-
如果爷爷节点的右孩子不存在或为黑
色，且x为父亲的右孩子，此时打破了条件3，则以x的父节点进行左旋，把x的父亲节点赋给x，并调整xp、xpp。此时xp为原来的x，如果xp存在，则把xp置为黑色，xpp若存在则置为红色并以xpp进行右旋。由于此时x的父节点即xp为黑色，下次循环自然终止。
情况2.png
-
如果爷爷节点的右孩子不存在或为黑色，且x为父亲的左孩子，则把父亲置为黑色，并把爷爷节点置为红色后以父亲节点进行右旋。由于此时x的父节点即xp为黑色，下次循环自然终止。
- 如果父节点是爷爷节点的右孩子，类似以上3来讨论，是对称的。
2、getTreeNode
getTreeNode调用的是TreeNode的find方法来找到节点，是红黑树的查找函数。
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;
}
find方法很容易理解，就是按照红黑树的查找规则，如果要查找的哈希值大于当前节点，则往当前节点的右子树找。反之则往左子树找。等于时再比较key值是否相等，等于即查找到了，返回当前节点，如果不等于，看看左子树为空就往右子树走，右子树为空就往左子树走，都不为空就比较Class。一直查找到找到正确节点或是叶子节点为止。
2、删除节点removeTreeNode方法
removeTreeNode方法源码如下：
/**
* 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);
}
主要逻辑为：
1、将要删除的节点，即调用这个方法的TreeNode对象this的前驱节点prev的next指向this的后继节点。
2、如果删除后树太小了就把树转成链表
3、 接下来分为几种情况：
（1）要删除的节点左孩子和右孩子都存在。沿着要删除的节点p的右孩子的左子树一直往左找，找到没有左孩子为止，将最后一个左孩子标记为s。交换p和s的颜色之后，再交换两者的位置。如果原来的s有右孩子，则replacement为s的右孩子，否则为交换后的p。
（2）要删除的节点只存在左孩子。replacement为要删除的节点p的左孩子
（3）要删除的节点只存在右孩子。replacement为要删除的节点p的右孩子
（4）p为叶子节点。replacement为p
4、继续分情况讨论
（1）若replacement != p。用replacement替换掉p。若p为父节点的左孩子，父节点的左孩子变成replacement。若p为父节点的右孩子同理。
（2）若p为黑节点，调用balanceDeletion(root, replacement);保证替换后树的平衡。
（3）若replacement = p，说明p为叶子节点，直接删除即可。
balanceDeletion
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;
}
}
}
}
}
balanceDeletion的主要逻辑为如下循环：
x为当前所在节点，xp为x的父节点。最开始时，x替换了原本的黑色节点，有可能打破了平衡。
一. 若x为根节点，将根节点置为黑色，返回
二. 若x为红色，将x置为黑色，返回。（如果x为红色，直接置为黑色则达到了之前的平衡。）
三. 若x为父节点的左孩子，有以下几个步骤：
-
若父节点的右孩子为红色，则把右孩子置为黑色，父节点置为红色，再以父节点进行左旋。
-
若此时父节点的右孩子为null，x = xp，即开始考虑父节点。
-
若父节点的右孩子为黑色，且父节点的右孩子xpr的左孩子sl和右孩子sr都为黑色或为空，则将xpr置为红色，下次考虑父节点。
balanceDeletion图一.png
-
若父节点的右孩子为黑色且父节点的右孩子xpr的左孩子sl或右孩子sr至少有一个为红色：
（1）若sr存在且为黑色，则将sl置为黑色，xpr置为红色，再以xpr进行右旋。更新xpr为旋转后的x的父节点的右孩子。
（2）若xpr不为null，xpr的颜色置为父节点的颜色，xpr的右孩子置为黑色。
（3）若xp不为null，xp置为黑色，以xp进行左旋
balanceDeletion图二.png
（4）x = root，下一次将结束循环。
四. 若x为父节点的右孩子，与上述情况对称。
四、resize方法
前文已提起resize方法调用的情况，现在来看看resize是怎么做的：
/**
* 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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
上面的注释说，这个方法初始化表的size或是将size扩大两倍。因为是两倍两倍的扩大，每个bin中的元素要么待在原处，要么移到新表中它的2的幂次的地方。
大致流程为：
1.决定新的threshold的值和新的容量（即长度）。threshold用于，当size>threshold时调用resize方法。如果旧表长大于 MAXIMUM_CAPACITY，不进行resize，直接返回旧表。如果旧表长大DEFAULT_INITIAL_CAPACITY（默认的初始化表长）且它的两倍小于MAXIMUM_CAPACITY，新threshold为旧的threshold左移一位（即乘以二），新的长度也为就长度乘以二。如果旧表为空且旧的threshold，新长度为旧的threshold。如果旧表长为0旧threshold也为0，新长度为 DEFAULT_INITIAL_CAPACITY，默认初始长度，新的threshold为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY，默认的负载因子乘以默认的初始容量。
2.建新表。申请新的长度（newCap）的内存空间：
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
3.拷贝旧表的值，并把旧表的每个槽置为null节省内存。遍历每个旧表每个槽，用e指向头节点，如果这个槽只有一个头节点e，旧把这个节点放到新表中第e.hash & (newCap - 1)槽里。如果有多个节点且e为树节点，调用e.split：
/**
* 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);
}
}
}
把树节点拆成两个链表，一部分的哈希值按位与旧表长为0，一部分不为0，再看这两个链表，如果链表长度小于等于UNTREEIFY_THRESHOLD，就调用untreeify把TreeNode替换成Node。否则再调用treeify把这链表弄成树结构。
回到resize方法，如果是有多个节点的链表，类似TreeNode的split，看节点的哈希值与旧表长按位与的结果是否为0，分成两条链表，为0放入loHead，为1放入hiHead。最后把loHead放入新表的j位（j为当前遍历到的旧表槽的下标），hiHead放到j+oldCap（原表长）位。
四、 remove源码分析
remove方法代码为：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
这主要调用了removeNode方法：
/**
* 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;
}
其中hash为要删除的键值的hash值经由hash函数二次哈希的哈希值，key为要删除的键值。
removeNode的主要逻辑为：
- 判断表是否为空以及要删除的键值的哈希值对应的哈希表中的槽是否为空
- 查找到要删除的节点。看键值的哈希值对应的槽，如果槽的头节点的类型不为TreeNode，即槽的数据结构为链表，则遍历这条链表，找到键值相等、哈希值相等的节点，计为node。如果头节点的类型为TreeNode，即槽的数据结构为红黑树，则调用TreeNode的getTreeNode方法找到要删除的节点，标记为node。
- 删除节点。如果node不为空且node的value与要删除的对象的value相等，执行删除操作。如果node为TreeNode类型，调用TreeNode的removeTreeNode方法来删除节点。否则将node的前一个节点的next = e.next，则从链表中删除了node。
- 删除后的modCount、size的变更。
五、结语
目前就看了这些，待填的坑有修饰table、size、entrySet、modCount等变量的transient关键字，modCount的作用等等，Emmm，HashMap的内容还是挺多的，希望能来填坑.jpg
网友评论