HashMap常见问题

HashMap常见问题

原文链接：https://www.leahy.club/archives/java%E5%9F%BA%E7%A1%80hashmap%E5%B8%B8%E8%A7%81%E9%97%AE%E9%A2%98

HashMap定义：
HashMap是Java集合框架下的一个用来存储键值对的集合类。

底层数据结构：
在JDK1.7之前采用的是数组+单向链表的形式，存储数据的单元为Entry；在JDK1.8之后采用的是数组+单向链表/红黑树的形式，存储数据的单元为Node，目的是为了与红黑树中的TreeNode对应。

如何添加元素：
HashMap实现了put方法往集合中添加键值对，首先会计算K的hashcode值并对hashcode值进行与运算和相关的扰动计算得到其应该在数组中存储位置的索引。之后判断数组中该索引位置是否存在元素，如果不存在就直接将封装好的Node存储进去；如果存在元素，调用equals方法判断是否K相同，如果相同直接覆盖已有的K对应的V，如果K不相同，那么就在链表的头部进行插入。

如何扩容：
首先HashMap初始化的容量为16，还有一个默认的负载因子是0.75，根据这些可以计算出一个threshold为12.那么每次进行插入的时候会判断已经使用的位桶size是否超过12，超过12那么会进行扩容操作，每次扩容会扩容为原来的两倍。扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率。同时，如果单个链表的 长度超过8会转化成红黑树，如果红黑树长度小于6则退化成链表，这样是为了防止振荡的发生。同时转化成红黑树还需满足数组容量不小于64，如果数组容量小于64且遇到了需要链表转红黑树的情况，优先考虑进行扩容而不是转化为红黑树。至于为什么选择8作为临界值，据说根据泊松分布计算，hash碰撞8次的概率是极低的，不到百万分之一。 $p\left(k\right)=\frac{e^{-\lambda }\ast {\lambda }^k}{k!}$p(k)=k!e−λ∗λk​.

JDK1.7——>JDK1.8的改进：
改进主要是初始化时JDK1.7是直接初始化一个容量为16的数组；而JDK1.8是初始化时并不去初始化数组的容量，而是在真正添加元素的时候在进行初始化，调用resize方法。然后从JDK1.7的数组+链表变成了JDK1.8中的数组+链表+红黑树。

为什么从头插改为尾插：
HashMap在JDK1.7中采用头插法，在扩容时调用transfer会改变链表中原本的顺序，以致于在并发场景下，如果多个线程对链表进行同时操作会导致链表成环的问题；而JDK1.8采用尾插法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

为什么采用16作为初始的容量，且扩容也保证容量是2的幂次。
首先16是2的整数次幂，采用2的整数次幂的时候，Length-1得到的二进制数都是1。由于计算键值的hashcode之后会将其与容量进行按位与操作，这种情况下，计算得到的数组index的结果就是hashcode后几位的值，只要输入的hashcode本身分布均匀，hash算法的结果就是均匀的，从而避免因为容量大小导致hash碰撞的概率增大。同时计算hashcode的过程中还会将hashcode进行扰动计算，也进一步降低了碰撞的可能性。

友情链接：
https://www.cnblogs.com/tag6254/p/9416946.html
https://juejin.im/post/5dee6f54f265da33ba5a79c8
https://juejin.im/post/5ba457a25188255c7b168023（详细源码分析）