HashMap实现原理：
JDK1.7：数组+单向链表（头插）
在并发情况下头插可能出现循环链表(死循环)问题。原因：因为头插，在新数组中链表的元素顺序发生了变化，
如上图，假设线程1在扩容，刚刚调整链表完毕；线程2的指针却指向的还是原来的元素。这时新数组链表中是1->2->3的指向，但是线程2却是调整（扩容）前的3->2指向
JDK1.8：数组+单向链表（尾插）+红黑树
HashMap中数组的大小有什么特点？
初始化时数组的容量是2的幂次方数，即16;
如果初始化时指定数组大小，比如17，则实际数组大小是>17的2的幂次方数，即32.
HashMap中如何计算数组下标？
HashMap的键值对组成了数组，数组就有下标索引问题。需要根据key来计算当前key-value在数组中的位置：
可以看到，通过哈希值和(数组长度-1)的与操作【位运算】（代替取余）来计算数组下标，这种位运算要求数组大小必须为2的幂次方。
奇数做位运算时，高位一定是0；奇数和哈希值做位运算，结果取决于哈希值的低位。
为何用二次哈希结果计算索引？为了让计算索引的hashcode值分布得更加均匀。
假设数组长度是10，现在有80个元素都有哈希冲突，理想情况是每个数组位，存1个元素+7个元素长度的链表。这就是分布均匀。
分布不均匀：某些链表非常长（被迫转换成红黑树），某些链表过短。
更多关于二次哈希移步
（JDK1.8为右移16位）
如何解决Hash冲突
上一篇文章有简单说明。
何时触发自动扩容机制
数组扩容因子=0.75
链表的长度>8 & 数组长度>=64,==>红黑树
红黑树生成时Node-->TreeNode的转变，同时会将单向链表转变成双向链表。
*本篇暂不阐述HashMap并发相关知识点。后续单独开新篇。
标签：扩容,HashMap,数组,链表,哈希,红黑树,原理 From： https://www.cnblogs.com/hangwei/p/16931453.html