上次写到了HashMap的put函数原理,这次我们来看一看HashMap在调用get函数的时候是什么原理.
上文已经提到了HashMap的数据结构是数组 + 链表/树 的结构 ，那么我们要怎么样才能根据key命中对应的目标呢，且听分解.
强调一下 jdk版本为 1.8.0_121
以下为get(key)源码
/**
* 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;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get(Object key) 中，首先对key进行hash处理,然后将hash值以及key传入getNode(int hash, Object key),那么实际上就是由getNode函数去查询对应的Node/Entry。
接下来我们来分析getNode源码:
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) {
//将table赋值到tab并判断是否有值并且通过(n-1) & hash 计算出key所对应的下标,找到该下标的元素判断其是否为null
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//这里first元素便是所属链表的入口元素 若first的hash以及k值与key的完全相同那么返回first
return first;
if ((e = first.next) != null) {
//这里获取到first下一个元素 并判断元素类型,若是TreeNode则使用平衡树的查询 若不是这遍历链表剩余元素
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))))
//判断他们的hash以及key值 返回满足条件的元素
return e;
} while ((e = e.next) != null);
}
}
return null;
}
到这里，结合上一篇文章 HashMap PUT 详解 首先要理解HashMap的数据结构,
结合数据结构再去看源码就十分容易理解了.
那么通过源码的分析我们还能得出一些HashMap需要注意的点:
1.尽量使用String和一些不可变类型作为key值.由源码我们可以看出,会大量使用hash来进行运算,由于String 为final，对象不可变，因此hash值也会保证不变。
2.由于HashMap线程不安全,当多个线程put时可能会造成线程数据丢失.
3.HashMap数据扩容, 其实在上一篇中在put函数末尾有这么一句代码
if (++size > threshold)
resize();
当数组大小大于阈值时会进行扩容,创建一个于当前数据两倍大小的数据,并把旧数据放入新数组中。
4.在1.8之前resize的代码跟1.8的区别比较大,建议大家对比一下。这里涉及到的是一个环形链表的问题，在1.8之前的版本，当两个线程同时扩容，会打乱链表顺序有一定几率形成环形链表导致无限循环。那么我们看看现在的resize代码如下:
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//这里针对hash值对应下标没有变化的元素
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
//着重看这里 会将loTail的next设置为null
//loTail 表示尾部元素
//这里每次循环链表完成组装后便会设置尾部元素的next为null 避免了环形链表的产生
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;//这里同上理
newTab[j + oldCap] = hiHead;
}
}
}
}
resize代码比较长 这里我只贴了比较重要的部分.
所以在1.8开始 hashMap不会造成环形链表了哈，大家注意了
本篇get 以及 resize就说到这里了。
接下来的文章我准备说说ConcurrentMap,给自己加油！
