HashMap 的负载因子

在 Java 基础中，集合类是很关键的一块知识点，也是日常开发的时候经常会用到的。比如 List、Map 这些在代码中也是很常见的。

个人认为，关于 HashMap 的实现，JDK 的工程师其实是做了很多优化的，要说所有的 JDK 源码中，哪个类埋的彩蛋最多，那我想 HashMap 至少可以排前五。

也正是因为如此，很多细节都容易被忽视，今天我们就来关注其中一个问题，那就是：

为什么 HashMap 的负载因子设置成 0.75，而不是 1 也不是 0.5？****这背后到底有什么考虑？

大家千万不要小看这个问题，因为负载因子是 HashMap 中很重要的一个概念，也是高端面试的一个常考点。

1. 什么是 loadFactor

首先我们来介绍下什么是负载因子（loadFactor），如果读者对这部分已经有了解，那么可以直接跨过这一段。

我们知道，第一次创建 HashMap 的时候，就会指定其容量（如果未明确指定，默认是 16），那随着我们不断的向 HashMap 中 put 元素的时候，就有可能会超过其容量，那么就需要有一个扩容机制。

所谓扩容，就是扩大 HashMap 的容量：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

从代码中我们可以看到，在向 HashMap 中添加元素过程中，如果 元素个数（size）超过临界值（threshold） 的时候，就会进行自动扩容（resize），并且，在扩容之后，还需要对 HashMap 中原有元素进行 rehash，即将原来桶中的元素重新分配到新的桶中。

在 HashMap 中，临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。

loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，也就是说默认情况下，当 HashMap 中元素个数达到了容量的 3/4 的时候就会进行自动扩容。

2. 为什么要扩容

还记得前面我们说过，HashMap 在扩容到过程中不仅要对其容量进行扩充，还需要进行 rehash！所以，这个过程其实是很耗时的，并且 Map 中元素越多越耗时。

rehash 的过程相当于对其中所有的元素重新做一遍 hash，重新计算要分配到那个桶中。

那么，有没有人想过一个问题，既然这么麻烦，为啥要扩容？HashMap 不是一个数组链表吗？不扩容的话，也是可以无限存储的呀。为啥要扩容？

这其实和哈希碰撞有关！！

哈希碰撞：

我们知道，HashMap 其实是底层基于哈希函数实现的，但是哈希函数都有如下一个基本特性：根据同一哈希函数计算出的哈希值如果不同，那么输入值肯定也不同。但是，根据同一哈希函数计算出的哈希值如果相同，输入值不一定相同。

两个不同的输入值，根据同一哈希函数计算出的哈希值相同的现象叫做碰撞。

衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。

而为了解决哈希碰撞，有很多办法，其中比较常见的就是链地址法，这也是 HashMap 采用的方法。

HashMap 将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。

image

HashMap 基于链表的数组的数据结构实现的。

我们在向 HashMap 中 put 元素的时候，就需要先定位到是数组中的哪条链表，然后把这个元素挂在这个链表的后面。

当我们从 HashMap 中 get 元素的时候，也是需要定位到是数组中的哪条链表，然后再逐一遍历链表中的元素，直到查找到需要的元素为止。

但是，如果一个 HashMap 中冲突太高，那么数组的链表就会退化为链表。这时候查询速度会大大降低。

image

所以，为了保证 HashMap 的读取的速度，我们需要想办法尽量保证 HashMap 的冲突不要太高。

扩容避免哈希碰撞

那么如何能有效的避免哈希碰撞呢？

我们先反向思维一下，你认为什么情况会导致 HashMap 的哈希碰撞比较多？

无外乎两种情况：

1、容量太小。容量小，碰撞的概率就高了。狼多肉少，就会发生争抢。

2、hash 算法不够好。算法不合理，就可能都分到同一个或几个桶中。分配不均，也会发生争抢。

所以，解决 HashMap 中的哈希碰撞也是从这两方面入手。

这两点在 HashMap 中都有很好的体现。两种方法相结合，在合适的时候扩大数组容量，再通过一个合适的 hash 算法计算元素分配到哪个数组中，就可以大大的减少冲突的概率，就能避免查询效率低下的问题。

3. 为什么默认 loadFactor 是 0.75

