hashMap 查找元素方法 get() 详解
查找方法，通过元素的 key 找到 value。
代码如下：
```java
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
```
get 方法主要调用的是 getNode 方法，代码如下：
```java
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果哈希表不为空并且key对应的桶上不为空
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) {
// 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
```
小结：
1.get 方法实现的步骤：
a. 通过 hash 值获取该 key 映射到的桶
b. 桶上的 key 就是要查找的 key，则直接找到并返回
c. 桶上的 key 不是要找的 key，则查看后续的结点：
如果后续结点是红黑树结点，通过调用红黑树的方法根据 key 获取 value
如果后续结点是链表结点，则通过循环遍历链表根据 key 获取 value
2.上述红黑树结点调用的是 getTreeNode 方法通过树形结点的 find 方法进行查找：
```java
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
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 = 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.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
```
3.查找红黑树，由于之前添加时已经保证这个树是有序的了，因此查找时基本就是折半查找，效率更高。
4.这里和插入时一样，如果对比结点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回。不相等就从子树中递归查找。
5.若为树，则在树中通过key.equals(k)查找，O(logn)。若为链表，则在链表中通过key.equals(k)查找，O(n)。
公众号进入网站体验更佳
