HashMap的底层原理-一文搞懂
1 HashMap的get与put方法的执行过程
HashMap用于存放键值对，用于非线程安全，其数据结构由数组、链表和红黑树构成。链表主要是为了解决哈希碰撞问题，而红黑树则是避免为链表长度过长而导致查询效率低的问题。HashMap数据结构如图1-27所示。
1）get方法的执行流程
(1)计算key的hash值，通过hash&(length-1)的方式计算key对应的数组下标。
(2)若首节点为null，则返回null。
(3)若首节点key与目标值相同，则直接返回key对应的value。
(4)若首节点key与目标值不同，且首节点的下一个节点为null，则返回null；否则判断首节点类型，首节点类型如果是链表，则遍历查找O(n)，如果是红黑树，则效率查找O(logn)。
2）put方法的执行流程
(1)如果数组为空就进行第一次扩容。
(2)计算key的hash值，通过hash & (length -1)的方式计算key对应的数组下标。
(3)如果数组下标处首节点为null，则直接插入。
(4)若首节点key与目标值相同，则直接覆盖，否则：
● 若首节点为红黑树节点类型，则在红黑树中插入键值对。
● 若首节点为链表节点类型，则遍历链表执行插入操作。如果链表的长度大于或等于8，那么需要将链表转化为红黑树。
(5)插入成功后，若键值对数量大于阈值则触发扩容。
2 key的hash值的计算过程
hash值的计算过程：(key == null) ? 0 : (h =key.hashCode()) ^ (h >>> 16)。
(1)计算hash值，int h = key.hashCode()。
(2)哈希值无符号右移16位与原哈希值做异或h^(h >>> 16)处理。
把高位与低位进行混合运算，提高低位的随机 性，降低碰撞概率。
3 HashMap是如何解决Hash冲突的
HashMap底层使用数组来存储数据，当添加键值对时，首先计算key的哈希值，然后通过hash &(length -1)的方式确定key在数组中的下标。但多个key经过hash &(length-1)计算后位置可能相同，也就是存在哈希冲突问题。HashMap使用拉链法来解决哈希冲突问题，即所有存在冲突的key组成一个单向链表，当链表长度大于8时转化为红黑树，以提高查询效率。
4 为什么链表转换为红黑树的阈值是8，而红黑树转换为链表的阈值却是6
一方面红黑树的查找效率为O(logn)，优于链表的O(n)，另一方面红黑树占用的内存空间大于链表，同时当键值对数量较少时链表的遍历查询与红黑树的搜索效率差异不大。综合空间和时间的考量，哈希冲突元素的个数达到某个阈值时红黑树和链表数据结构才会互相转化。HashMap的源码如下：
理想情况下，使用随机哈希码，在扩容阈值为0.75的情况下，桶中节点的数量遵循参数为0.5的泊松分布，即：
由此可知，链表长度为8的概率为0.00000006，此时树化。一方面遍历长度小于8的链表的时间效率尚可接受；另一方面每个桶的树化概率很小，节约了内存空间。红黑树退化为链表的阈值为6，中间留有空间，可以防止链表和红黑树之间频繁转换。
泊松分布(poisson distribution)是一种离散型概率分布，通常用于描述一个固定时间内事件发生次数的概率分布，如在一个小时内某个网站的访问次数、一天内某个交通路口的车辆通过次数等。
5 JDK8为什么使用红黑树
JDK7使用数组+链表来存储键值对，当数据量较多或哈希算法散列不均匀时，会导致链表长度很长，遍历查询的时间复杂为O(n)，如果将链表转换为红黑树，那么读写时间复杂度可降低为O(logn)。
6 HashMap扩容机制
首先解释几个与扩容有关的参数：
● capacity容量，即数组长度，默认为16。
● loadFactor加载因子，默认为0.75。
● threshold阈值。阈值=容量×加载因子，默认为12。
一般情况下，当HashMap中包含的键值对数量大于threshold时会触发扩容，容量扩大为原来的两倍。
JDK1.7版本，HashMap底层数据结构为数组和链表，扩容时新建数组，遍历旧数组的每个桶和桶中的每个键值对，将其rehash到扩容后的新数组，然后插入链表。
JDK1.8版本，底层数据结构为数组、链表和红黑树，当HashMap中键值对数量大于阈值、HashMap数组长度为0或升级成红黑树时，数组长度小于64都会触发扩容。扩容流程如下：
● 若数组索引位置对应的数据结构是链表，则生 成low和high两条链表，low链表插入新数组中的下标为[当前数组下标]，high链表插入新数组中的下标为[当前数组下标+旧数组长度]。
● 若数组索引位置对应的数据结构是红黑树，则生成low和high两棵红黑树，若树中元素个数小于或等于6则会退化成链表。low红黑树插入新数组中的下标为[当前数组下标]，high红黑树插入新数组中的下标为[当前数组下标+旧数组长度]。
同一个桶中的键值对属于low还是high，详细说明见“为什么HashMap是二倍扩容，容量总为2的n次幂”。
7 为什么HashMap是两倍扩容，容量总为2的n次幂
原因如下：
(1)在数组长度为2的幂次方时hash % length才等价于hash & (length-1)，定位key所在的哈希桶时位运算比求余更高效。
(2)避免破坏hash函数的散列均匀性。如果容量是2的n次幂，那么容量减1对应的二进制形式为***1111，key的hash值与它进行与运算时，结果完全取决于与key的哈希值进行的与运算。
举个例子，HashMap的容量是16，容量减1的二进制是1111，与不同key的hash值的与运算的结果如图1-28所示。
假如容量为10（非2的n次幂），容量减1的二进制是1001，与不同key的hash值进行与运算的结果如图1-29所示。
可以看出，当容量不是2的n次幂时，4个不同的哈希值的与运算得到的结果相同，发生了严重的哈希碰撞，这是因为容量减1对应的二进制低位存在0比特位。
(3)HashMap遵循两倍扩容，扩容后元素在新数组的下标为当前数组下标或者当前数组下标加旧数组长度，JDK1.8版本根据这个规律实现快速rehash。
举例说明，扩容前数组的容量为16，元素a和b在扩容前处于同一索引位置，如图1-30所示。、
扩容后的数组长度为32，新数组长度减1对应的二进制只比旧数组长度(oldCap)减1高位多了一个1(00011111和00001111)，如图1-31所示。
扩容前后，key的哈希值对数组长度求余，对比结果发现，同一个桶中的元素a和b在扩容后的新位置取决于新数组长度减1对应的二进制的最高位，即00010000，其十进制正巧为旧数组长度。总结一下，若(e.hash & oldCap) == 0，则扩容后元素在新数组的下标为当前数组下标；若(e.hash &oldCap ) != 0，则扩容后元素在新数组的下标为当前数组下标加旧数组长度。