转载

阿里P7岗位面试，面试官问我：为什么HashMap底层树化标准的元素个数是8

前言

先声明一下，本文有点标题党了，像我这样的菜鸡何德何能去面试阿里的P7岗啊，不过，这确实是阿里p7级岗位的面试题，当然，参加面试的人不是我，而是我部门的一个大佬。他把自己的面试经验分享给了我，也让我间接体会下阿里级别的面试难度，这样算起来，我也勉强算是经历面试过阿里P7的岗位的人吧，顿时感觉信心暴涨。

一般的面试题

对于HashMap，我们再熟悉不过了，日常开发最常用的Java集合类就是它了，而且面试的时候对于HashMap知识点基本是必问的，就拿我之前的面试经历来看，问的最多的无非是这么几个：

1、HashMap的底层存储结构是怎样的啊？

2、线程安全吗？为什么不安全？

3、1.7和1.8版本的HashMap有什么区别？1.7的有什么隐患，什么原因导致的？

4、hashcode是唯一的吗？插入元素的时候怎么比较的？

5、跟HashTable，ConcurrentHashMap有什么区别？

对于这些问题，如果你看过一些博客，或者大概的浏览过源码的话，基本都能答出来，我之前参加过很多面试，也很少在HashMap这块失过手。

事实证明，我还是年轻了点（怎么说也是90后的）。有时候，你答的好不是因为你懂得多，而是人家问的不深，如果你没有对源码做深入的了解和思考的话，别人稍微换个角度考察，你也许就会犯难了。

就好像标题上的题目，为什么HashMap链表树化的标准是8个？说实话，尽管我之前也知道是树化的阈值是8，但是为什么是这个数目我还真没仔细的思考过，借着这个机会，我也重新梳理了遍HashMap的源码，本文也算是一些新的思考点的总结吧。

HashMap的基本知识点

HashMap可以说是Java项目里最常用的集合类了，作为一种典型的K-V存储的数据结构，它的底层是由数组 - 链表组成，当添加新元素时，它会根据元素的hash值找到对应的"桶"，也就是HashMap源码中 Node<K, V> 里的元素，并插入到对应位置的链表中，链表元素个数过长时会转化为红黑树(JDK1.8后的版本)，

为什么要转成红黑树呢？

我们都知道，链表取元素是从头结点一直遍历到对应的结点，这个过程的复杂度是O(N) ，而红黑树基于二叉树的结构，查找元素的复杂度为O(logN) ，所以，当元素个数过多时，用红黑树存储可以提高搜索的效率。

既然红黑树的效率高，那怎么不一开始就用红黑树存储呢？

这其实是基于空间和时间平衡的考虑，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.  
复制代码

看注释里的前面四行就不难理解，单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，这个足够多的标准就是由 TREEIFY_THRESHOLD 的值（默认值8）决定的。而当桶中节点数由于移除或者 resize (扩容) 变少后，红黑树会转变为普通的链表，这个阈值是 UNTREEIFY_THRESHOLD（默认值6）。

