前言
如题所示，本文是基于jdk1.8的hashMap源码个人学习思考，内容具有一定主观性，仅供参考。如有错误请指正，感激不尽。
什么是HashMap?：
HashMap是基于散列(hash)函数的数组，每个数组的元素都是Node(继承entry)。Node既具有键值对和hash值，同时也是链表/红黑树的一个节点。
为什么要设计HashMap?
个人觉得是通过散列函数将key映射到对应下标的做法，来实现快速定位、查找、增删kv对。
设计的关键?
前面已经说到，为了快速查找而产生了hashmap。而这种查找是基于散列函数，那么对散列函数就必然要求：1.生成散列值效率要快2.尽可能减少散列冲突3.发生冲突时的选择好的解决方案
当然了，通过看源码，发现了第四点：4.合理、高效的扩容方案。
总结一下，就是：
1.生成散列值效率要快
2.尽可能减少散列冲突
3.发生冲突时的选择好的解决方案
4.合理、高效的扩容方案
源码解析
本文源码解析会针对put流程，按图索骥地来理解hashMap、来引起相关知识点的思考。
put流程
话不多说，先上putVal源码：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//表为空则扩容（表初始化会在第一次Put时进行）
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//下标计算,hash值的设计原理？
tab[i] = newNode(hash, key, value, null);
else {//存在冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//key相等
e = p;
else if (p instanceof TreeNode)//已经是红黑树节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//遍历链表，尾插法，若插入前的链表长度达到7则转化为红黑树
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//达到临界值则扩容
resize();
afterNodeInsertion(evict);
return null;
}
经过梳理，从前到后主要产生了这样几个值得思考的地方
1.临界值设计与扩容规则？
2.hashCode与下标计算方式:为什么要这样设计？
3.为什么是尾插法不是头插法？
4.当冲突达到一定数量(默认是8)后为什么要选择使用红黑树？
下面我们就针对这几个问题作简单的梳理。
1.临界值设计与扩容规则
在putVal的末尾，对size进行了检查,超出临界值则扩容。
if (++size > threshold)//达到临界值则扩容
resize();
什么是threshold？
threshold就是一个临界值，当表实际存放长度大于临界值，则进行resize(扩容)。threshold也是在第一次Put时进行初始化，如下图resize()中的该部分代码所示：
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
于是又出现了新的概念，填充因子(DEFAULT_LOAD_FACTOR 0.75)与默认容量(DEFAULT_INITIAL_CAPACITY 16)。
这些概念以及关于为什么容量是2的幂次等等的问题在网上随便百度就有，就不赘述了。
我们今天着重的一点是，为什么要设计临界值？如果填充因子小于1，那么每次达到临界值时就扩容，不就造成了空间的浪费吗？
这一点就和它散列的性质有关了，填充因子越趋近于1，数据存放的密度就越大，hash冲突的可能性就越高，那出现链表/红黑树的可能性就越大，就会影响查找的效率。
那么是不是填充因子越小越好呢？显然也不是。
的确填充因子越小，数据存放密度越稀疏，产生hash冲突的可能性越小。但数组的利用率也就越低，扩容的操作也就越频繁，而扩容操作实际是遍历+重新计算hash值的过程，比较消耗性能。
所以一个好的填充因子应兼顾空间利用率和hash冲突的概率，那么为什么官方会选择0.75呢？
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
jdk关于hashmap的源码中有这样一段注释，解释了选择0.75的原因，在采用随机hash码的情况下，这样容器中的节点的分布会接近参数为0.5的泊松分布。
这样，一个Bin中的链表长度达到8的概率就小于千万分之一（这就是为什么链表到8后扩容为红黑树）。
总的来讲，0.75就是平衡hash冲突和空间使用率后最终得到的一个结果。
2.hashCode与下标计算方式
我们先来看看hashMap中hashCode的计算方式：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
主要的疑问是为什么hash值要^ (h >>> 16)呢？
因为hash值的计算是为下标计算服务的，那么我们先放下疑问，看看下标是如何计算的
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
在putValue中节选了一段，发现下标计算方式是(n - 1) & hash。
所以index=(n - 1) & (key.hashCode()^ (h >>> 16));//n为数组长度
而通常数组长度都会小于2^16=65536，所以绝大部分时候都是n-1&hash值的低16位。
那么hash值的低十六位随机性越大，下标计算结果不就越随机吗？
因此，选择了用低16位与高16位相异或的方式来加强这种随机效果。
那为什么不选择&或者|呢，因为&结果偏向1，|结果偏向0，就会使随机性大打折扣。
这一点即对应了前面讲的设计关键中的第二点：尽可能减少散列冲突。
3.为什么是尾插法不是头插法？
jdk1.7中冲突后始终使用链表时，put选择的是头插法。
jdk1.8以后引入了红黑树，put变成了尾插法。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
可能会简单地想，反正你要遍历来计算链表长度看是否转化为红黑树，那不就顺便插在尾端了呗。
实际上，头插法转换为尾插法的原因并不在此。
根本原因还是由于resize的线程不安全导致。
使用头插法，在多线程环境下，容易出现环形链表，最终使程序在遍历时陷入死循环。
这一点的详细解析推荐阅读https://www.cnblogs.com/developer_chan/p/10450908.html
4.当冲突达到一定数量(默认是8)后为什么要选择使用红黑树？
使用红黑树，可以使查找性能提升，但相对的，增删成本也会提升。
直接推荐阅读https://www.cnblogs.com/mfrank/p/9227097.html，写的很通俗易懂，也许日后我也会再开一篇文章专门写红黑树。
后记
唔，hashmap的源码思考就先到这儿为止了。为了不误导可能看到这篇文章的人，也查询了不少资料，自己的领悟也更深刻了。写博客确实是梳理思维、提升表达能力的好途径。
网友评论