HashMap还有ConcurrentHashMap我跟你拼了(第一章)-轻识

小故事

最近面试流行ConcurrentHashMap，还有这个HashMap为啥线程不安全。我直接说的，如果两个线程同时操作HashMap的话，如果大家都进行一个get操作，再put操作，那么就会导致1号线程get操作完成，put操作之前，2号线程get了旧的值，然后1号线程更新之后的值并没有被2号线程取到，导致两次操作的效果变成了一次操作的效果。例如，get一个数值，进行+1操作，结果两个线程过去，发现加了1，并没有+2。

显然，我已经回答错了，面试官直接说，这是你业务上的问题，和人家HashMap没有关系。这是你业务上没有控制get和put的原子性导致的。我彻底懵了，我果然是个渣渣。

本来想总结完的，奈何没有足够的时间了，明天还有事情，我们下一章接着完善。

面试流程

能当得了面试官，那一定是个久经沙场的渣男，他并不会像钢铁直男那样直奔主题，而是会由浅入深，缓缓地套路你，直到你进入他设计好的陷阱之中。所以一般的面试流程都是这样开始的。

小伙子你了解数据结构中的HashMap么？聊聊他的数据结构和底层原理？

HashMap，这个我知道，我很了解他，不就是个数组+链表吗。数组用来散列，链表用来解决哈希碰撞。就这么简单吗，是不是，完事。哦对了，在JDK1.8的时候，当链表过长同时数组容量大于64阈值（最小树化容量）的时候，链表会转变为红黑树。呵呵，64这个点也被我答出来了，这下没话说了吧。

那你给我说下链表过长是什么意思？

就是链表长度大于等于8的时候，他就会进行树化，但是一定要注意此时哈希数组的容量不能小于最小树化容量64，否则他会再次进行扩容来分散节点，而不是进行树化。

那你给我说下为什么这个长度是8？

纳尼，卧槽，这就触及我的知识盲点了。为什么是8，难道这是个经验数字？那他是怎么推导来的呢。难道是为了让数据分散的更加均匀？不对，这不符合逻辑啊。正常的逻辑应该是链表过长肯定会影响查询效率，所以才需要变为红黑树来加快查询，但是这个8是为什么。

网上主流的答案：

红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，红黑树的查找效率更高，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。当时面试官也是这样给我解释的，逻辑上确实也对。

但是我查看了源码后，发现设计者真正的想法并不是这样的。而是：

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

如果 hashCode的分布离散良好的话，我们基本上用不到红黑树这玩意儿（纳尼，原来这玩意大部分时候只是个摆设），因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据。如果我们的数据离散性确实很差，那么这个时候就要变成红黑树来提高查询效率了。

很可能会树化的代码案例：

在HashMap中，决定某个对象落在哪一个 “桶“，是由该对象的hashCode决定的，JDK无法阻止用户实现自己的哈希算法，如果用户重写了hashCode，并且算法实现比较差的话，就很可能会使HashMap的链表变得很长，就比如这样，相信这段代码小伙伴们看了一定想要骂娘，这又是哪个傻叉写的屎山，结果看了一下作者，沃特法克，小丑居然是我自己。

public class HashMapTest {
public static void main(String[] args) {
Map<User, Integer> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
map.put(new User("鄙人薛某" + i), i);
}
}

static class User{

private String name;

public User(String name) {
this.name = name;
}

@Override
public int hashCode() {
return 1;
}
}
}

总结下来就是，主流的说法也符合逻辑，但是8这个值却是用上边这种方法定下来的。所以到时候就看你碰到的面试官是那种面试官了，如果面试官脑子里背的是主流的方法，那么你最好回答主流的，当然如果你能把面试官吊打一顿，他也很佩服你也行，但是也别打的太狠，不然你肯定也会与这次面试机会失之交臂，懂得都懂。

既然链表查询效率不如红黑树，为什么不一开始就用红黑树，为什么还要用链表