解释了这么多，我们终于回归到了标题上的问题。

至此，我们知道了 loadFactor 是 HashMap 中的一个重要概念，他表示这个 HashMap 最大的满的程度。

为了避免哈希碰撞，HashMap 需要在合适的时候进行扩容。那就是当其中的元素个数达到临界值的时候，而这个临界值前面说过和 loadFactor 有关，换句话说，设置一个合理的 loadFactor，可以有效的避免哈希冲突。

那么，到底 loadFactor 设置成多少算合适呢？

这个值现在在 JDK 的源码中是 0.75：

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

那么，为什么选择 0.75 呢？背后有什么考虑？为什么不是 1，不是 0.8？不是 0.5，而是 0.75 呢？

在 JDK 的官方文档中，有这样一段描述描述：

As a general rule, the default load factor (.75) offers a good tradeoff 
between time and space costs. Higher values decrease the space overhead 
but increase the lookup cost (reflected in most of the operations of the 
HashMap class, including get and put).

大概意思是：一般来说，默认的负载因子 (0.75) 在时间和空间成本之间提供了很好的权衡。更高的值减少了空间开销，但增加了查找成本(反映在 HashMap 类的大多数操作中，包括 get 和 put)。

试想一下，如果我们把负载因子设置成 1，容量使用默认初始值 16，那么表示一个 HashMap 需要在 "满了" 之后才会进行扩容。

那么在 HashMap 中，最好的情况是这 16 个元素通过 hash 算法之后分别落到了 16 个不同的桶中，否则就必然发生哈希碰撞。而且随着元素越多，哈希碰撞的概率越大，查找速度也会越低。

4. 0.75 的数学依据和必然性

理论上我们认为负载因子不能太大，不然会导致大量的哈希冲突，也不能太小，那样会浪费空间。

通过一个数学推理 log(2)/log(s/(s - 1)) ，当 s 趋于无穷大时，如果增加的键的数量使 P(0) = 0.5，那么 n/s 很快趋近于 log(2)，测算出这个数值在 log(2)（即：0.7 左右）时是比较合理的。

当然，这个数学计算方法，并不是在 Java 的官方文档中体现的，而是查询了一些资料习得，所以也无从考证，只做参考了。

那么，为什么最终选定了 0.75 呢？

还记得前面我们提到过一个公式吗，就是：临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）。

根据 HashMap 的扩容机制，它会保证 capacity 的值永远都是 2 的幂；

那么，为了保证负载因子（loadFactor） * 容量（capacity）的结果是一个整数，这个值是 0.75(3/4) 比较合理，因为这个数和任何 2 的幂乘积结果都是整数。

5. 总结（非常重要）

HashMap 是一种 K-V 结构，为了提升其查询及插入的速度，底层采用了链表的数组这种数据结构实现的。

但是因为在计算元素所在的位置的时候，需要使用 hash 算法，而 HashMap 采用的 hash 算法就是链地址法。这种方法有两个极端。

如果 HashMap 中哈希冲突概率高，那么 HashMap 就会退化成链表（不是真的退化，而是操作上像是直接操作链表），而我们知道，链表最大的缺点就是查询速度比较慢，他需要从表头开始逐一遍历。

所以，为了避免 HashMap 发生大量的哈希冲突，所以需要在适当的时候对其进行扩容。

而扩容的条件是元素个数达到临界值时。

HashMap 中临界值的计算方法：

临界值（threshold） = 负载因子（loadFactor） * 容量（capacity）

其中负载因子表示一个数组可以达到的最大的满的程度。这个值不宜太大，也不宜太小。

loadFactor 太大，比如等于 1，那么就会有很高的哈希冲突的概率，会大大降低查询速度。

loadFactor 太小，比如等于 0.5，那么频繁扩容没，就会大大浪费空间。

所以，这个值需要介于 0.5 和 1 之间。根据数学公式推算。这个值在 log(2) 的时候比较合理。

另外，为了提升扩容效率，HashMap 的容量（capacity）有一个固定的要求，那就是一定是 2 的幂。

所以，如果 loadFactor 是 3/4 的话，那么和 capacity 的乘积结果就可以是一个整数。

最后，一般情况下，我们不建议修改 loadFactor 的值，除非特殊原因。