常见面试题：HashMap的底层原理？
在 JDK7 和 JDK8 中，HashMap 的底层是有所不同的
- 在 JDK7 中，HashMap 是通过数组+链表实现的
- 在 JDK8 中，HashMap 是通过数组+链表+红黑树实现的
我们通过源码来探讨 JDK8 中 HashMap 的底层，主要是分析它的一些属性，以及它的构造方法、put 方法和 get 方法
属性
首先看一下 HashMap 里都有哪些属性，得有个大致了解：
//HashMap底层的那个数组
transient Node<K,V>[] table;
//似乎和缓存有关
transient Set<Map.Entry<K,V>> entrySet;
//记录当前HashMap中有多少个Node
transient int size;
//记录当前HashMap被修改了多少次，在出现线程不安全的问题时可以通过这个属性来迅速报错
transient int modCount;
//当size达到这个阈值后将对HashMap进行扩容，*****不过在table正式初始化前，用来记录table的初始容量*****
int threshold;
//负载因子，在table正式初始化后，threshold就是通过capacity*loadFactor计算得到的
final float loadFactor;
//默认的table初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//table的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子
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;
构造方法
然后来看看 HashMap 的构造方法，虽然这里调用的是无参的，但我们直接看最复杂的那个：
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);
}
-
这两个参数，一个是初始的数组容量（无参时默认为16），另一个和扩容有关，叫做负载因子（无参时默认为0.75）
-
这个构造函数其实也没做什么事情，就是对输入的参数进行检查，然后对 HashMap 的两个属性做初始化
-
可以发现，在构造方法中其实并没有对
table进行初始化，此时table的初始容量旧记录在threshold中 -
需要注意的是，这里
loadFactor是直接赋值的，但threshold的赋值是经过处理的，看看tableSizeFor这个方法：/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }- 直接看就懵逼了，因此我们可以带入几个值看看，比如说，如果我传入的 capacity 是 10 的话，这个方法就会返回 16，如果传入的 17 的话，这个方法就会返回 32，这也符合官方对这个方法的描述
- 由此可见，HashMap 的数组容量并不是任意的，一定得是 2 的幂，就算我们强行指定数组容量为 10，也会经过这个方法的处理而变成 16
- 此外，构造方法并没有限制
initialCapacity不能为 0，如果是 0 的话经过这个方法返回的还是 0，这其实算是个特殊情况吧，如果initialCapacity为 0，那么在后续对 table 初始化时就会使用DEFAULT_INITIAL_CAPACITY作为其初始容量
put
接下来看一下 put 方法，是最重要的一个方法
首先需要明确，虽然我们是 put 了一个键值对，但其实最后存到 HashMap 里的是一个 Node，这个 Node 有以下属性：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
看看 put 的源码：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
-
可以发现 put 只是个马甲，实际上是调用了 putVal，涉及五个参数，我们关注前三个，除了 key 和 value，还有根据 key 算出来的一个哈希值，看看到底是怎么算的：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } -
可以发现，这个哈希值并不直接是对象 markword 里的那个哈希值，而是经过处理的
-
如果 key 为 null，那么哈希值就是 0（说明 HashMap 是允许 null 作为 key 的）
-
否则，先得到 markword 里的哈希值，记为 h，然后进行
h ^ (h >>> 16)这个运算，运算结果才是 HashMap 真正使用的哈希值
再来看看 putVal 的源码，可以发现比较复杂，请看注释：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//定义一些变量，后面会使用到
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//先对变量进行赋值，tab就是table的另一个引用，n就是table的容量
//如果table还未初始化（或者容量为零），那么进行初始化（或者扩容），并将新的容量赋值给n
if ((tab = table) == null || (n = tab.length) == 0)
//注意这里的resize方法，初始化、扩容都是使用的这个方法
n = (tab = resize()).length;
//注意这里的i = (n - 1) & hash，这里其实是在计算这个node该放在table的哪个位置中，i就是最后算出的位置
//这里先将tab[i]处的内容交给了p
//如果发现p为null，说明这个位置还什么都没有，此时直接新建一个node放进去就好
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果p不为空，说明这个地方已经有东西了，这里可能是个链表，也可能是个红黑树
else {
//定义一些变量
Node<K,V> e;
K k;
//我们有时可能会put几个相同key的node到HashMap中，此时新的value会覆盖旧的value
//这里就是在判断p的key和当前put的node的key是否相同
//如果是，将p交给e，此时也不用管是链表还是红黑树，直接覆盖就完事了
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
//覆盖操作会在后面统一处理
e = p;
//如果key不相同，那么需要根据p是链表结点还是红黑树结点来分别处理
//如果是红黑树结点，那么调用putTreeVal方法将新的node插入到红黑树中
else if (p instanceof TreeNode)
//如果发现红黑树中存在相同key的node，会把这个node交给e，此时其实没有插入，只需要后面进行覆盖
//否则返回null，表示成功插入了新的node
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果是链表结点
else {
//这里是在遍历链表，binCount记录链表中有多少个结点
for (int binCount = 0; ; ++binCount) {
//如果发现遍历到底了，说明链表中没有相同key的node，那么直接新建一个node插在最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果插入之后发现链表中结点个数超过了阈值（默认为大于8），将链表升级为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
//注意，其实升级还需要另一个条件，隐藏在treeifyBin这个方法中，同时满足才会升级
treeifyBin(tab, hash);
//都插入好了肯定可以break了
break;
}
//如果遍历途中发现有相同key的node，那么也可以break了，后面进行覆盖即可
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//在上面的三种情况中，一旦发现有相同key的node，都会把这个node存放在e中，在这里进行覆盖
if (e != null) {
//得到旧的value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//用新的value覆盖旧的
e.value = value;
afterNodeAccess(e);
}
}
//如果确实是插入了node，那么modCount加一
++modCount;
//size肯定也加一，如果加一后发现超过了阈值，那么需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
//如果确实是插入了node还不是覆盖，put方法返回null
return null;
}
可能会有些迷糊，这里再捋一下：
-
我们是在已经有了 hash key value 三样东西之后进入 putVal 方法的
-
首先，检查 table 是否初始化了，如果初始化了，再检查其容量是否为零，无论其中哪一种情况发生，显然这个 HashMap 都是没法使用的，因此需要对 table 进行初始化或者扩容，这两个操作统一通过
resize方法来完成，由于这个方法也比较复杂，因此放到最后再具体介绍 -
现在，一个可用的 table 肯定已经有了，接下来就是根据 hash 来计算该把新的 node 放在 table 的哪个位置，把目标索引记为 i，那么 i 的计算公式为
i = (n - 1) & hash，新的 node 就是放在table[i]这个地方 -
但
table[i]这个地方可能是原本就有 node 的，不能直接就进行table[i]=newNode这种莽夫操作，因此，先把table[i]处的node 赋值给一个变量 p，接下来分四种情况进行讨论：-
如果 p 为 null，说明这个地方没有 node，那是最爽的，直接
table[i]=newNode就完事了，新的 node 就插入成功了 -
如果 p 不为 null，但 p 的 key 和当前要插入的 node 的 key 相同，说明此时要完成的不是插入，而是覆盖，于是用新的 value 覆盖旧的 value 就完事了
-
如果 p 不为 null，p 的 key 和当前要插入的 node 的 key 也不同，此时就没那么方便了，因为我们不得不深入到链表或者红黑树中来进行插入的工作了
-
如果发现 p 是一个红黑树结点，那么就得在这个红黑树中进行插入操作，有关操作都被封装在了
putTreeVal这个方法中，我们也不必对这个方法过于纠结，因为比较复杂，而且和 HashMap 的关系并不大，我们只需要知道，如果发现树中存在相同 key 的 node，那么实际进行的也是覆盖操作，而不是插入 -
如果发现 p 是一个链表结点，那么就得在这个链表中进行插入操作，这相比红黑树是比较简单的，就是遍历这个链表，如果途中发现某个相同 key 的 node，那么进行覆盖操作，但如果遍历到底了也没有发现相同 key 的 node，那就说明没有，于是把新的 node 插入到链表的尾部即可，在插入完毕后，如果发现这个链表中结点的个数超过了阈值（默认为 8），就会调用
treeifyBin这个方法，我们稍微看一下这个方法，可以发现，虽然方法的名字是树化，但在方法中还会对 table 的容量做判断，如果 table 的容量小于MIN_TREEIFY_CAPACITY，那么进行的其实是数组扩容，而不是链表树化：final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //注意这里，如果table的容量小于MIN_TREEIFY_CAPACITY这个阈值（默认为64），其实也不会把链表升级为红黑树 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); } }
-
-
-
至此，如果上面完成的是覆盖操作，那么其实
putVal方法已经完事了，但如果完成的是插入操作，最后还需要判断 HashMap 中 node 的个数是否超过了阈值，如果超过了，需要进行一次扩容
现在，我们就剩下 resize 这个方法没有看了，在看它之前，先梳理一下哪些情况下会调用它：
- case1：尝试插入 node 时发现 table 未初始化，或者 table 的容量为 0（我不是很清楚怎么会有容量为 0 的情况发生，因此后面分析时为了简洁起见就不管这种神奇的情况了）
- case2：成功插入新 node 后，发现链表中结点个数大于 8，试图进行链表树化，但发现 table 的容量小于 64
- case3：成功插入新 node 后，发现哈希表中 node 的个数超过了
threshold
接下来就正式看一下 resize 这个方法：
final Node<K,V>[] resize() {
//记录旧的table（可能是未初始化的，因为初始化和扩容都是使用的这个方法）
Node<K,V>[] oldTab = table;
//记录旧table的容量（如果未初始化就是0）
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//记录旧table的阈值（如果未初始化，记录的是要把table初始化为多大的容量）
int oldThr = threshold;
//新table的容量和阈值，后面一通操作就是给这两个变量确定值
int newCap, newThr = 0;
//如果旧table是已经初始化的
if (oldCap > 0) {
//如果旧table的容量已经超过最大限制了，那么已经不能再扩容了，只能放宽扩容的阈值，此时直接返回旧的table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果将旧容量翻倍后依旧没有超过限制，并且旧容量是大于等于16的，将翻倍后的旧容量和旧阈值交给新容量和新阈值
//****在我们的日常使用中绝大多数情况都是进的这里，也就是说大多数情况下扩容都是把容量和阈值扩大为原来的两倍****
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
//以下两种都是table未初始化的情况，注意这里的话oldThr的含义就不是旧阈值了，而是要把table初始化为多大的容量
//当我们使用无参的构造函数，或者使用有参并且传入了正常的initialCapacity，那么oldThr肯定大于0并且一定是2的幂
else if (oldThr > 0)
//把oldThr交给newCap就完事了
newCap = oldThr;
//这就是前面提到过的特殊情况，当我们使用有参的构造函数但传入了0作为initialCapacity，表明使用默认值
else {
//使用默认的初始容量
newCap = DEFAULT_INITIAL_CAPACITY;
//使用默认的初始容量和默认的负载因子算出阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//新容量前面已经全部算好了（如果没反应过来可以再体会一下），但如果新阈值还没算出来，统一在这里计算
if (newThr == 0) {
//先根据新容量和负载因子算出一个阈值ft
float ft = (float)newCap * loadFactor;
//如果新容量和ft都没有超出限制，就使用ft作为新阈值，否则，使用INT_MAX作为新阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将求出的新阈值交给threshold，此时阈值就真的更新好了，再下面就是根据新容量进行真正的扩容了
threshold = newThr;
//根据新容量开辟新的table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果旧table是未初始化的，里面肯定没东西，那么resize就结束了，否则需要把旧table里的东西挪到新table里
if (oldTab != null) {
//遍历旧table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果oldTab[j]处为空，那么这个位置就不用管了，但如果oldTab[j]处不为空，先把这里的node交给e
if ((e = oldTab[j]) != null) {
//oldTab[j]处肯定直接置空，不需要了
oldTab[j] = null;
//如果只有一个node，那方便，直接把这唯一的一个node放到newTab里
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//但如果有多个node，就麻烦了
//如果这是棵红黑树，那么所有的转移操作都封装在split里了，这里就不深入了
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果这是个链表
else {
//构建两个新链表lo和hi，分别有两个变量指向首尾
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历链表中的每个node
do {
next = e.next;
//如果哈希值与旧容量相与结果为0，把node放到lo里
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//否则，把node放到hi里
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//收尾工作，把lo和hi放到newTab里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
虽然代码看起来有点复杂，但其实思路是比较直观的，无论是为了初始化还是扩容，第一步都是算出接下来新 table 的容量和阈值，如果是为了初始化，那么开辟好新的 table 就完事了，但如果是为了扩容，还得把旧 table 里的内容转移到新 table 里
现在，我们对整个 put 的流程已经有所了解了，但里面有一些地方其实是比较让人疑惑的：
-
在计算哈希值时，为何不直接使用 markword 里的哈希值，而是要经过一些额外的运算？
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 首先我们得知道，哈希值很重要，涉及这个 node 最后会存放在 table 的哪个位置中
- 如果直接使用 markword 里的哈希值，要知道我们是可以覆写一个对象的
hashCode方法的，如果我们写的很烂，然后还在这里直接用，可能会导致最后很多的 node 都放在 table 的同一个位置中，这对 HashMap 的性能影响是很大的 - 因此，在这个方法里会对 markword 里的哈希值做一些额外的运算（移位和异或），目的就是为了让哈希值变得更随机，使得最后各个 node 可以尽量均匀的分布在 table 中，提高 HashMap 的性能
-
在计算要把 node 放在 table 的哪个位置中时，
i = (n - 1) & hash是什么原理，为什么不直接对 n 取余？-
首先我们得知道，table 的容量是固定的，比如 16，那么不管我们的哈希值有多复杂，经过计算都得落在 0~15 这个范围中
-
直接用哈希值对 16 取余肯定是可行的，但取余看着简单，其实是比较耗时的，相比之下位运算的速度快很多
-
那么，
i = (n - 1) & hash是怎么保证计算结果落在 0~15 这个范围中的呢？-
首先，16 是 table 目前的容量，其二进制为 10000，减一后为 15，二进制为 1111
-
我们的哈希值是一个 32 位的整数，不管它有多大，高位有多少个 1，跟 1111 进行与操作后，相当于取了哈希值的最后四位，因此结果一定是在 0000~1111 之间的，也就是 0~15，随便看个例子：
哈希值 1011 1100 0010 0011 1111 1100 1001 1100 15 0000 0000 0000 0000 0000 0000 0000 1111 & 0000 0000 0000 0000 0000 0000 0000 1100
-
-
既然通过位运算也能达到目标，并且速度还比取余快，那自然就是采用这种方案了
-
-
为什么 table 的容量一定得是 2 的幂？
-
直接举个反例吧，如果 table 的容量为 17，那么哈希值经过计算一定得落在 0~16 这个范围中：
哈希值 1011 1100 0010 0011 1111 1100 1001 1100 16 0000 0000 0000 0000 0000 0000 0001 0000 & 0000 0000 0000 0000 0000 0000 0001 0000 -
可以发现，在这种情况下，虽然运算结果也不会超出 0~16 的范围，但其实只会出现 10000 和 00000 两种结果，也就是说，无论我们的哈希值是多少，最后这个 node 只会被放到 table[0] 或者 table[16] 的位置，这样一来，剩下的位置统统都浪费了，所有 node 都扎堆在两个位置里，会导致 HashMap 的性能受到极大的影响
-
因此，我们要求 table 的容量一定得是 2 的幂，因为 2 的幂减一之后，其二进制肯定是 1111 这种形式，与哈希值进行与操作后，首先肯定不会越界，其次保证了 table 中的每个位置都会被用上
-
-
在扩容的转移过程中，链表中的 node 是如何转移的？lo 和 hi 这两个链表是什么意思？
-
首先，我们想一下最暴力的转移方式是什么？其实很简单，就是遍历 oldTab[i] 处的每个 node，然后根据这个 node 的哈希值和 table 的新容量来计算出这个 node 在 newTab 中的位置，即
hashCode & (newCapacity - 1)，然后放进去即可 -
但实际上，一个 node 在 newTab 中的位置只有两种可能，假如原始容量为 16，新容量为 32，那么 oldTab[i] 处的 node 只可能被转移到 newTab[i] 和 newTab[i+16] 两个位置
-
我们举个例子，假如原始容量为 16，新容量为 32，有 node1 和 node2 两个 node：
node1 1011 1100 0010 0011 1111 1100 1001 1100 oldCap-1 0000 0000 0000 0000 0000 0000 0000 1111 oldPos 0000 0000 0000 0000 0000 0000 0000 1100 -> 12 node1 1011 1100 0010 0011 1111 1100 1001 1100 newCap-1 0000 0000 0000 0000 0000 0000 0001 1111 newPos 0000 0000 0000 0000 0000 0000 0001 1100 -> 12+16=28 node2 1011 1100 0010 0011 1111 1100 1000 1100 oldCap-1 0000 0000 0000 0000 0000 0000 0000 1111 oldPos 0000 0000 0000 0000 0000 0000 0000 1100 -> 12 node2 1011 1100 0010 0011 1111 1100 1000 1100 newCap-1 0000 0000 0000 0000 0000 0000 0001 1111 newPos 0000 0000 0000 0000 0000 0000 0000 1100 -> 12 -
可以发现，由于容量总是 2 的幂，并且每次扩容都是翻倍，因此
newCap-1和oldCap-1其实只有一位 1 的差别（比如这里只有第五位有区别），而 node 的哈希值是不会改变的，因此，在和newCap-1进行与操作后，结果的后四位不可能发生改变，node 的新位置只取决于哈希值的第五位是 0 还是 1- 如果是 0（比如 node2），那么结果的第五位肯定还是 0，因此 node2 还是放在 i 的位置
- 但如果是 1（比如 node1），那么结果的第五位就变成 1 了，因此会放在 i+16 的位置
-
因此，oldTab[i] 处的 node 只可能被转移到 newTab[i] 和 newTab[i+16] 两个位置，于是就产生了 lo 和 hi 这两个链表，在转移一个 node 时，先通过
hashCode & oldCap来判断哈希值的第五位是 0 还是 1，如果是 0，就加入到 lo 中，如果是 1，就加入到 hi 中，所有 node 全部转移完成后，再统一把 lo 放到 newTab[i] 的位置，把 hi 放到 newTab[i+16] 的位置，此时整个转移的过程就结束了
-
get
在把 put 方法看明白后，get 就简单多了：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
可以发现 get 的主体是在 getNode 这个方法中，如果可以根据给定的 key，在 HashMap 中找到相同 key 的 node，那么返回这个 node 的 value，否则返回 null
再来看看 getNode 这个方法：
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) {
//如果这个位置上的node就是目标，直接返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不止一个node，根据是红黑树还是链表分别讨论
if ((e = first.next) != null) {
//如果是红黑树
if (first instanceof TreeNode)
//封装好了，咱就不管了
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是链表
do {
//就是遍历链表，逐个检查是否有相同key的node，有的话就返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))
return e;
} while ((e = e.next) != null);
}
}
//如果没有找到相同key的node，只能返回null了
return null;
}
这个方法需要两个参数，一个就是我们输入的 key，还有一个是根据 key 计算出的哈希值
首先进行一系列判断，主要做了三件事情：
- 保证 table 已经初始化了
- 保证 table 的容量不为 0
- 根据
(n - 1) & hash算出目标 node 会在 table 的哪个位置中（哈希值的作用），保证这个位置有 node 存在
如果上述三个条件有一个不满足，那么这个 HashMap 里肯定没有目标 node 了，直接返回 null 就完事了
否则，查找过程如下：
- 先看 table[i] 处的 node 是否就是目标 node，如果是，那最爽，直接返回这个 node 即可
- 如果不是目标 node，看看这个 node 有没有 next，也就是这个位置有没有多个 node，如果这个位置就一个 node，那么也挺爽，直接返回 null 即可
- 如果这个位置有多个 node，就麻烦了，需要判断这里是链表还是红黑树
- 如果是红黑树，具体查找细节封装在
getTreeNode里了，咱就不管了 - 如果是链表，逻辑很简单，就是遍历一次链表，看有没有目标 node，有的话就返回，没有就返回 null
- 如果是红黑树，具体查找细节封装在