【JAVA】HashMap的原理及多线程下死循环的原因

  再次翻到以前工作中遇到的一个问题，HashMap在多线程下会出现死循环的问题，以前只是知道会死循环，导致CPU100%把机器拖跨，今天来彻底看看

首先来看下，HashMap的原理：HashMap是一个数组，对key使用hash算法计算出数组对应的下标i，然后把<key, value>插到table[i]，如果两个不同的key被算在同一个i，那就出现冲突，又叫碰撞，这样就会在table[i]上形成一个链表；总结下来HashMap是一个数组+链表组成的数据结构；

我们知道，在往HashMap里put元素的时候，会有一个key，我们先会取到这个key的下标，实际上是key对应类型的hashCode()方法，而HashCode又是什么呢？

提到HashCode，首先我们要了解到一种数据结构，散列表(HashTable，也叫哈希表），是根据关键码值(Key Value)而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的 字段等）映射成一个数值，这个数值称作为散列值。

再回来看看，HashCode对应的就是关键码值的Key，然后我们把Java代码中String的hashCode计算代码撸出来看看：

算出来的hashCode，实际上是根据字符的值进行计算，假设我们要计算“abc”的hashCode，收计算出来是多少呢？

a对应的int值是97，b=98，c=99；那么根据以上算式计算出来的结果应该是：31 * (31 * (31 * 0 + 97) + 98) + 99

结果是多少不重要，但是我们看的出来，这个字符串的hashCode肯定是唯一的，因为每个字符对应的值是不一样的，算出来肯定不一样

理解了上面的过程，我们再来看看多线程下面的死锁的问题，有很多文章 写的很复杂，总结下来需要满足以下几个条件：

1. 两个线程在对同一个hashMap进行处理
2. put数据的时候产生了冲突，就是在table[i]上需要存储多个元素（即一个链表）,冲突太多，执行效率就会下降，所以数组大小的设定很重要
3. 现在假设出现冲突比较厉害的时候，这个时候需要对HashMap进行重组，即容量增加，用以减少冲突
4. 这个时候需要将老的HashMap的元素重新拷贝（实际上不是拷贝，而只是重新引用地址，不new新对象）到新的HashMap中，在table[i]上存储多个元素的时候，两线程同时进行，导致链表出现循环链表即：A->B  && B->A
5. 假设现有的链表数据是A->B->null
1. 第一个线程执行时e=A，next=B，暂停
2. 第二个线程执行新链表执行完成，数据为B->A->null；
3. 此时第一个线程继续执行
1. 第一次循环的时候是A->null，
2. 第二次循环的时候是B->A->null，
3. 由于第二个线程已经修改了链表的结构(B->A->null)，此时取B的next的时候，取到的是A
4. 将A放到新数组中，结构为：A->B->A；此时老的链表取的的e = null，结束循环
5. 此时链表已形成A<->B
6. 出现循环链表之后，触发条件是在get循环链表中的数据时，出现无限循环，导致CPU被耗尽，机器挂掉

在理解这个问题的时候有很重要一点，当多个线程在执行时，每个线程都会定义一个table对象，假设是两个线程在执行，那么这里有三个table

1. 老的table
2. 线程1的table
3. 线程2的table

但是表里的链表是引用类型的，即地址是一样的，对链表做变更的时候，会影响全局Map;

这里面有几个点：每个table都是引用类型，而表里面的每个链表结构元素也是引用类型，改变了引用类型的结构是全局的改变，不单是一个线程的变量；

解决办法：

1. 在使用HashMap的时候，不要在多线程的环境中使用，如果需要使用，可以使用ConcurrentHashMap
2. 确实要使用的时候使用synchronized关键字

后记：在前面讨论的时候我们看到，如果在hashMap里面将老的元素拷贝到新的表上去时，就不会出现死循环了，但是又会出现新的问题，元素永远不一致，因为各个线程上的值不一致，所以在多线程中使用集合类型时一定要注意线程安全问题

参考文章：

浅谈Java中的hashcode方法：http://www.cnblogs.com/dolphin0520/p/3681042.html

疫苗：JAVA HASHMAP的死循环：https://coolshell.cn/articles/9606.html

这个例子更加清晰，我是看这个看懂的：https://blog.csdn.net/zhuqiuhui/article/details/51849692