HashMap源码之二：get方法
2018-08-03 本文已影响49人
涂豪_OP
上篇文章分析了HashMap的put方法，既然有put，就肯定有get方法，下面分析get方法：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
//核心就是这个getNode方法，根据key的hash值找
//Node，找到了就返回Node的value，否则就返回空，没找到
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get方法很简单，没什么好说的，核心是getNode方法：
/**
* Implements Map.get and related methods
*
* @param hash hash for key 查找的key的hash值
* @param key the key 查找的key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
//tab就是HashMap的数组；first是每个通上的节点；
//n是数组的长度；k是节点的hash值
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//一通判断，首先数组不能为空；其实数组长度要大于0；
//最后算出来的桶里面必须要有节点，都很简单，不多说
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//把首节点拿出来单独判断，若干hash值一样，key也一样，那么直接返回首节点
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 {
//往死里循环，直到此链表遍历完了；查找的依据是hash相同，key也相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
getNode方法也很简单，首先判断首节点是不是我们要找的节点；如果不是的话，就看这个节点是不是红黑树节点，如果是红黑树节点，那么以查找红黑树的方式去搜索；如果是普通节点的话，那么用do ... while循环去遍历这个链表；遍历链表很简单，直接看红黑树的搜索：
/**
* Calls find for root node.
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
//首先拿到红黑树的根节点，然后调用find方法去搜索红黑树；root方法
//太简单，不管；find方法在上一篇文章讲过，但是没分析，这次分析下
return ((parent != null) ? root() : this).find(h, k, null);
}
getTreeNode方法很简单，就是简单的调用了find方法，下面分析：
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
* h : 要查找的key的hash值
* k : key的值
* kc : key的Class对象，传进来的null
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc)
{
//find本来就是TreeNode的方法，this代表调用find的TreeNode
TreeNode<K,V> p = this;
do {
//ph是遍历到的节点的hash值；dir是目标key
//和红黑树节点的key比较的结果pk是节点的key值
int ph, dir; K pk;
//定义左右子节点和节点q
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果节点的hash大于目标key的hash，那么在这
//个节点的左子树中查找，所以讲p指向p的左子节点
if ((ph = p.hash) > h)
p = pl;
//如果节点的hash小于目标key的hash，那么在这
//个节点的右子树中查找，所以讲p指向p的右子节点
else if (ph < h)
p = pr;
//如果节点的hash和key的hash相等，而且节点的key
//和目标key相等，说明找到了，此时返回此节点即可
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//下面的流程是目标key的hash和节点hash
//相等，但是目标key和节点key不等的场景
//pl == null遍历到的节点没有左子节点了，怎么办？当然
//是从右子树开始继续搜索，所以这里就将右子节点赋值给p
else if (pl == null)
p = pr;
//同上，但是是从左子树开始继续搜索
else if (pr == null)
p = pl;
//comparableClassFor(k))的作用是判断目标key是否实现了Comparable
//接口，也就是判断目标key是否有可比性，如果返回null说明没实现接口，
//没有可比性；可比性dir = compareComparables(kc, k, pk))
//!= 0是说明目标key和节点的key具有可比性，dir就存放了对比的结果，
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
//根据dir赋值左子节点或者右子节点，继续下一轮搜索
p = (dir < 0) ? pl : pr;
//流程走到这，说明目标key和当前节点没有可比性，或者比较不出来
//结果，那么从这个节点的右子节点开始继续递归搜索，直到找到为止
else if ((q = pr.find(h, k, kc)) != null)
return q;
//如果右子树没有找到，那么从左子树开始继续找
else
p = pl;
} while (p != null);
//如果没找到就返回空
return null;
}
总的来看，find方法还是蛮简单的，自此，get方法分析完毕。
下面分析remove方法：
/**
* Implements Map.remove and related methods
*
* @param hash hash for key key的hash值
* @param key the key key本身
* @param value the value to match if matchValue, else ignored key对应的value,传进来是空
* @param matchValue if true only remove if value is equal 是否值删除key和value都匹配的节点
* @param movable if false do not move other nodes while removing 删除节点后是否移动别的节点
* @return the node, or null if none
*/
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;
//一波判断，前面的getNode方法解释过，pass
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;
//下面的一波操作是跟getNode一毛一样的，不多解释
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就是查找出来的节点。remove是一个重载的方法，有一个参数和两个参数的，两个参数的
//方法不光要判断key，还要判断value，matchValue就是表示要不要判断value；如果找出来
//的节点是红黑树节点，那么调用removeTreeNode去红黑树中删除节点，否则删除链表中的节点
//，链表删除节点很简单，就是把node他爹的next指向node自己的next，不多解释
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;
//删除操作也是修改HashMap，所以modCount自增
++modCount;
//HashMap元素个数自减，没毛病
--size;
//回调，在put方法中解释过，pass
afterNodeRemoval(node);
//返回删除的节点
return node;
}
}
//没有找到目标节点就是返回空
return null;
}
removeNode比较简单，删除的第一步就是查找，跟上面get方法一样，找到节点后就删除，其中链表节点的删除很简单，不分析，下面分析红黑树的删除：
待定