这个我们就需要采取JDK源码中的另一段解释了，这个解释也符合常理。

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.

因为树节点一般是普通节点的两倍大，所以我们通常只有在链足够长的时候使用它。其实就是这个节点太占空间了，所以如果在链表短的时候查询效率相差不大，我们就用链表就完事了。

那什么条件下，红黑树会退化为链表。

在红黑树节点移除达到6的时候，会退化为链表结构。

为什么会是6这个数字，你明明在8的时候树化的，为什么不在小于8的时候就退化呢。

因为树化和退化是一个比较繁琐的过程，链表和树结构频繁转换会导致性能降低，所以如果还能将就着用，那就用现成的，别转来转去的。

你能给我讲讲HashMap的扩容吗。

终于到了这个问题了，HashMap的初始默认桶数量（数组长度）为16，但是我们可以指定默认大小，同时指定扩容因子，默认扩容因子为0.75。当含有元素的桶的数量超过负载因子比例时，会触发resize操作，还有当链表长度达到8同时发现数组容量没有超过64，也会在树化方法中触发resize而不触发树化操作。

具体的扩容操作就是，创建一个新的数组，长度是原来的2倍，然后遍历原数组，进行rehash操作，因为新的数组长度变化了，所以原来节点的下标已经不再适用于新数组的下标。

i = (n - 1) & hash(key)

你能给我说说JDK1.7和JDK1.8HashMap扩容时候的区别吗

我擦，还好我早有准备。这是Jdk1.7和Jdk1.8的扩容之后节点新的数组下标的计算方式。很明显的一点，JDK1.7会把节点全部重新进行一次hash操作。

下边图片的操作，由于扩容总是2的倍数，所以从二进制的角度来看，每次扩容其实就是数组长度左移一位。而我们原来计算hash的时候是用hash值与旧数组容量-1的方式计算。而数组容量实际上应该是更高位为1。例如旧数组容量16，那么数组容量实际上是1 0000，而我们计算的时候16-1，实际上是0 1111。所以如果在新的数组里面，32 -1 ，二进制为 1 1111。如果节点hash值高位并没有超越 1 0000，也就是还是在 0 1111这里面，那么你与新的1 1111 与运算之后，还是在低位。所以此时，jdk1.8，如果hash值与旧容量与运算为0，那么就证明在新的数组中，这个节点实际上位置不变。而如果hash值与旧容量与运算为1，那么就证明在新的数组中，该节点高位为1，同时其低位都是与1进行与运算，而旧数组容量恰好就是高位值。所以直接原来的索引+旧数组容量刚好与重新rehash的值相同。

牛逼，你能说下JDK1.8之前为什么会有死循环的问题吗，在什么情境下会发生。

HashMap1.7当中，扩容的时候，采用的是头插法转移结点，在多线程并发的情况下会造成链表死循环的问题。

假设有两个线程，线程1和线程2，两个线程进行hashMap的put操作，触发了扩容。下面是扩容的时候结点转移的关键代码

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {//两个线程都先进入if
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; //线程1 这里还没执行停下
newTable[i] = e;
e = next;
} while (e != null);
}
}
}

线程1和线程2 都进入if，然后线程1没有拿到cpu的资源在上面代码注释的地方停下了。此时的变量指针如下图所示：

记住线程1中 E变量指向a结点，next变量指向b结点。

下面是线程2 拿到cpu的资源，执行结点转移

线程2停下，轮到线程1

因为之前线程1中E变量指向的是a结点，next变量指向的是b结点，所以如下图所示：

再来看看刚才线程是在e.next = newTable[i] 这句代码还没执行的时候停下的，那么现在就要执行这一句代码

void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {//两个线程都先进入if
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; //线程1刚才在这里停下，所以现在从这一句代码开始执行
newTable[i] = e;
e = next;
} while (e != null);
}
}
}

此时线程1 执行代码之后，就造成了链表的死循环，结果如下：