关键属性
static final int `DEFAULT_INITIAL_CAPACITY*`= 1 << 4; // aka 16 默认初始容量为16
static final int `MAXIMUM_CAPACITY` = 1 << 30; //最大容量 恰好为int的最大值除以2
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子
static final int TREEIFY_THRESHOLD = 8 //树化阈值
static final int UNTREEIFY_THRESHOLD = 6;//红黑树转化回链表阈值
static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量为64
int threshold; // hashmap阈值
final float loadFactor; //负载因子
构造方法
无参构造
public HashMap() { //初始容量在第一次put的时候才会显化
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
带参构造函数
//带参构造函数一
public HashMap(int initialCapacity) { //自定义容量
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//带参数构造函数二
public HashMap(int initialCapacity, float loadFactor) { //自定义容量和负载因子
if (initialCapacity < 0) //初始化容量小于0 则抛出非法数据异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //初始化容量大于最大容量 则等于最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果负载因子小于等于0，或者不是一个数字 则抛出非法数字
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//带参构造函数三
public HashMap(Map<? extends K, ? extends V> m) { //传入一个map集合的构造方法
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
选取带参构造函数二进行分析：
逻辑流程：
①传入相应的自定义的初始容量参数
initialCapacity和负载因子loadFactor。
②进行相应检查判断
③赋值loadFactor和使用tableSizeFor()方法来求出相应容量
注意：此时只是为threshold属性赋值了，仍然没有初始化容量，初始化真正时刻是在第一次调用put()方法时显化
tableSizeFor()
static final int tableSizeFor(int cap) { //tableSizeFor的作用就是，如果传入A，当A大于0，小于定义的最大容量时
int n = cap - 1; //如果A是2次幂则返回A，否则将A转化为一个比A大且差距最小的2次幂。
n |= n >>> 1; //例如传入7返回8，传入8返回8，传入9返回16
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8; //该方法可以保证hashmap的容量一定是2的幂次方
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
put（）方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) { //hash根据key算出来的hash值 onlyIfAbsent 如果当前位置已经有一个值 是否替换 false是替换 true是不替换
Node<K,V>[] tab; Node<K,V> p; int n, i; //evict 表示是否在进行表的模式的创建 false则表是在创建模式
//如果主干上的table为空或者 长度为0 则进行resize（），来调整table的长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //resize()既对数组进行了初始化，又可以进行扩容 这里是第一次put时，对数组进行初始化
if ((p = tab[i = (n - 1) & hash]) == null) //将计算得到的hash值与数组长度进行比较 (n - 1) & hash操作等价于取模运算 不过前者效率更高
tab[i] = newNode(hash, key, value, null); //位置为空时 将i位置上赋值一个Node对象
else { //位置不为空时
Node<K,V> e; K k;
if (p.hash == hash && //如果这个位置的old节点与new节点的key完全相同 old节点p = tab[i = (n - 1) & hash]
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //则e=p
else if (p instanceof TreeNode) //判断是p是不是一个红黑树节点 ，是的话就走红黑树的逻辑
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //p与新节点既不完全相同，p也不是treeNode的实例对象
for (int binCount = 0; ; ++binCount) { //遍历链表
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); //树化转换的此时虽然binCount==7了 但新节点仍然插入了链表 该时刻有了第九个元素 JDK1.8使用的是尾插法
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 链表长度>=8 进行树化
treeifyBin(tab, hash); //binCount＝＝7 就会进行树化 进行时树化的时刻已经有了9个节点
break;
}
if (e.hash == hash && //如果遍历过程中链表中的元素与新添加的元素完全相同，则跳出循环
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key 当前的key已经存在了，发生了hash冲突，那么进行put方法时，会将他在链表中的他的上一个元素的值返回
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //条件成立则，将oldvalue的值替换成newvalue，返回oldvalue；否则不替换，然后返回oldvalue
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //记录修改次数 用来做快速失败
if (++size > threshold) //如果元素数量大于阈值 则进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
putVal（）逻辑流程分析：
①、判断表是否空或者表长是否为0（此时可能只是调用了构造方法，还未初始化容量），满足条件则调用resize（）方法进行初始化。
②、通过相应的条件分支语句，找到要插入的位置，位置为空则new一个Node对象，否则进入③。
③、此时位置不为空，首先判断old节点是否和new节点的key、hash相同，相同则获取old节点，进行最后面的判断，满足条件则进行返回oldValue，且对行value属性进行覆盖。
④、进行到这一步说明hash值相等，但是key值不相等，发生了hash碰撞。故，需要进行节点数据类型判断，如若是红黑树节点，则走红黑树的逻辑。否则就是链表节点，遍历链表，尾插法插入到最后；同时判断加上这个节点整个链表上的节点是否大于8（即此时链表上有第九个节点）进行树化，因为是先加入节点，然后才有binCount ++。
⑤、最后判断加入该节点是否会大于当前hashMap的阈值，大于则调用resize（）方法进行扩容。
resize()
final Node<K,V>[] resize() { // 初始化或者扩容
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //①使用默认构造方法创建的hashMap第一次使用 未初始化时 oldThr==threshold==0 ②自定义的构造方法是含有初始容量和负载因子的 即阈值存在
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // MAXIMUM_CAPACITY = 1 << 30 当容量超过最大值时，容量设置为int的最大值 1 << 31
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //新数组的2倍小于最大容量且原来数组的长度大等于16
newThr = oldThr << 1; // double threshold //扩容为2倍 阈值也为2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold 调用带参构造函数创建时对应的情况
newCap = oldThr; //oldThr==threshold==tablesizefor（自定义容量） 为2的幂次方
else { // zero initial threshold signifies using defaults 调用默认构造方法创建时对应情况
newCap = DEFAULT_INITIAL_CAPACITY; //初始化时候给的阈值 默认时16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //阈值为;16*0.75 = 12
}
if (newThr == 0) { //配合带参构造函数情况 进行阈值计算 相当于initialCapacity*loadFactor
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) { //扩容后，1.8不重新计算元素的新位置 而是直接用了原位置+原数组长度这种巧妙的方式 与重新计算hash得到结果相同
for (int j = 0; j < oldCap; ++j) { //通过原容量遍历原数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { //有元素才转移 判断node节点是否为空 不为空则将j位置上的值保存到e中 然后将该位置置为空
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); //j为数组中的位置
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) { //计算出来最高位为0的元素
if (loTail == null) //先将值算出来 放在一个链表中 统一的移动到新链表中 jdk1.7中 将元素一个一个的移动到新链表中
loHead = e; // loHead 算出来值小的链表的头
else
loTail.next = e; //lo链表为最高位为0的元素 转移后直接就在原位置 loTail算出来值小的链表的尾
loTail = e;
}
else { //eg.: 0101 0101 & 0001 000 == 00010000 不为0
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;
}
使用resize（）初始化
1. newCap = DEFAULT_INITIAL_CAPACITY; 新的容量等于默认值16
2. *newThr = (int)(DEFAULT_LOAD_FACTOR \* >DEFAULT_INITIAL_CAPACITY);*
3. *threshold = newThr; 阈值等于16\*0.75*
4. *Node[] newTab = (Node[])new Node[newCap];*
5. *table = newTab; 将新的node数组赋值给table，然后return newTab*
6.
7. *如果是自定义的构造方法则会执行resize中的：*
8. *int oldThr = threshold;*
9. *newCap = oldThr; 新的容量等于threshold，这里的threshold都是2的>倍数，原因在*
10. *于传入的数都经过tableSizeFor方法，返回了一个新值，上面解释过*
11. *float ft = (float)newCap \* loadFactor;*
12. *newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?*
13. *(int)ft : Integer.MAX_VALUE);*
14. *threshold = newThr; 新的阈值等于 (int)(新的容量\负载因子)*
15. *Node[] newTab = (Node[])new Node[newCap];*
16. table = newTab; return newTab;
红黑树扩容split（）
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; //高位链表 索引位置为：原位置+oldCap
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; //高位链表中元素的个数有多少 高位计数
}
}//for循环遍历链表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) //低位个数<=6 转化为链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified) hiHead是空 则直接将整棵红黑树进行转移
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null) //loHead是空 则直接将整颗红黑树进行转移
hiHead.treeify(tab);
}
}
}
红黑树链表化 untreeify()
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null; //hd指向头节点 tl指向尾节点
for (Node<K,V> q = this; q != null; q = q.next) { //从调用方法的节点开始遍历，将所有节点转转为链表节点
Node<K,V> p = map.replacementNode(q, null); //调用replacementNode方法构建链表节点
if (tl == null) //只有一个节点 将hd赋值为当前节点
hd = p;
else
tl.next = p; //尾插进链表
tl = p;
}
return hd; //返回转换链表的头节点
}
hash(key)
static final int hash(Object key) { //此处如果传入的int类型的值：①向一个Object类型赋值一个int的值时，会将int值自动封箱为Integer。②integer类型的hashcode都是他自身的值，即h=key；h >>> 16为无符号右移16位，低位挤走，高位补0；^ 为按位异或，即转成二进制后，相异为1，相同为0，由此可发现，当传入的值小于 2的16次方-1 时，调用这个方法返回的值，都是自身的值。
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //最终结果key原来的hash值的高16位和低16位 进行了异或操作 达到的效果就是①混合原始hash值的高低位，以次来加大随机性 ②低16位同时拥有这高16位的信息
}
树化 treeifyBin()
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(); //数组长度小于最小树化容量时（64）时 不会进行树化 只会进行扩容
else if ((e = tab[index = (n - 1) & hash]) != null) { //根据hash做&运算，得到链表的首节点
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); //do--while将原来的节点改用TreeNode节点代替，加上prev指针生成双向链表
if ((tab[index] = hd) != null) //把转化后的双向链表替换原来的单链表
hd.treeify(tab); //真正的进行树化
}
}
replacementTreeNode()
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { //next==null
return new TreeNode<>(p.hash, p.key, p.value, next);
}
treeify()
final void treeify(Node<K,V>[] tab) { //遍历链表 然后依次将节点插入红黑树中
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) { //x为当前节点
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; //x为要插入的节点
for (TreeNode<K,V> p = root;;) { //从根节点开始遍历 查找属于该节点的位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //h为当前节点hash值
dir = -1; //比较hash值 -1向左走
else if (ph < h)
dir = 1; // 1 向右走
else if ((kc == null && //x的hash和p的hash值相等 则比较key值
(kc = comparableClassFor(k)) == null) || //如果k没有实现comparableClassFor（）接口 或者 x节点和p节点的key相等
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); //使用定义一套规则来比较节点x和节点p的大小，用来决定时向左走还是向右走
TreeNode<K,V> xp = p; // xp赋值为x的父节点,中间变量用于下面给x的父节点赋值
if ((p = (dir <= 0) ? p.left : p.right) == null) { // 判断插入左右子树 dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root); //将红黑树的根节点移动到table中，保证根节点在双向链表的最前面 即将其调整为头节点
}
comparableClassFor()
static Class<?> comparableClassFor(Object x) { // 看是否实现了Comparable接口 如果实现了就返回C的Class类型
if (x instanceof Comparable) { //判断x是否实现了Comparable接口
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks 检验x是否是String接口
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) { //遍历x所有实现接口
if (((t = ts[i]) instanceof ParameterizedType) && //如果x实现了Comparable接口，则返回x的class
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
tieBreakOrder()
static int tieBreakOrder(Object a, Object b) { //比较顺序： 1、hashCode 2、compareTo（） 3、getClass().getName() 4、System.identityHashCode()
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); //System.identityHashCode 是根据对象在内存中的地址算出来的hash值
return d;
}
moveRootToFront()
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { //将root放入头节点的位置
int n; //如果当前索引位置的头节点不是root节点，则将root的上一个节点和下一个节点进行关联
if (root != null && tab != null && (n = tab.length) > 0) { //将root放到头节点的位置，原头节点放在root的next节点上 即原节点成为了root的后继节点
int index = (n - 1) & root.hash; //计算root节点的索引位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //对应位置上的节点应用为first
if (root != first) { //如果该索引位置的头节点不是root节点，则该索引位置的头节点替换成root
Node<K,V> rn; //临时节点rn root的后继节点
tab[index] = root; //将索引位置的节点替换成头节点
TreeNode<K,V> rp = root.prev; //root的前驱节点
if ((rn = root.next) != null) //将root的前驱和root的后继相关联起来
((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); //检查树是否正常 将传入的节点作为根节点，遍历所有节点，校验节点的合法性，主要是保证该树符合红黑树的规则
}
}
get（）方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value; //获取到对象 就将对应的值返回
}
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 && //数组存在 并且 数组长度大于0 并且 索引位置节点存在
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node first节点的hash值和传入的参数hash一样 且和key对象的相等（Interge） 或者 key值相等
((k = first.key) == key || (key != null && key.equals(k))))
return first; //first则为目标节点 直接返回
if ((e = first.next) != null) { //first节点不是目标节点 则继续遍历
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; //所有分支语句都找不到，即相应节点不存在 直接返回空
}
getTreeNode()
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null); //先找到根节点 使用红黑树的根节点调用find方法
}
find()
final TreeNode<K,V> find(int h, Object k, Class<?> kc) { //从调用此方法的节点开始查找，通过hash和key找到相应节点
TreeNode<K,V> p = this;
do { //从p节点开始向下遍历
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) //目标hash < 当前节点hash向左遍历
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节点的左子树为空就直接向右遍历 提高效率
p = pr;
else if (pr == null) //p节点的右子树为空就直接向左遍历
p = pl;
else if ((kc != null || //其他条件都不符合（hash值相等 但key值不相等）
(kc = comparableClassFor(k)) != null) && //进行comparable（）接口实现判断 如若实现则得到依照制定的规则进行赋值
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null) //此处表示key所属类没有实现comparable接口实现，直接指定向p的右边走
return q;
else // pr.find(h, k, kc))==null 直接指定向p的左边走
p = pl;
} while (p != null);
return null;
}
remove()方法
public V remove(Object key) { //找到相应节点 删除并返回节点的值
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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
(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)))) //hash值和key都符合 则p为目标节点
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) //node==p只会出现在p为第一个节点的情况 否则node==p.next
tab[index] = node.next;
else
p.next = node.next; //将node的前驱与其后继进行关联
++modCount; //修改次数
--size;
afterNodeRemoval(node); //共LinkLedHashMap使用
return node; //返回被移除的节点
}
}
return null;
}
removeTreeNode（）
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n; //以下为链表处理 开始
if (tab == null || (n = tab.length) == 0) //表空或者长度为0 则直接返回
return;
int index = (n - 1) & hash; //计算索引位置
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; //首节点置为root
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; //将node的next节点赋值给 succ 将prev节点赋值给pred
if (pred == null) //表示node节点为第一个节点
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 = root.root();
if (root == null
|| (movable //通过root节点来判断红黑树是否太小，如果是则将红黑树转化为链表节点 并返回
&& (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; //以下为红黑树处理 p为要被移除的节点
if (pl != null && pr != null) { //左右节点都不为空
TreeNode<K,V> s = pr, sl; //将s赋值为p的右节点
while ((sl = s.left) != null) // find successor 遍历找到当前右字数中最左边的节点为s 即没有左孩子的节点
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors 交换s和p的颜色
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent 第一次调整 如果s节点为p的右节点 则将p的父节点赋值为s 将s的右节点赋值为p
p.parent = s;
s.right = p; //此时sr和pp节点是与整个树断开的状态
}
else {
TreeNode<K,V> sp = s.parent; //将sp赋值为s的父节点
if ((p.parent = sp) != null) { //将p的父节点赋值为sp
if (s == sp.left)
sp.left = p; //s在左子树上就把p节点替换到左子树上
else
sp.right = p; //s在右子树上就把p节点替换到右子树上
}
if ((s.right = pr) != null) //用来替换p的位置
pr.parent = s;
}
p.left = null; //第二次调整 逻辑为：将断开的pp节点作为s的父节点赋值 sr节点作为p节点的右节点 将p的左节点pl挂到s的左孩子上
if ((p.right = sr) != null)
sr.parent = p; // 将p节点的右节点赋值为sr，如果sr不为空，则将sr的父节点赋值为p节点
if ((s.left = pl) != null)
pl.parent = s; // 将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点赋值为s节点
if ((s.parent = pp) == null)
root = s; //如果pp为空，则p节点为root节点, 交换后s成为新的root节点
else if (p == pp.left)
pp.left = s; // 如果p不为root节点, 并且p是pp的左节点，则将pp的左节点赋值为s节点
else
pp.right = s; // 如果p不为root节点, 并且p是pp的右节点，则将pp的右节点赋值为s节点
if (sr != null)
replacement = sr; //如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
else
replacement = p; //如果sr为空，则s为叶子节点，replacement为p本身，只需要将p节点直接去除即可
}
else if (pl != null) //右子树为空 则直接使用左子树pl成为replacement
replacement = pl;
else if (pr != null) //左子树为空 则直接使用右子树pr成为replacement
replacement = pr;
else
replacement = p; //p本身就是叶子节点 则直接使用自己作为replacement
if (replacement != p) { //第三次调整 p不是叶子节点 使用replacement节点将p节点替换掉 进行平衡调整
TreeNode<K,V> pp = replacement.parent = p.parent; //p不是叶子节点 则将pp节点和replacement节点关联起来
if (pp == null)
root = replacement; //p为root节点 直接将replace节点作为新的root
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); //p不是红色节点则对红黑树平衡没有影响 否则进行删除平衡调整
if (replacement == p) { // detach p是叶子节点则简单删去即可
TreeNode<K,V> pp = p.parent;
p.parent = null; //将p的parent属性置为空 为GC做准备
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
图解removeTreeNode
removeTreeNode图解
总结
1.HashMap 的底层是个 Node 数组（Node<K,V>[] table），在数 组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。
2.增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到 key 的 hashCode 值；2）将 hashCode 的高位参与运算，重新计算 hash 值；3）将计算出来的 hash 值与 “table.length - 1” 进行 & 运算。
3.HashMap 的默认初始容量（capacity）是 16，capacity 必须为 2 的幂次方；默认负载因子（load factor）是 0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。
4.HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。
5.HashMap 在触发扩容后，阈值会变为原来的 2 倍，并且会对所有节点进行重 hash 分布，重 hash 分布后节点的新分布位置只可能有两个：“原索引位置” 或 “原索引+oldCap位置”。例如 capacity 为16，索引位置 5 的节点扩容后，只可能分布在新表 “索引位置5” 和 “索引位置21（5+16）”。
6.HashMap 有 threshold 属性和 loadFactor 属性，但是没有 capacity 属性。初始化时，如果传了初始化容量值，该值是存在 threshold 变量，并且 Node 数组是在第一次 put 时才会进行初始化，初始化时会将此时的 threshold 值作为新表的 capacity 值，然后用 capacity 和 loadFactor 计算新表的真正 threshold 值。
7.当同一个索引位置的节点在增加后达到 9 个时，并且此时数组的长度大于等于 64，则会触发链表节点（Node）转红黑树节点（TreeNode），转成红黑树节点后，其实链表的结构还存在，通过 next 属性维持。链表节点转红黑树节点的具体方法为源码中的 treeifyBin 方法。而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容。
8.当同一个索引位置的节点在移除后达到 6 个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的 untreeify 方法。
9.HashMap 在 JDK 1.8 之后不再有死循环的问题（相对于JDK1.7元素转移时出现死循环），JDK 1.8 之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。实际上，在高并发情况下JDK 1.8 也可能出现死循环，会在链表转移成红黑树或对树进行操作时出现。
10.HashMap 是非线程安全的，在并发场景下使用 ConcurrentHashMap 来代替。
