本文是hashMap系列的最后一篇文章，如果您觉得写得还不错的话，请关注本公众号
接上文
六 HashMap是如何解决hash冲突的
解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。
HashMap是用拉链法解决的Hash冲突问题。HashMap的数据结构 ，前两篇文章有介绍过，jdk1.7 是数组+链表的结构 ，jdk1.8是数组+链表+红黑树。正是为了解决Hash冲突以及平衡查询、插入等操作的效率HashMap的作者才将HashMap设计成这种数据结构
我们来具体看一下put方法的源码(jdk1.8)，通过这个过程了解下如何解决冲突
1/**
2 * Implements Map.put and related methods.
3 *
4 * @param hash hash for key
5 * @param key the key
6 * @param value the value to put
7 * @param onlyIfAbsent if true, don't change existing value
8 * @param evict if false, the table is in creation mode.
9 * @return previous value, or null if none
10 */
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13
14 Node<K,V>[] tab; Node<K,V> p; int n, i;
15
16 //tab为空则创建
17 if ((tab = table) == null || (n = tab.length) == 0)
18 n = (tab = resize()).length;
19 //计算index，并对null做处理
20 if ((p = tab[i = (n - 1) & hash]) == null)
21 tab[i] = newNode(hash, key, value, null);
22 else {
23 Node<K,V> e; K k;
24 //节点key存在，直接覆盖value
25 if (p.hash == hash &&
26 ((k = p.key) == key || (key != null && key.equals(k))))
27 e = p;
28 //判断该链为红黑树
29 else if (p instanceof TreeNode)
30 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
31 else {
32 //该链为链表
33 for (int binCount = 0; ; ++binCount) {
34 if ((e = p.next) == null) {
35 p.next = newNode(hash, key, value, null);
36 //链表长度大于8转换为红黑树进行处理
37 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
38 treeifyBin(tab, hash);
39 break;
40 }
41 //key已经存在直接覆盖value
42 if (e.hash == hash &&
43 ((k = e.key) == key || (key != null && key.equals(k))))
44 break;
45 p = e;
46 }
47 }
48 if (e != null) { // existing mapping for key
49 V oldValue = e.value;
50 if (!onlyIfAbsent || oldValue == null)
51 e.value = value;
52 afterNodeAccess(e);
53 return oldValue;
54 }
55 }
56 ++modCount;
57 //超过最大容量 就扩容
58 if (++size > threshold)
59 resize();
60 afterNodeInsertion(evict);
61 return null;
62 }
HashMap的put方法执行过程可以通过下图来理解
通过上图和源码注释，我们了解了put方法的执行过程，其中在这一行：
1if ((p = tab[i = (n - 1) & hash]) == null)
计算 index，并对 null 做处理，如果不为 null ,则表明 tab 的这个 i 位置上已经有数据了，hash冲突就发生在了这里。从这里的else条件开始就是hashMap解决hash冲突的过程。也就是所谓的“拉链法”。
这里有几个需要注意的点：
HashMap采用的链表法的方式，链表是单向链表
当发生hash冲突，hashMap的桶中形成链表的时候，新的元素插入到该链表的时候，jdk1.7使用的是“头插法” 即新元素在链表头，而jdk1.8使用的“尾插法” 即新元素在链表尾。
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap
思考题：jdk1.8为什么改头插法为尾插法？
关于上面第三点，其中有个著名的例子，就是在多线程环境下使用HashMap可能产生环链（死循环）问题，当然是在jdk1.7版本，jdk1.8由于使用了“尾插法”就避免了这个问题。在使用jdk1.7的情况下，是put过程中的resize方法在调用transfer方法的时候导致的环链。
我们举例说明一下：
1public class HashMapInfiniteLoop {
2
3 private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);
4 public static void main(String[] args) {
5 map.put(5， "C");
6
7 new Thread("Thread1") {
8 public void run() {
9 map.put(7, "B");
10 System.out.println(map);
11 };
12 }.start();
13 new Thread("Thread2") {
14 public void run() {
15 map.put(3, "A);
16 System.out.println(map);
17 };
18 }.start();
19 }
20}
其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。下面代码是jdk1.7的
1void resize(int newCapacity) { //传入新的容量
2 Entry[] oldTable = table; //引用扩容前的Entry数组
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
5 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
6 return;
7 }
8
9 Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
10 transfer(newTable); //！！将数据转移到新的Entry数组里
11 table = newTable; //HashMap的table属性引用新的Entry数组
12 threshold = (int)(newCapacity * loadFactor);//修改阈值
13}
14
15 void transfer(Entry[] newTable) {
16 Entry[] src = table; //src引用了旧的Entry数组
17 int newCapacity = newTable.length;
18 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
19 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
20 if (e != null) {
21 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
22 do {
23 Entry<K,V> next = e.next;
24 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
25 e.next = newTable[i]; //标记[1]
26 newTable[i] = e; //将元素放在数组上
27 e = next; //访问下一个Entry链上的元素
28 } while (e != null);
29 }
30 }
31
通过设置断点让线程1和线程2同时debug到transfer方法的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的断点，让线程2进行完resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二 rehash 后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
HashMap 有并发问题，并不单单指环链问题，而是在数据结构的设计上就没有考虑并发环境。HashMap 的设计目标是简洁高效，没有采取任何措施保证 put、remove 操作的多线程安全。put 方法的操作对象要么是整个散列表，要么是某个哈希桶里的链表或红黑树，而这些过程都没有采取措施保证多线程安全。在这个复杂的逻辑过程中，任何一个线程在这个过程中改动了散列表的结构，都有可能造成另一个线程的操作失败。
java有一条深入人心的规则：“重写equals()时，必须重写hashCode()”, 那么这是为什么呢？我们从hashMap的源码中也能看出些原因
1 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
2 e = p;
上面这段比较简单就不解释了，试想如果你的对象没有正确重写这两个方法，那么装在容器中一定会有问题。
参考 ：
关注公众号 获取更多精彩内容