阿里面试官：HashMap中8和6的关系（2）

那么概率统计学的知识与Java 8的HashMap有着怎样的关系呢？本文将从以下几点开始逐步深入分析HashMap背后的设计思路。

1. HashMap的基本原理
2. 哈希碰撞的概念
3. 常见的处理哈希碰撞的算法
4. Java 7处理哈希碰撞的方法
5. Java 8处理哈希碰撞的方法较Java7的改进
6. Java 8中为什么选择在链表长度到达8时将链表转红黑树
7. 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 时才会开启树化）；另一方面则是红黑树相比链表占用了更多的引用。