1.5 查询数据

1.5.1 get方法-查询数据的入口

在查询数据时，会先判断当前key对应的value，是否在数组上。
其次会判断当前位置是否属于特殊情况：数据被迁移、位置被占用、红黑树结构
最后判断链表上是否有对应的数据。
找到返回指定的value，找不到返回null即可

// 基于key查询value
public V get(Object key) {
// tab：数组， e：查询指定位置的节点 n：数组长度
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 基于传入的key，计算hash值
int h = spread(key.hashCode());
// 数组不为null，数组上得有数据，拿到指定位置的数组上的数据
if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
// 数组上数据恩地hash值，是否和查询条件key的hash一样
if ((eh = e.hash) == h) {
// key的==或者equals是否一致，如果一致，数组上就是要查询的数据
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果数组上的数据的hash为负数，有特殊情况，
else if (eh < 0)
// 三种情况，数据迁移走了，节点位置被占，红黑树
return (p = e.find(h, key)) != null ? p.val : null;
// 肯定走链表操作while ((e = e.next) != null) {
// 如果hash值一致，并且key的==或者equals一致，返回当前链表位置的数据
if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
// 如果上述三个流程都没有知道指定key对应的value，那就是key不存在，返回null即可
return null;
}

1.5.2 ForwardingNode的find方法

在查询数据时，如果发现已经扩容了，去新数组上查询数据
在数组和链表上正常找key对应的value
可能依然存在特殊情况：
● 再次是fwd，说明当前线程可能没有获取到CPU时间片，导致CHM再次触发扩容，重新走当前方法
● 可能是被占用或者是红黑树，再次走另外两种find方法的逻辑

// 在查询数据时，发现当前桶位置已经放置了fwd，代表已经被迁移到了新数组
Node<K,V> find(int h, Object k) {
// key：get(key) h：key的hash tab：新数组
outer: for (Node<K,V>[] tab = nextTable;;) {
// n：新数组长度， e：新数组上定位的位置上的数组
Node<K,V> e; int n;if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null)
return null;
// 开始在新数组中走逻辑
for (;;) {
// eh：新数组位置的数据的hash
int eh; K ek;
// 判断hash是否一致，如果一致，再判断==或者equals。
if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
// 在新数组找到了数据
return e;
// 发现到了新数组，hash值又小于0
if (eh < 0) {
// 套娃，发现刚刚在扩容，到了新数组，发现又扩容
if (e instanceof ForwardingNode) {
// 再次重新走最外层循环，拿到最新的nextTable
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
// 占了，红黑树
return e.find(h, k);
}
// 说明不在数组上，往下走链表
if ((e = e.next) == null)
// 进来说明链表没找到，返回null
return null;
}}
}

1.5.3 ReservationNode的find方法

没什么说的，直接返回null
因为当前桶位置被占用的话，说明数据还没放到当前位置，当前位置可以理解为就是null

Node<K,V> find(int h, Object k) {
return null;
}

1.5.4 TreeBin的find方法

在红黑树中执行find方法后，会有两个情况
● 如果有线程在持有写锁或者等待获取写锁，当前查询就要在双向链表中锁检索
● 如果没有线程持有写锁或者等待获取写锁，完全可以对lockState + 4，然后去红黑树中检索，并且在检索完毕后，需要对
lockState - 4，再判断是否需要唤醒等待写锁的线程

// 在红黑树中检索数据
final Node<K,V> find(int h, Object k) {
// 非空判断
if (k != null) {
// e：Treebin中的双向链表，for (Node<K,V> e = first; e != null; ) {
int s; K ek;
// s：TreeBin的锁状态
// 00000010
// 00000001
if (((s = lockState) & (WAITER|WRITER)) != 0) {
// 如果进来if，说明要么有写线程在等待获取写锁，要么是由写线程持有者写锁
// 如果出现这个情况，他会去双向链表查询数据
if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
// 说明没有线程等待写锁或者持有写锁，将lockState + 4，代表当前读线程可以去红黑树中检索数据
else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) {
TreeNode<K,V> r, p;
try {
// 基于findTreeNode在红黑树中检索数据
p = ((r = root) == null ? null : r.findTreeNode(h, k, null));
} finally {
Thread w;
// 会对lockState - 4，读线程拿到数据了，释放读锁
// 可以确认，如果-完4，等于WAITER，说明有写线程可能在等待，判断waiter是否为null
if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER) && (w = waiter) != null)
// 当前我是最后一个在红黑树中检索的线程，同时有线程在等待持有写锁，唤醒等待的写线程
LockSupport.unpark(w);
}
return p;}
}
}
return null;
}

1.5.6 TreeNode的findTreeNode方法

红黑树的检索方式，套路很简单，及时基于hash值，来决定去找左子树还有右子数。
如果hash值一致，判断是否 == 、equals，满足就说明找到数据
如果hash值一致，并不是找的数据，基于compare方式，再次决定找左子树还是右子数，知道找到当前节点的子节点为null，停住。

// 红黑树中的检索方法
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk; TreeNode<K,V> q;
// 声明左子树和右子数
TreeNode<K,V> pl = p.left, pr = p.right;
// 直接比较hash值，来决决定走左子树还是右子数
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)p = pr;
// 判断当前的子树是否和查询的k == 或者equals，直接返回
else if ((pk = p.key) == k || (pk != 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.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}