前言
关于Java的HashMap的资料真的太多了，用被研究“烂”了形容也一点不过分😂，此篇文章就几个疑难问题加上自己这两天的研究，做个总结。
1.原理实现细节总结
1.hashMap在Jdk1.7和1.8略有不一样，1.7是数组+链表，1.8是数组+链表+红黑树。
2.通过系统提供或者自定义的hashCode()算法算出key的hashCode&table.lenth - 1算出index，插入数组当中，时间复杂度为O(1)。
3.不同的hashCode通过&运算得到的index可能相同，我们称之为hash collision(哈希冲突/碰撞)。如果出现碰撞，相同index的bucket将变成链表或者红黑树，1.8中当相同位置的节点大于8时会从链表变成红黑树，相反如果又变成6或者更小时会退化成链表。
4.loadfactor默认0.75，假设数组容量为16，那么当size为12时，数组扩容成32。之前不管是链表还是树上的节点都会重新计算index进行迁移。
5.hashMap中即使会涉及到一些链表和二叉树搜索树的遍历，但get和put的时间复杂度也可以近似看成O(1)。
6.当数组容量小于64的时候，当链表大于8的时候也不会树化，而是优先扩容。
2.为什么loadfactor是0.75
查遍网上资料，好像没有官方解释。然后看到很多文章都是乱说的，什么泊松分布之类的，都是文不对题。
https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap/31401836#31401836
里面第三个答案好像是现在公认的比较可信的说法。
第一次看到这个还是有点懵逼，这个ln(2)是怎么算出来的。
昨晚我自己在书房推了一遍，这里需要用到离散概率和无穷比无穷求极限的一些大学数学基础知识。
当数组的容量趋向于无穷大时，负载因子约等于0.7，小于这个值，意为”不太容易”发生hash碰撞，所以各个语言的hashMap的loadfactor也略有不同。
3.树化问题
既然遍历链表的复杂度是O(n)，而红黑树因为有自平衡的特点复杂度是O(log(n))，为什么不直接用红黑树呢？
因为单个 TreeNode 需要占用的空间大约是普通 Node的两倍，这个很好理解，TreeNode中有颜色属性，父节点，左右子节点等属性，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD的值决定的。而当桶中节点数由于移除或者resize变少后，又会变回普通的链表的形式，以便节省空间。通过查看源码可以发现，默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了时间和空间平衡的思想，最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树，需要确定一个阈值，这个阈值默认为 8，并且在源码中也对选择 8 这个数字做了说明，原文如下：
大概意思:
如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，在loadfactor等于0.75的情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。但，顶不住我们故意把算法变得不均匀，例如下面的代码:
1
2
3
4
@Override
public int hashCode() {
return 1;
}
这样一旦size过大，hashMap必树化。
事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。
所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突。
4.JDK1.7头插问题
JDK1.7的hashMap在扩容时的数据迁移时，遍历节点，之后采用头倒序的方式进行迁移，也就是后遍历到的节点，会插到新数组节点的头部，这样在多线程的情况会出现循环链表的情况。
下面这篇文章：
我觉得讲的是讲得比详细，也是比较通俗易懂的，这边不做过多的解释了。
我想谈谈的是关于这个”bug”的看法:
首先hashMap本身就是线程不安全的，官方本身就不建议你这样使用。
关于这个bug的讨论就好比你在一个错误的情况讨论一个错误的事情。
虽然我个人认为这不是一个bug，但是JDK还是在1.8修复了这个问题，改成了尾插。但hashMap在1.8的多线程中同样会有别的问题。
最后再来说说为什么1.7会设计成头插？
有一种说法是：缓存的时间局部性原则 (新插入的数据可能会更早用到)。这一点在操作系统中有很常见的应用，例如LRU算法。
5.JDK1.8不安全问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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)
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))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
主要是在put当中发生的问题，第6行代码，如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
6.总结
学无止境
感谢
为何hashmap默认的负载因子是0.75？应该是空间和时间的折中，背后的统计原理是什么呢？
