HashMap简介
HashMap是Java语言中的一种集合类，它实现了Map接口，用于存储Key-Value对。它基于哈希表数据结构，通过计算Key的哈希值来快速定位Value的位置，从而实现高效的插入、删除和查找操作。下面我们对照着JAVA1.8中的HashMap源码来分析一下它的内部实现逻辑
基本的结构
在开始分析HashMap的实现逻辑之前，我们需要先了解一下基础的组成和内部的成员变量都有哪些，分别代表什么意思。
1、Node<K,V>
首先我们看一下HashMap其中一个子类:Node<K,V>，这个子类用于存储基本的元素，即Key-Value对、Key的Hash值以及指向下一个节点的Node<K,V>变量。在HashMap内部，由Node<K,V>类型组成的数组用来存储所有的元素。 Node<K,V>实现自Map.Entry<K,V>接口，并且实现了接口中规定的多个基本方法:
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
...
}
同时，在Node<K,V>类中，定义了4个成员变量：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable {
....
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
...
}
其中hash是key的hash值，key和value存储键和值，next变量指向链表中的下一个元素。
2、HashMap的成员变量
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
table：保存所有元素的数组。
entrySet：一个用于遍历所有数据节点的集合。
size：记录HashMap中元素的总数量。
modCount：用来判断在对HashMap数据项进行遍历时，其中的数据项是否有修改过，如删除或者新增一项。
threshold：控制扩容时机，当数据项数量大于threshold时进行扩容，新的容量大小是老的两倍。
loadFactor：默认值0.75，加载因子决定threshold大小，计算公式是threshold=table.length*loadFactor。
我们先大致了解一下HashMap成员变量及基础的Key-Value承载的结构，之后随着介绍的进度我们再介绍新的类型。下面我们开始正式分析HashMap的逻辑。
初始化方法
HashMap有4个初始化方法，分别是：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// MAXIMUM_CAPACITY = 1 << 30
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
第一个初始化方法有两个参数:initialCapacity和loadFactor，看参数名initialCapacity好像是控制初始化时HashMap容量大小的，实际上它不直接控制大小，而是通过tableSizeFor方法计算出threshold的值，此时threshold为大于等于传入的initialCapacity的2的次幂最小值。比如传入3，那么threshold=\(2^2\)=4，如果传入9，则threshold=\(2^4\)=16。loadFactor初始化HashMap的成员变量loadFactor。
/**
* 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;
}
而实际控制容量大小的逻辑在添加第一个元素时确定，现在先放一边不管，等到介绍添加逻辑时再分析。
第二个构造函数很简单，直接调用了第一个构造函数，传入initialCapacity和默认的加载因子DEFAULT_LOAD_FACTOR，默认加载因子是0.75。
第三个是无参的构造函数，没有设置threshold，只设置了默认的加载因子0.75。
第四个构造函数则是使用一个现有的Map对象进行初始化操作，首先设置好默认的加载因子，然后利用putMapEntries方法初始化数据项。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
//若传入的Map为空，则不进行初始化操作
if (s > 0) {
//初始化时，HashMap中还没有任何元素，所以table为null，此时根据传入的map大小计算出threshold。
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//非初始化（例如调用putAll方法）时，如果传入的map大小大于threshold，则进行resize扩容操作。
else if (s > threshold)
resize();
//遍历传入的map,依次调用putVal方法将所有数据加到当前HashMap对象中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
这个方法中所调用的resize和putVal方法在其他地方也有调用，我们在put方法的实现中再详细分析，此处只需要知道这个构造函数是通过其他Map对象构造HashMap对象的。
现在已经了解了它的基本结构和所有的构造函数，我们用一张图先直观的看一下HashMap是什么样的。
在这个HashMap对象中，变量table长度等于8，size等于3，threshold等于6。当元素个数大于6时，table将被扩容到16个，threshold也会变为12。
操作
1、put操作
put操作的实现逻辑是调用一个内部不可重写的方法putVal实现，这个方法有5个入参，分别是Key的Hash值、Key、Value、onlyIfAbsent、evict。onlyIfAbsent表示是否覆盖相同Key的Value值，为true时，只有原来的Value值为null时才会覆盖，否则不覆盖。为false时直接覆盖原值。下来我们直接看源码并逐行分析。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/**
* 将对象成员变量table赋值给局部变量tab并判断是否为null，如果为null，或者不为null则将长度赋给局部变量n，并判断长度是否0。
* 条件成立的话调用resize()方法对table进行初始化，并将初始化后的table长度重新赋值给n。
* 注意：除了调用第四个构造方法使用其他Map对象进行初始化，其余三个构造方法构造HashMap对象时，
* table默认是null,所以在第一次往HashMap里添加数据时就需要初始化table对象。
* resize()方法是HashMap内部的一个通用方法，初始化table、扩容缩容都要用到它，后续还会出现很多次，所以一定要眼熟他。
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 长度与key的hash值做按位与运算，得到的结果一定小于长度值。然后将得到的值赋给i，
* 并从tab中对应槽位取值并赋值给p。如果取到的是null，则表明当前位置没有存其他元素，
* 可以直接将新元素添加到tab中。若非null，表示key重复或者Key的hash值计算槽位冲突，则进行其他操作。
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接创建新节点并赋值给tab[i]
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/**
* 若新元素的hash值和刚才取到的p的hash值相同，并且p的key和新元素的key相同，
* 那就表示当前要保存的新key值是已存在的，不必新增，所以将p赋值给e以备后面操作。
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/**
* 否则就是Key的槽位冲突，HashMap中如果发生Hash值计算后的槽位冲突，有两种结构进行存储，第一个是链表，第二个是红黑树。
* 下面的代码会判断p节点是否为TreeNode类型，如果是则将p转为TreeNode，并调用它的putTreeVal方法，将新元素保存到树中。
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
/**
* 如果不是TreeNode类型就是上面刚开始介绍的普通Node，它里面的next变量可以指向一个Node对象，从而形成链表。
* 循环遍历p的next是否为null并且复制给e，如果为null，表示已经循环到了链表尾部，接下来创建一个Node节点并赋给p.next，
* 即链表尾部增加元素。如果不为null表示还没循环到链表尾部，判断是否存在重复元素，和上面判断逻辑相同。如果相同，
* 则在接下来处理e，如果不相同则进入下一轮循环判断，直到链表尾部。
* 要注意一点是每新增一个元素到链表尾部时，要判断一下当前链表长度是否大于等于TREEIFY_THRESHOLD，是的话会尝试将当前链表转换为红黑树。
* TREEIFY_THRESHOLD是用来判断链表是否需要转换红黑树的阈值，它的值为8，即链表长度大于等于8时尝试转换为红黑树。
*/
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;
}
}
/**
* 经过上面的计算后，局部变量e如果不为null，则表示当前需要添加的key值以存在，此时就判断onlyIfAbsent值，
* 若为false，或者已存在的key值对应的value值是null，则直接覆盖旧值。
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
/**
* 每进行一次操作（添加，删除等），modCount就加1。每新增一个元素size就加1，
* 然后判断当前tab中元素数量是否大于threshold，大于则调用resize函数进行扩容。
*/
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上面put方法总体逻辑概括下来是，Key的hash值是否与数组中已有元素槽位冲突，若未冲突则直接在对应槽位添加元素。否则需要判断Key是否一致，不一致，则将新元素加到链表尾部或者红黑树中，若链表长度超过阈值还需要将链表转换为红黑树。若一致，则需要判断是否覆盖旧值。最后再判断是否要扩容。
reseize()方法在HashMap内部承担着非常重要的任务，包括初始化table，控制table的大小，控制扩容阈值threshold和扩容操作等。接下来我们看看resize()的实现逻辑。
final Node<K,V>[] resize() {
/**
* 首先将当前table，capacity，threshold全部暂存到old开头的变量中。
* 定义新的capacity，threshold变量。定义newCap,newThr变量表示扩容后的table容量和扩容阈值。
*/
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/**
* 1、当前容量如果大于0，新的容量将翻倍，并且当前容量如果大于默认的初始化容量（16），那么扩容阈值也翻倍，否则扩容阈值使用加载因子进行计算。
* 2、当前容量如果等于0，并且当前扩容阈值大于0，那么当前扩容阈值就作为新的容量大小，用于初始化table，并且重新计算扩容阈值。（无参构造函数初始化HashMap,并且第一次添加元素时的情况）
* 3、当前容量和扩容阈值都为0时，使用默认的初始化容量（16）并计算扩容阈值（12）
*/
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;
//扩容完毕后，如果旧的table数组不为null，就将旧的数组元素迁移到扩容后新的table数组中。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//不为null说明旧数组中的这个槽位有元素，将数据赋值给变量e,并开始迁移。
if ((e = oldTab[j]) != null) {
//旧数组里这个槽位置为null，等待内存回收
oldTab[j] = null;
//next等于null说明当前槽位不存在hash冲突的元素，重新计算槽位后放到新数组中。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//否则说明存在冲突，并判断当前槽位中的元素是否是TreeNode类型，如果是的话说明已经转为红黑树了，所以迁移逻辑由红黑树逻辑实现。
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
/**
* 不是TreeNode类型，那必然是Node类型了，也就是链表，此时就迁移链表。但也不是单纯的把链表原样迁移过去，而是会进行计算，
* 因为存在这种情况，如果table的长度不长，但是有大量的key发生hash冲突，那么就会出现某个槽位的链表很长有很多数据，
* 但其他槽位基本上没数据的情况，这时就需要将这个长链表拆分成两个长度相对较短的链表，存储在新table的不同槽位上，增加查找效率。
*/
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;
/**
* 利用元素的hash值和旧链表长度做按位与运算，将长链表拆分成两个链表，一个链表放在和旧table相同位置的新table槽位中，
* 另一个链表的槽位距离第一个槽位隔了一个旧table的长度。
*/
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;
}
上面说过在添加元素的时候，如果某个槽位的链表长度超过8个就会将链表转换为红黑树，严格来说并非只看链表长度来决定是否进行转换，我们来分析一下treeifyBin方法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果当前table数组长度小于转换数规定的最小容量即64时，不转红黑树，只进行扩容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
/**
* 进行转换红黑树前的准备工作，将当前槽位的链表元素由Node类型转换为TreeNode类型，然后使用TreeNode类型的prev和next属性将所有节点连接起来，
* 构成TreeNode类型链表。最后才调用链表头节点的treeify方法进行红黑树转换。
*/
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);
}
}
通过上面的treeifyBin方法，我们知道如果数组长度如果小于64时，即使某个槽位的链表长度超过8也不会转红黑树，而是首先将数组长度扩容到超过64，同时resize方法也会在迁移数据时根据条件将链表长度超过原数组长度的链表拆分成两个链表保存到不同的槽位。同时我们也知道了不光是元素个数超过threshold才会扩容，当某个槽位的链表长度超过8并且数组长度小于64也会触发数组扩容。而红黑树的原理和具体操作本文不做详细介绍，有兴趣的可以看看网上这篇文章或者自行搜索。
现在我们已经分析了添加元素的源代码逻辑了，接下来我们结合几个例子和图来进一步加深理解。为了模拟Hash冲突的情况，我们先定义一个类Student，并且重写它的hashCode和equals方法，hashCode方法只计算name，equals方法计算name和age，确保Student类作为Key保存到HashMap中时发生Hash冲突，使程序按照我们预想的方向运行。
package com.xxx.demo;
import java.util.Objects;
public class Student {
private Integer age;
private String name;
public Student(Integer age, String name) {
this.age = age;
this.name = name;
}
public Integer getAge() {
return age;
}
public String getName() {
return name;
}
@Override
public boolean equals(Object o) {
if (Objects.isNull(o)) {
return false;
}
if (!(o instanceof Student)) {
return false;
}
Student target = (Student) o;
return age.equals(target.getAge()) && name.equals(target.getName());
}
@Override
public int hashCode() {
return name.hashCode();
}
}
接下来我们创建一个HashMap，并往其中添加若干元素，然后分析一下这个HashMap内部是如何运行的。
public static void main(String[] args){
Map<Student,String> map = new HashMap<>(4);
map.put(new Student(18,"张三"),"value1");
map.put(new Student(18,"李四"),"value2");
map.put(new Student(19,"王五"),"value3");
map.put(new Student(18,"张三"),"value4");
map.put(new Student(19,"张三"),"value5");
map.put(new Student(20,"张三"),"value6");
map.put(new Student(21,"张三"),"value7");
map.put(new Student(22,"张三"),"value8");
map.put(new Student(23,"张三"),"value9");
map.put(new Student(24,"张三"),"value10");
map.put(new Student(25,"张三"),"value11");
map.put(new Student(16,"张麻子"),"value12");
map.put(new Student(26, "张三"), "value13");
}
首先初始化HashMap时传入了initialCapacity=4，根据我们上面分析的初始化逻辑，此时map对象中的loadFactor=0.75（默认），threshold=4（大于等于4的2的最小次幂值），table=null，size=0，modCount=0。
然后添加第一个Key-Value对后，size=1，modCount=1，table初始化长度为4的Node<Student,String>数组，threshold变为3（4*0.75）
添加第二个Key-Value对后，size=2,modCount=2。
添加第三个Key-Value对后，size=3，modCount=3。
添加第四个Key-Value对时，因为Student对象和第一次添加的相等，所以默认会覆盖掉第一次添加的value值，此时size=3，modCount=3。
从第五个开始到第11个Key-Value对，都会发生hash冲突但Key不相同，所以接下来第五个Key-Value元素会在table[2]的位置上搭建链表，table[2]上的Node对象的next会指向新的元素。但是当value5被添加进去后，size=4，大于扩容的数量阈值3，此时进行扩容，从table[4]变为table[8]，threshold=6，并对已有的元素重新计算hash值后迁移到新table中。此时元素的分布如下：
然后陆续添加元素一直到第8个时，再次扩容，table[8]变为table[16]，threshold=12，再重计算hashcode并重排元素在数组中的位置。
当添加完value13后，table[2]上的元素已经超过TREEIFY_THRESHOLD了，此时就会调用treeifyBin方法，尝试对槽位2上的链表进行红黑树的转换，不过现在数组的长度还不够64位，不进行转换，而是扩容并迁移各个槽位上的数据。当前table长度为32，threshold为24。
value14添加到hashMap后，同样会再次扩容，table长度到64，threshold为48，并且各个元素重新计算槽位。等到value15被加入到HashMap后，槽位34(添加value14后槽位2的元素重新计算槽位到34)上才会真正转换为红黑树。
红黑树相较于链表，在查询方面的时间复杂度为O(log n)，是一种自平衡的二叉查找树。而链表的查找操作需要遍历整个链表，时间复杂度为O(n)。因此红黑树在查询方面具有明显的优势。
除了put方法外，还有一个putAll方法，此方法实际上是调用putMapEntries方法，将一个Map类型参数循环添加到HashMap中，putMapEntries方法的逻辑上面我们已经介绍过了。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
2、删除元素操作
我们首先看一下删除方法源码
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
remove方法内部调用removeNode方法，将指定Key的元素删除，并在删除成功后返回对应Key的value值。下面是removeNode的源码。
/**
* hash:Key的hashcode
* matchValue: 是否匹配value，true的话表示不光匹配Key，还需要匹配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;
//数组不为空并且对应槽位有值，则将对应槽位元素赋值给p
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;
/**
* p的hash值和要删除的hash值一样，并且Key本身相等，说明p就是要删除的值，则将p赋值给node；
* 否则说明存在hash相同，但值不相同的key，即hash冲突。此时判断p.next是否有值，
* 有值代表链表或红黑树存在，可以在链表或红黑树上进一步检索Key，如果找到了则赋值给node。
*/
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);
}
}
/**
* 若node有值，并且不匹配value值，或者value值匹配成功，即开始删除操作。
* 如果node是TreeNode类型，则调用红黑树的移除操作对元素进行移除。否则是Node类型；
* node==p说明直接在槽位上匹配到元素了，没有进行hash冲突判断，所以直接将node的next赋值给槽位，
* node对象在当前方法执行完后就失去了引用，可以被GC。
* 若node不等于p，则说明进行了hash冲突判断，也是同样的道理，把node的next复制给p.next，
* node失去引用等待被GC。最后返回匹配到的node即可。
*/
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;
}
上面的删除方法我们分析了删除的相关逻辑，当然除了红黑树的删除方法，本文不具体介绍红黑树。不过HashMap中有个逻辑还得说一下。在添加元素的方法中，我们知道链表转红黑树的条件是：数组长度大于等于64，链表长度超过8，那么就会被转换成红黑树。如果删除红黑树里的元素，达到什么条件时，红黑树才退化成链表？这块的逻辑在removeTreeNode方法和split中
final void removeTreeNode(HashMap<K,V> map,Node<K,V>[] tab, boolean movable){
......
//树根节点为null，或者不为null的情况下，跟节点的右节点是空的，或者左节点是空的，或者右节点的左节点是空的，此时执行退化操作
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
......
}
final void split(HashMap<K,V> map,Node<K,V>[] tab,int index, int bit){
......
//lc\hc为树上的元素个数，如果元素个数少于等于UNTREEIFY_THRESHOLD时，则将树退化到链表，UNTREEIFY_THRESHOLD的值为6.
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);
}
}
......
}
在我们分析完添加元素的逻辑和源码后，再看上面移除元素的逻辑就很简单了，其中匹配元素的逻辑在putVal方法中也出现过，老眼熟了。下面我们简单的图示一下移除的步骤。
图1表示数组和链表的原始状态，图2表示删除指定槽位链表头元素后的情况，即tab[index] = node.next这行代码。图3表示hash计算槽位冲突后检索链表，删除链表中某个元素的情况，即p.next = node.next这行代码。
HashMap还提供了一个clear方法，用于清除数组中所有槽位元素，逻辑也非常简单，即循环数组将所有槽位设置为null，并将size设置为0。
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
3、查找元素
在介绍查找元素方法之前，我们先看一下HashMap中集合相关的源码和逻辑。HashMap中有三个获取集合的方法：keySet(),values(),entrySet()，分别返回Key的集合，value的集合及键值对集合，三个方法的实现都依赖内部类KeySet,EntrySet,Values。其中KeySet和EntrySet继承自AbstractSet抽象类，Values继承自AbstractCollection抽象类，下面我们只分析EntrySet集合的源码和逻辑，KeySet和Values集合逻辑类似，有兴趣的可以自行查看。
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
//多数方法的核心实现逻辑都是依赖HashMap中的逻辑实现。
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
/**
* 遍历方法对所有元素进行遍历时，会判断modCount是否有变化，如果有变，说明在遍历途中，有其他线程对元素进行了增加或者删除，
* 有线程安全问题所以抛出异常。或者在遍历方法内对集合元素进行了增加或删除操作。
*/
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
通过上面的forEach方法，我们总算知道了modCount到底是干吗用的了，modCount就是为了保证，在任何时候遍历该键值对的集合时确保集合内的值不会变化，导致发生“明明我都遍历所有元素统一处理了，为什么还有好几个元素不生效”这种事情。
接下来我们正式看看查询相关代码逻辑。
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;
/**
* 根据Key的hash值，计算出所在槽位。并去除对应槽位的值赋值给first变量。
* first变量hash值和方法入参的hash值相等，并且first.key与入参key相等，表示找到节点数据，并返回。
* hash值相等，但first.key与入参key不相等，说明有hash冲突。若first是TreeNode类型说明当前槽位已经是红黑树，则使用红黑树的方法进行元素查找。否则是链表，遍历链表的next属性进行查找
* 将找到的元素返回，未找到则返回null
*/
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;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
查找元素的方法逻辑非常清晰和容易理解，getNode方法作为内部的方法被许多方法调用，是一个公共的查找元素方法。
其他方法
除了基本添加元素、删除元素、查找元素等方法，还有其他的方法提供给我们，以支持更多的功能。
/**
* 替换Value，查到对应Key的元素节点后，判断Value值是否等于给定的oldValue，相等则将newValue值替换至元素节点，不相等则不替换。
*/
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
/**
* 查找到对应Key元素节点后，直接对Value值进行替换，不进行其他逻辑判断。
*/
@Override
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
/**
* 通过给定的Key查找元素，将查到的元素Key、Value值传入入参的回调函数，并通过回调函数接受一个返回值，
* 若返回值不为null，用返回值替换旧的value值，否则删除查到的元素。
*/
public V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node<K,V> e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
removeNode(hash, key, null, false, true);
}
return null;
}
除了上面介绍的几类方法，还有逻辑相似或者作用相似的几个方法，包括合并方法，替换元素方法，遍历方法等等，就不一一介绍了，有兴趣的话各位可以自己看看。
另外在我们上面分析的众多的源码逻辑中，可以看到出现了很多次的afterNodeAccess,afterNodeInsertion,afterNodeRemoval的方法调用，这些方法在HashMap内部没有实现是个空方法，实际上的实现是在LinkedHashMap类中，而LinkedHashMap则是继承自HashMap的，所以LinkedHashMap实例在调用父类方法，也就是HashMap中的相关逻辑时，这几个方法才有实质的作用。
总结
HashMap是建立在Hash算法和数组之上，拥有对数组进行随机访问能力的Key-Value结构，同时在处理Hash冲突时使用了不同的策略即链表和红黑树，得益于此，HashMap拥有比较高的性能，各类开源中间件中也有大量的应用，日常编程中也会非常频繁的使用到HashMap。但HashMap是非线程安全的，多个线程同时对它进行操作会出现线程安全问题，如果要在多线程环境中使用Key-Value结构的数据结构容器，可以使用ConcurrentHashMap。