/**
* 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;

/**
* 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;
复制代码

看到这里就不难明白了，红黑树虽然查询效率比链表高，但是结点占用的空间大，只有达到一定的数目才有树化的意义，这是 基于时间和空间的平衡考虑 。

为什么树化标准是8个

至于为什么树化标准的数量是8个，在源码中，上面那段笔记后面还有一段较长的注释，我们可以从那一段注释中找到答案，原文是这样：

* 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
复制代码

大概意思就是：如果 hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了1-8长度的具体命中概率，当长度为8的时候，概率概率仅为0.00000006，这么小的概率，HashMap的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据，你会存上千万个数据到HashMap中吗？

当然，这是理想的算法，但不妨某些用户使用HashMap过程导致hashCode分布离散很差的场景，这个时候再转换为红黑树就是一种很好的退让策略。

至于什么情况下会导致这样的场景，大家可以自己思考或网上找一下答案，我就不再赘述了，省点力气。

别，咱好好说话，我接着写还不行吗，不容易啊，被你们白嫖就算了，还要被冠上渣男的称号，我图啥呢？

首先说明一下，在HashMap中，决定某个对象落在哪一个 “桶“，是由该对象的 hashCode 决定的，JDK无法阻止用户实现自己的哈希算法，如果用户重写了 hashCode ，并且算法实现比较差的话，就很可能会使HashMap的链表变得很长，就比如这样：

public class HashMapTest {
    public static void main(String[] args) {
        Map<User, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put(new User("鄙人薛某" + i), i);
        }
    }

    static class User{

        private String name;

        public User(String name) {
            this.name = name;
        }

        @Override
        public int hashCode() {
            return 1;
        }
    }
}
复制代码

我们设计了一个hashCode永远为1的类 User ，这样一来存储到HashMap的所有User对象都会存放到同一个“桶”里，这样一来查询效率无疑会非常的低下，而这也是HashMap设计链表转红黑树的原因，可以有效防止用户自己实现了不好的哈希算法时导致链表过长的情况。

hash方法

说到哈希算法，我们再来扩充一个知识点，这也是我觉得HashMap中非常牛逼的设计之一。

在HashMap的源码中，存储对象hashCode的计算是由 hash() 方法决定的， hash() 是HashMap 中的核心函数，在存储数据时，将key传入中进行运算，得出key的哈希值，通过这个哈希值运算才能获取key应该放置在 “桶” 的哪个位置，下面是方法的源码：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

从代码中可以看出，传入key之后，hash() 会获取key的hashCode进行无符号右移 16 位，然后进行按位异或，并把运算后的值返回，这个值就是key的哈希值。这样运算是为了减少碰撞冲突，因为大部分元素的hashCode在低位是相同的，不做处理的话很容易造成冲突。

除了做16位位移的处理，在添加元素的方法中，HashMap还把该hash值与 table.length - 1 ，也就是“桶”数组的大小做与运算，得到的结果就是对应的“桶”数组的下标，从而找到该元素所属的链表。源码里这样的：

// n的值是table.length
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
复制代码

当查找不到对应的索引时，就会新建一个新的结点作为链表的头结点。那么这里为什么要用 i = (n - 1) & hash 作为索引运算呢？

这其实是一种优化手段，由于数组的大小永远是一个2次幂，在扩容之后，一个元素的新索引要么是在原位置，要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算，之前提到过&运算只会关注n – 1（n =数组长度）的有效位，当扩容之后，n的有效位相比之前会多增加一位（n会变成之前的二倍，所以确保数组长度永远是2次幂很重要），然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置，如果是0，那么索引没有发生变化，如果是1，索引就为原索引加上扩容前的容量。

用一张效果图来表示就是：

通过位运算，在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开，达到较好的分布离散效果，不得不感叹，设计功底真是太牛逼了，几句看似简单的代码里面居然包含了这么多的学问。

为什么退化为链表的阈值是6

上面说到，当链表长度达到阈值8的时候会转为红黑树，但是红黑树退化为链表的阈值却是6，为什么不是小于8就退化呢？比如说7的时候就退化，偏偏要小于或等于6？

主要是一个过渡，避免链表和红黑树之间频繁的转换。如果阈值是7的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，所以阈值才不设置的那么临界。

最后

HashMap的知识点还有很多，这里我也强烈大家去多看几遍源码，不光是为了应付面试，也是对自己能如何更好的使用HashMap能有更清晰的认知，毕竟它实在是太常见了，用的不好很容易就产生bug。而且，我觉得JDK的源码真的有很多值得我们开发者深入研究的地方，就比如这个HashMap，它的真实代码量不算多，但非常的高效，最重要的是，它每个版本都在不停的优化，每一行代码都是精雕细琢，看源码的时候我也一直在心里感叹，我要是也能写出那么牛逼的代码，那进阿里什么的还算是事吗？