深入理解HashMap
2020-10-11 本文已影响0人
CDF_cc7d
简述
HashMap是一种比较常见的map子类，是由数组+链表组成(JDK8以后采用的是数组+链表+红黑树的形式)。
元素是以键值对的形式存在，并且允许使用null作为键和值存入其中。另外HashMap是无序的(有序的可以使用LinkHashMap)，且是线程不安全的(线程安全的可以使用ConcurrentHashMap)。
首先看下HashMap的几个构造方法:
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
第一个就是最常见的无参构造方法，这个构造方法仅仅是初始化了加载因子，DEFAULT_LOAD_FACTOR为0.75。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
接下来这两个可以一起看:
- 单参数的构造方法就是将初始容量传入，然后加载因子设置成默认值，然后调用两个参数的构造方法。
- 两个参数的构造方法控制了初始容量不可小于0，并且不能超过最大容量数，加载因子也不能小于0.最后调用tableSizeFor方法进行HashMap的阈值的初始化。
tableSizeFor方法待会讲。这里我们看到构造方法里面我们有看到三个参数:loadFactor，threshold和initialCapacity。默认情况下加载因子为0.75，初始容量是16，阈值则为loadFactor * initialCapacity，一旦HashMap的size超过了阈值以后，HashMap就会进行一次resize操作。
为什么要设置这个加载因子？
当加载因子增大，意味着到时候填充的元素就越多了(因为扩容的门槛上升)，空间利用率提升了，但是hash冲突的概率就会增大会降低查找效率，是一种时间换空间的做法。当加载因子减少，意味着填充的元素越少(扩容门槛的下降会导致插入没有多少元素就会进行一次扩容)，这样空间利用率就低了，但是hash冲突的概率会降低提升了查找效率，是一种以空间换时间的做法。这样可以根据项目本身的需要来设置不同的加载因子
默认加载因子为什么是0.75?
注释里面已经有给出，下面这段注释大致意思是说HashMap的Node分步频率服从λ为0.5的泊松分布，当长度为16的数组中存入了12个数据的时候，其中一个链表的长度为8的概率只有 0.00000006(链表长度大于8的时候会转化成红黑树)
* 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
好了，接下来看下tableSizeFor的代码
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这方法其实是算出最接近当前cap的2的n次幂值。第一步减1主要是为了防止当前cap正好是2的n次幂值。为什么要这么做呢？我们举个栗子：假设当前cap是16。
- int n = cap - 1(n = 15)
- n |= n>>>1 (n先右移一位变成0b00111即7 ，然后做或运算得0b01111即15)
- n |= n>>>2 (n先右移两位变成0b00011即3，然后做或运算得0b01111即15)
- n |= n>>>4 (n先右移三位变成0b00000即0，然后做或运算得0b01111即15)
- n |= n>>>8 (n先右移四位变成0b00000即0，然后做或运算得0b01111即15)
- n |= n>>>16 (n先右移四位变成0b00000即0，然后做或运算得0b01111即15)
- 当前n必然小于最大容量值，那么最后的结果就是16。
如果第一步没有减1的操作，那么最后的结果就是是32，这样会浪费大量的空间。我们做tableSizeFor的操作目的就是获得最接近当前cap的2的n次幂值，所以当cap等于16的时候最后的结果应该是16而非32。
上面的步骤完全没有体现2~6步的价值，那么我们接下来再举个栗子看下:假设当前cap是17
- int n = cap - 1(n = 16)
- n |= n>>>1 (n先右移一位变成0b01000即8 ，然后做或运算得0b11000即24)
- n |= n>>>2 (n先右移两位变成0b00110即6，然后做或运算得0b11110即28)
- n |= n>>>4 (n先右移三位变成0b00001即1，然后做或运算得0b11111即31)
- n |= n>>>8 (n先右移四位变成0b00000即0，然后做或运算得0b11111即31)
- n |= n>>>16 (n先右移四位变成0b00000即0，然后做或运算得0b11111即31)
- 当前n必然小于最大容量值，那么最后的结果就是32。
所以当cap等于17时，得到的结果就是32。
为什么最后的结果必须是2的n次幂值，稍后在做解释。初始化完成，接下来就是HashMap的几大操作了put,get,remove。下面我们假设默认初始容量为16
put操作
首先看下HashMap的核心方法:
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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) //step1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //step2
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)))) //step3
e = p;
else if (p instanceof TreeNode) //step4
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//step5
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 //step6
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //step7
resize();
//step8
afterNodeInsertion(evict);
return null;
}
put操作主要调用内部方法putVal方法，传入了key的hash值，以及key和Value。
在讲put的主要逻辑之前，在这里先解释下为什么初始容量必须是2的n次幂值，我们看下step2
if ((p = tab[i = (n - 1) & hash]) == null) //step2
tab[i] = newNode(hash, key, value, null);
这里会先判断(n-1)&hash值在数组里面是否存在，我们假设当前初始容量是16，那么n-1就是15换成二进制就是1111，这样与后面的hash做与运算就是等于hash值，所以只要hash值不一样，那么就不会出现hash冲突的情况。那如果初始容量不是2的n次幂值呢，假设为15，那么n-1就是14换成二进制就是1110，这样后面的hash值只要前三位一样，后面一位不管是0还是1，的出来的值就是一样的，这样会增大hash冲突的概率。所以设置成2的n次幂的值主要就是为了减少hash冲突。
接下来进入正题，我们看下代码的主要逻辑。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; //step1
第一次put的时候table必然是空，那么执行step1，做一次resize操作，具体操作后面再讲，resize的主要作用就是扩容或者初始化数组，这里会分配一个初始容量的数组。
初始数组.jpg
然后进入step2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //step2
n为初始数组大小16，这个时候n-1与上hash得出来的结果为10(假设插入的hash值是10，key为"青菜",value为"14元"，那么0b01111 & 0b01010 = 0b01010)，tab[10]必然是空，所以会new一个新的Node放入到tab[10]中。然后当size大于阈值的时候会进行一次扩容操作即resize(注意这里的阈值并不是一开始设置的初始容量，阈值会在初次调用resize操作的时候乘上加载因子，得出最终的阈值。这个加载因子的作用我们稍后再讲，这里记住是这样的机制就行)。
插入青菜.jpg
- 接下来put一个新的值(假设hash值仍为10，key仍为"青菜",value为"15元")
此时我们会跳过step1和step2，进入else分支step3
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
此时p获取出来是有值的，并且key是等于传入的key，hash值也相同,那么将p赋值给e，然后进入step7
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
此时将新的value值替换掉旧的value值。
插入青菜.jpg
- put一个新的值(假设hash为10，key为"白菜"，value为“10元”)
此时我们会跳过step1,step2和step3,又因为我们当前的链表并没有达到一定的长度,所以p不为TreeNode，直接进入step5
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;
}
此时根据hash值可以获取到对应的p值，但是p的key跟传入的key不一致，所以开始在链表里面寻找与当前key一致的node。
如果到最后发现仍然不存在，那么就新建一个node，插入到当前链表的最后一个位置。这里有个treeifyBin方法，其实就是将链表转化成红黑树的操作。TREEIFY_THRESHOLD为8，也就是说链表长度大于8的时候会将链表转化成红黑树，这个时候node会转变成TreeNode(只有JDK8之后的HashMap才会有这个操作。红黑树的原理在我这篇文章中讲过，这里不再赘述)。
这里重点提一下HashMap中TREEIFY_THRESHOLD为8，而UNTREEIFY_THRESHOLD为6，也就是说链表长度大于8的时候才会转化成红黑树，而元素个数小于6的时候才会变回链表。
为什么两个值要不一致呢？其实链表与红黑树的转化是比较耗费性能的。如果存在着某个场景HashMap的某个下标上面的节点数在8之间来回跳，那么就有可能导致链表和红黑树之间反复转化，导致HashMap效率低下。为了避免这种情况，才会设计出两个不一样的值
如果发现存在对应的节点，那么就替换掉原来的节点
插入白菜.jpg
-
put一个新的值(假设hash为8，key为"萝卜"，value为“8元”)
此时step2获取到的p值为null，所以会new一个新的Node出来
插入萝卜.jpg
- 接下来我们依次插入10个hash值不同的值，这样整个数组长度就等于12
此时在step7的时候满足条件会做一次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) {//step1
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 //step2
newCap = oldThr;
else { // zero initial threshold signifies using defaults //step3
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { //step4
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) { //step5
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。这里我们还是分步来解释:
还记得第一次put操作么，它会先进入resize方法，
- 这个时候table是空的(因为第一次put的时候table并没有赋值)，所以oldCap为0，因为将当前阈值赋值给了oldThr，所以此时oldThr是有值的，就是一开始的初始容量 16，所以会进入step2
- 将oldThr赋值给newCap，此时newThr没有赋值，所以会进入step4
- newCap乘以loadFactor也就是16✖️0.75 = 12，将12赋值给了阈值(所以使用的时候阈值肯定是最大容量*加载因子)。
- 因为oldTab是空的，所以step5就直接跳过了。
以上就是第一次的put操作，那么我们再来看下刚才数组size到达阈值以后的扩容操作
- 因为这个时候是要扩容了，所以table必然不为空，所以oldCap必然是大于0的(为16),所以进入step1
- oldCap并没有超过最大阈值，然后
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
满足这个条件，所以此时oldThr左移一位，赋值给newThr相当于是✖️2。此时newThr不为0，所以跳过了step4
- 进行扩容操作，即新建一个原来两倍大小的数组，然后进入step5
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
- step5代码有点长，直接用通俗一点的话来说就是将原数组上面的node给赋值到新的已经扩容好的数组上面去，那么看下具体的实现逻辑吧：
//这个判断主要是为了过滤首次进行resize操作的情况，初始化的时候不需要进行扩容操作，所以也就不存在将旧数组的值移到新数组上面去
if (oldTab != null) {
//这里做循环主要就是将数组的值复制到新数组上面
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//原数组当前下标必须是有值才会进入此if条件中，否则没有复制的必要
oldTab[j] = null;
//当e.next是空的时候证明当前链表只有一个节点，那么直接通过hash & (newCap - 1)来计算出新的下标，将e放入数组对应下标中
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
//进入这个else循环，证明当前链表节点不止一个
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//所以这里做的do-while循环目的就是将当前下标的链表里面的所有节点生成两条不同的链表。
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;
}
}
}
}
}
前面部分可以直接看代码注释，这里着重解释下do-while以及之后的操作，为什么要将一个下标下面的链表分成两个不同的链表呢。
首先数组下标是通过hash&(cap-1)生成的，一旦扩容以后，cap的值就会变成原来的两倍。这样hash&(cap-1)的下标要么就跟老的数组的下标一致，要么就是拿老的数组下标再加上老的数组的长度来作为新数组的下标。
为何呢？我们举个栗子：假设旧的cap是16即0b10000,则oldcap-1为0b01111:那么扩容以后就是32即0b100000，则newcap-1为0b011111。我们拿hash&(cap-1)其实就是(hash&01111)和(hash&011111)。我们可以看到后四位运算得出来的结果肯定是一样的，唯一的不同就是第5位，假设hash值是10101，那么旧下标就是0101(5)，新下标就是10101(21)，结果就是5+16 = 21也就是刚才说的【老的数组下标再加上老的数组的长度】。假设hash值是00101，那么旧下标就是0101，新下标也是0101，所以新下标跟旧下标保持一致。
这个其实也是为什么初始容量会是2的n次幂值的原因之一，便于扩容的时候计算。
上面这段解释看明白了以后，这里面的操作其实就不难理解了。这里会将链表分拆成lo和hi。
loHead：下标不变的链表头
loTail：下标不变的链表尾
hiHead：(下标+原数组长度)的链表头
hiTail：(下标+原数组长度)的链表尾
而(e.hash & oldCap) == 0就是为了判断高位一位。如果是0，那么代表下标不变，加入到lo中；如果是1，那么代表下标变成了[下标+原数组长度]，那么就加入到hi中。里面的操作、就是链表插入的基本操作这里就不加以展开了。
下面给出对应的流程图：
put操作.jpg
get操作
相对于put操作来说，get操作的逻辑就简单了很多，我们直接看代码
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 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) { //step1
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k)))) //step2
return first;
if ((e = first.next) != null) { //step3
if (first instanceof TreeNode) //step4
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do { //step5
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- step1判断当前table是否初始化过，长度是否大于0，并且(n-1)&hash获取的第一个Node元素不为0，才会进入step2
- step2 判断获取的第一个Node元素与传入的key对应的hash值是否相等，key值相等(这里有个或运算:前者判断基本数据类型所对应的key是否相等;后者判断对象类型是否为同一个)，一旦满足就直接返回对应的node
- step3判断第一个节点是否有next节点，如果存在进入step4，否则直接返回null
- step4判断如果是红黑树的话，通过红黑树的方式找到对应的node，如果不是则进入step5
- step5做一个do-while循环，判断逻辑与step2一致，目的是为了找出当前链表中key相同的那个node返回出去，否则返回null。
以上就是get的所有逻辑。相对比较简单，没有什么需要特殊说明的。
remove操作
remove会比get稍微复杂点
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 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) { //step1
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //step2
node = p;
else if ((e = p.next) != null) { //step3
if (p instanceof TreeNode) //step4
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do { //step5
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)))) { //step6
if (node instanceof TreeNode) //step7
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) //step8
tab[index] = node.next;
else //step9
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
- 其实remove的step1,step2,step3,step4,step5跟get方法里面的五步操作一样，目的都是为了找到指定的元素，不同的是get是获取到以后直接return掉，而remove是找到以后需要删除以及接下来一系列的操作
- step6如果能获取到node，那么肯定就进入条件了(因为我们外界调用的remove方法传入的matchValue默认是false)。
- step7判断是否为红黑树，如果是的话在红黑树中找出对应node，删除以后如果不满足红黑树了需要做旋转和变色来自平衡。如果不是则进入step8
- step8 如果node==p条件成立，那么就是step2获取的值，而step2获取的就是对应下标下的头节点。所以直接将头结点的next作为当前下标的头结点
- step9 这里p节点其实就是node之前的一个节点，(我们可以看下step5的逻辑：如果当前节点e满足传入的key值和hash值的话，那就把e赋值给node，而e就是p.next得到的)。所以只要把node的next节点与node节点切断，与p.next连接即可。然后size自减。
在put和remove方法里面调用了下面三个空方法:
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
这三个方法主要是LinkedHashMap实现的，这里就不展开细讲了，后续有机会分析LinkedHashMap的时候再讲。
