阿里面试官：HashMap中8和6的关系（2）
那么概率统计学的知识与Java 8的HashMap有着怎样的关系呢？本文将从以下几点开始逐步深入分析HashMap背后的设计思路。
- HashMap的基本原理
- 哈希碰撞的概念
- 常见的处理哈希碰撞的算法
- Java 7处理哈希碰撞的方法
- Java 8处理哈希碰撞的方法较Java7的改进
- Java 8中为什么选择在链表长度到达8时将链表转红黑树
- Java 8中为什么选择在红黑树结点到达6时将红黑树退化为链表
引言 —— 奇葩的大厂面试题
为什么Java 8的HashMap选择在8的时候将链表转为红黑树，在红黑树结点到达6的时候将红黑树退化为链表？为什么选择8和6这两个数组？难道老外跟我们中国人一样，喜欢吉利数字吗？
emmmmm。。。。。
1 HashMap的基本原理
HashMap是一种在平均情况下可以达到O(1)时间复杂度的一种高效的数据结构。其底层的实现逻辑只要依靠数据和链表（Java 8中引入了红黑树）。
HashMap逻辑示意图如下。
【注】
- 上图中纵向的编号0~15的元素其实是在一个长度的16的数组中。一般称这个数组为桶数组。数组中的每个位置称为桶或者槽。
- 横向的元素是存放在桶中的元素。最优情况下，HashMap的每个桶中只会存放一个元素。
正是因为数组具有按下标随机查找，且查找的时间复杂度为O(1)的特性，因此存储在HashMap中的元素，只要按照一定的机制，保证能够快速找到其中的元素存储于HashMap桶数组中的位置（数组的下标）即可实现O(1)实现复杂度的查找。
2 哈希碰撞的概念
所谓哈希（hash），就是将不同的输入映射成独一无二的、固定长度的值（又称"哈希值"）。它是最常见的软件运算之一。
通俗的说，哈希碰撞就是有2个或者多个对象存放在了HashMap桶数组的同一个位置上。
- 如：一个容量为16的HashMap要存储17个元素，因为容量的限制，无法保证每个槽位上只存储1个元素，那么必然会出现2个或者多个对象要放在桶数组的同一个位置上。
- 也有可能出现，要存储的元素个数小于HashMap容量，但是经过计算后，两个元素存储在HashMap桶数组相同位置的情况。
上图所示的John Smith和Sandra Dee这两个元素同时存储在哈希桶数组的第02个位置上，此时John Smith和Sandra Dee这两个元素发生哈希碰撞。
3 常见的处理哈希碰撞的算法
1.开放地址法
开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次发生哈希碰撞后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。
前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。
当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。
类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
2.再哈希法
当发生冲突时，使用第2个、第3个等哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止。
3.链地址法/拉链法
将所有关键字为同义词的记录存储在同一线性链表中。如下：
4.建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
4 Java 7处理哈希碰撞的方法
Java 7 HashMap采用的链表法的方式，链表是单向链表。形成单链表的核心代码如下:
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}上面方法的代码很简单，但其中包含了一个设计：
系统总是将新添加的 Entry 对象放入 table 数组的 bucket Index 索引处——如果 bucket Index 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链)，如果 bucketIndex 索引处没有 Entry 对象，也就是上面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。
如果两个 Entry的 key的 hashCode()返回值相同，那它们的存储位置相同。如果这两个 Entry的 key通过equals比较返回 true，新添加 Entry的 value将覆盖集合中原有 Entry的 value，但key不会覆盖。如果这两个 Entry的 key通过equals比较返回 false，新添加的 Entry将与集合中原有 Entry形成 Entry链，而且新添加的 Entry位于 Entry链的头部。
HashMap里面没有出现hash冲突时，没有形成单链表时，hashmap查找元素很快,get()方法能够直接定位到元素，但是出现单链表后，单个bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中)，那系统必须循环到最后才能找到该元素。
通过上面可知如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。也就是说我们是通过链表的方式来解决这个Hash碰撞问题的。
5 Java 8处理哈希碰撞的方法较Java7的改进
Java 7：随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。
Java 8对此进行了优化！它是一个log的曲线，因此它的性能要好上好几个数量级。尽管有严重的哈希碰撞，已是最坏的情况了，但这个同样的基准测试在JDK8中的时间复杂度是O(logn)，单独来看JDK 8的曲线的话会更清楚，这是一个对数线性分布。
如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的Treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。
6 Java 8中为什么选择在链表长度到达8时将链表转红黑树
Java 8的HashMap源码中有这样一个属性：
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;TREEIFY_THRESHOLD属性的含义：在某个桶中链表长度到达8时将链表转化为红黑树。
面试官
为什么Java 8的HashMap选择链表长度为8时将链表转为红黑树？为什么不是9或者7？
关于上面这个问题的答案要从JDK的源码中查找：
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* ( http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million源码的注释中写到（理想情况下，在随机哈希码和默认大小调整阈值为 0.75 的情况下,存储桶中元素个数出现的频率遵循泊松分布（泊松分布的内容请点击这里）,平均参数为 0.5，有关 k 值下,随机事件出现频率的计算公式为 (exp(-0.5) * pow(0.5, k) /factorial(k))）。
根据泊松分布概率质量函数,一个哈希桶达到 9 个元素的概率小于一千万分之一. 选定阈值为 8 猜测是基于泊松分布和类似与 DEFAULT_LOAD_FACTOR 一样，基于一些空间和效率之间取的一个平均值。
7 Java 8中为什么选择在红黑树结点到达6时将红黑树退化为链表
Java 8的HashMap中有另一个属性值得注意：
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;UNTREEIFY_THRESHOLD的含义是：当同一个桶内红黑树的大小减小到6时，将红黑树退化为链表。
面试官
为什么Java 8的HashMap选择红黑树长度为6时将红黑树退化为链表？为什么选择TREEIFY_THRESHOLD-1=7的时候退化为链表？
Java 8的HashMap中的部分源码如下。
#若 loHead 的节点数量小于,则红黑树退化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null)
loHead.treeify(tab);
}
#若链表数量大于或等于(树化阈值-1)则退化,
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 是因为 binCount 是 0 为第一个节点.
treeifyBin(tab, hash);由代码我们得知，树化和树退化方法的判断都是闭区间，如果都是 8,则可能陷入(树化<=>树退化)的死循环中. 若是 7,则当极端情况下(频繁插入和删除的都是同一个哈希桶)对一个链表长度为 8 的的哈希桶进行频繁的删除和插入，同样也会导致频繁的树化<=>非树化。
由此,选定 6 的原因一部分是需要低于 8，但过于接近也会导致频繁的结构变化。
那为什么不是 6 以下呢？我也是这么想的。查看 TreeNode 和 Node 的源码
//树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
//链表节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;由源码可知,TreeNode 光是属性数就多于 Node, 再看Oracle 文档中变量的初始值,引用类型初始为 NULL。引用类型内存占为：32 位系统 4 字节,64 位系统 8 字节。
故不选定低于 6 的退化阈值一方面是因为红黑树不一定在元素较少时效率更好（事实上由 MIN_TREEIFY_CAPACITY=64 参数可知，只有容量大于 64 时才会开启树化）；另一方面则是红黑树相比链表占用了更多的引用。