本文将HashMap分两个版本剖析
jdk7->jdk8以前的版本
jdk8->jdk8版本

jdk7的HashMap

数据结构：数组 + 链表
链表中数据插入方式:头插法

jdk8的HashMap

数据结构：数组 + (链表 || 红黑树)
链表中数据插入方式：尾插法
构造方法：扩容因子
扩容原则：元素总量大于数组容量 * 负载因子时会扩容
特点：链表再特定情况下会树化

链表的长度是否可以超过8

当数组的大小<64时，put后链表的长度会>8，只会对链表进行扩容。如果扩容后该链表中的所有元素桶下标(数组索引)值全部相同，那么链表长度就有可能>8。

红黑树的基本特点

父节点的左侧元素都<父节点，父节点的右侧元素都>父节点。

树化的条件

数组长度>64 && 链表长度>8。

当某一个数组下的链表大于8时再继续插入数据，如果当前数组的大小<64则会对数组进行扩容而不是进行树化，只有数组的大小>64时，链表>8再继续插入才会树化。

为什么使用红黑树

红黑树可以防止特殊情况下(攻击者刻意构造的key，使得同一桶下标链(数组中部分索引下的链表过长)查询性能下降。
一般情况下，链表都不会达到树化的条件(正常的hash分布链表长度几乎不会超过6)。

为什么不一开始就树化

链表短的时候查找性能是由于红黑树的，红黑树的查找更新时间复杂度是O(log₂ⁿ)，TreeNode占用的内存空间>普通的Node，通常控制链表的长度，再结合数组扩容。链表的综合性能会优于红黑树。

树化的阈值为什么是8

正常情况下链表中的元素个数几乎不会>8个，树化是在非正常情况下才有的操作，即在hash分布均匀时加上扩容操作几乎不会发生树化。一旦发生树化说明数据为极其特殊的情况。

什么时候会退化为链表

• 情况一
  扩容时会拆分树，当树的大小<=6时就会发生退化
• 情况二
  remove树中的节点时，在remove之前，如果根节点(root)，根左子节点(root.left)，根左孙节点(root.left.left)，根右子节点(root.right)存在null时，也会退化成链表。

数组索引(桶下标)的计算

对象的原始hashCode获取hash值，在hash值的基础上再次执行二次hash(扰动)，得到二次hash的值，将第二次hash值与数组容量求模，结果就是数组索引(桶下标)。

二次hash值为97，数组大小=16
数组索引(桶下标) = 97 % 16 = 1
实际的实现是 二次hash值 & (数组大小-1) ，97 & (16-1) = 1 。
注: 这种 97 % 16 和 97 & (16-1) 结果相同的前提是， 除数(16)必须是2的n次幂。

二次hash过程(扰动)

二次hash的目的：让元素分布的更均匀，避免某个链表过长。
低位去求模的时候很容易发生hash聚集的情况。通过右移16位(留下高位)，和原始hash 异或 得出更均匀的结果。

数组长度为2的n次方的优点

可以将求模运算转换为 按位与 运算，提升性能。
扩容时桶下标重计算时可以优化运算。

扩容时判断链表中的元素所属桶下标是否改变。

二次hash值 与 原始数组大小求模 结果为 0 ，那么扩容后该元素的桶下标不会改变。
如果 二次hash值 与 原始数组容量求模 结果 != 0，那么扩容后的桶下标为原始容量+原始桶下标=扩容后桶下标。

数组容量为2的n次幂时的缺点

hash分布较差,如果key值都是偶数，偶数和偶数求模的结果依旧是偶数，奇数索引没办法利用浪费资源。
质数数组容量的hash分布较偶数数组容量好。
综合来看数组容量为2的n次幂效率更好(使用位运算优化性能)，如果希望有更好的hash分布行应该选择一个较大的质数作为数组容量。

1.8之前和1.8之后 put方法流程对比

• HashMap的数组创建是懒汉式的，首次put才会创金数组。
• 计算元素在数组中的索引(桶下标)
• 如果桶下标下没有元素，则会创建Node占位。
• 如果桶下标下已经有元素占用，
  • 如果是TreeNode走红黑树的增删改逻辑
  • 如果是普通Node，走链表的添加或更新逻辑，如果链表长度超过树化的阈值，走树化的逻辑。
• 检查元素数量是否超过阈值，超过阈值进行扩容。

为什么负载因子默认是0.75f

• 在空间占用与查询时间之间取得较好的权衡
• 大于这个值,空间节省了，链表相对较长影响性能
• 小于这个值，hash冲突小了，但是扩容会更加频繁，并且占用更多的空间

多线程时HashMap存在的问题

jdk7 数据错乱、扩容死链
jdk8 数据错乱

死链的原因，头插法在迁移的时候链表顺序会改变。
jdk7在迁移的时候会有两个指针，指针一指向当前迁移的元素，指针二指向下一个要迁移的元素。两个线程A和B同时操作jdk7的HashMap，A线程准备迁移时，B线程迁移完成了，此时元素顺序已经颠倒。这是就会发生 a的下一个是b，b的下一个是a。

HashMap中的key是否可以为null

HashMap中key可以为null，其他Map不一定可以为null

HashMap的key有哪些要求

key对象，必须实现hashcode和equals
key不可被修改(不可变)，否则会出现查找不到数据的情况

HashTable的数组容量

默认为0，扩容规则为上一次数组容量+1为扩容后的数组大小。

未完待续