在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
hash值：指的是数组的下标；
Hash值的计算方法： // ^异或：如果相对应位值相同，则结果为0，否则为1 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 并以此确定key的在数组中的位置， // i 为数组下标，使用位运算&，执行效率更高，&如果对应位上都为1，值为一，否则为0 int i = (n - 1) & hash;
Hash碰撞：多个元素计算得出相同的hashCode，在put时出现冲突。HashMap是将无限的元素存放到有限的数组中，所以hash碰撞在所难免。
从上述我们可以得知，从key映射到HashMap数组的对应位置，会用到一个Hash函数，那么问题来了，如何实现一个尽量均匀分布的Hash函数呢？
取模运算？这种方式固然可以，但是效率很低，为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。
index = HashCode（key） & (length-1)
下面我们以值为“book”的Key来演示整个过程：
1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
4.假设需要扩容，第一次扩容，扩容后HashMap长度变成32，计算Length-1的结果为31，二进制为11111;
5.将book的hashcode与数组长度做与运算，101110001110101110 1001 & 11111 = 1001，此时并不需要移动book在数组中的位置。index=9，
6.假设第二次扩容，101110001110101110 1001 & 111111 = 101001，此时index=32+9=41，仅需要移动到oldIndex + oldLength = 9 + 32 = 41；
这样可以保证hashMap中元素均匀分布。
链地址法：数组中每个元素都存有一个单链表，发生 Hash 冲突时，只是将冲突的 value 当作新节点插入到链表（HashMap 解决冲突的办法）。
HashMap是使用链地址法解决hash冲突的，即数组+单链表+红黑树；
1.JDK8以前是头插法，JDK8后是尾插法
2.为什么要从头插法改成尾插法？
A.因为头插法会造成死链，参考链接
while(null != e) { Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了 e.next = newTable[i]; newTable[i] = e; e = next; }
多线程，进行rehash，transfer()方法时，造成死链。
比如：hashmap死锁主要是一个线程执行transfer过程中，被另一个线程改变了链表元素（共同资源）的指针指向；
B.JDK7用头插是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)，但这其实是个伪命题,因为JDK7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置(就是因为头插)
所以最后的结果 还是打乱了插入的顺序 所以总的来看支撑JDK7使用头插的这点原因也不足以支撑下去了 所以就干脆换成尾插 一举多得
原文：https://www.cnblogs.com/little-learner/p/14414387.html