“ 本文将主要介绍HashMap的get。”
相关阅读:
JDK1.8HashMap源码学习-put操作以及扩容(一)
JDK1.8HashMap源码学习-put操作以及扩容(二)
本文我们学习一下get操作,让我们看下源码。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
我们看到核心其实就是将传入的key计算了hash值,然后将key值一起作为参数调用getNode(hash,key)并对返回值做判断,如果返回为null则返回null,否则返回对应value。
接下来看下核心方法
/**
* hash key的hash值
* key
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
/**
* 1、赋值到临时数组并判断不为空 (tab = table) != null && (n = tab.length) > 0
* 2、数组下标保存的值不能为空 即(first = tab[(n - 1) & hash]) != null
*/
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//头节点的hash值与要获取值的key的hash值一致 且 key值相等 说明找的就是该头节点 直接返回
//每次都要执行是因为这是单链的头节点 需要从该节点进行查找
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))){ // always check first node
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;
}
我们再看下如果根节点是红黑树节点,是如果进行操作操作的。
final TreeNode<K,V> getTreeNode(int h, Object k) {
//如果现在节点的父节点不为空 则需要先找到根节点
//如果为空 说明当前的节点就是根节点
//通过根节点去查找数据
return ((parent != null) ? root() : this).find(h, k, null);
}
/**
* 通过根节点查找对应的节点数据
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//调用的时候就是使用的根节点调用 所以this指向的是根节点
//也就是说 p在刚进入的时候就是红黑树的根节点
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
/**
* pl 当前节点的左孩子
* pr 当前节点的右孩子
* q 右孩子查找结果返回的临时赋值
*/
TreeNode<K,V> pl = p.left, pr = p.right, q;
//执行赋值操作 ph = p.hash
//比较当前节点hash和要获取节点hash
if ((ph = p.hash) > h){
//当前节点的hash大于要获取的节点hash
//则移动节点为当前节点的左孩子
p = pl;
}else if (ph < h){//移动为右孩子
p = pr;
}else if ((pk = p.key) == k || (k != null && k.equals(pk))){//hash值一致且key值一致 即找到 返回
return p;
}else if (pl == null){//如果没有左孩子 则移动为右孩子
p = pr;
}else if (pr == null){//如果没有右孩子 则移动为左孩子
p = pl;
//hash值一致 左右孩子都有 判断传入的key是否可比较 根据比较判断是找左孩子还是右孩子
}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;
}
上一个红黑树查找动态图
下一篇我们学习下remove操作。