在Java基础中，集合类是一个重点知识点，在日常开发中经常会用到。比如List和Map在代码中也很常见。在我看来，关于HashMap的实现，JDK工程师其实做了很多优化。如果要说所有JDK源码中哪个类埋的蛋最多，那我觉得HashMap至少可以排进前五。也正是因为如此，很多细节很容易被忽略。今天我们将重点讨论其中一个问题，即：为什么HashMap的负载因子设置为0.75，而不是1或0.5？这背后有哪些考虑？大家不要小看这道题，因为负载因子是HashMap中非常重要的一个概念，也是高端面试的一个常见考点。另外这个值得设置，有的人会用错。比如我前几天的文章《阿里巴巴Java开发手册建议创建HashMap时设置初始化容量，但是多少合适呢?》，有读者回复：既然有人会试图修改负载因子，那改成1对不对？合适的？为什么HashMap不使用1作为负载因子的默认值？什么是负载因子？首先介绍一下什么是负载因子（loadFactor）。如果读者已经了解这一部分，可以直接跳过这一部分。我们知道在第一次创建HashMap的时候，会指定它的容量（如果不指定，默认是16，看看为什么HashMap的默认容量是16？），然后随着我们不断往HashMap中放入元素有时，它可能会超出其容量，因此需要扩展机制。所谓扩容，就是对HashMap进行扩容：length);hash=(null!=key)?hash(key):0;bucketIndex=indexFor(hash,table.length);}createEntry(hash,key,value,bucketIndex);}从代码中我们可以看出在HashMap中添加元素的过程中，如果元素个数（size）超过临界值（threshold），会自动扩容（resize），扩容后需要对HashMap中原有元素重新hash，也就是将原bucket中的元素重新赋值到新的bucket中。在HashMap中，阈值（threshold）=负载因子（loadFactor）*容量（capacity）。loadFactor是加载因子，表示HashMap有多满。默认值为0.75f。也就是说，默认情况下，当HashMap中的元素个数达到容量的3/4时，会自动扩容。（具体可以看HashMap中那些傻傻分不清的概念。）为什么要扩容？还记得我们之前说过的，HashMap在扩容过程中不仅需要扩容，还需要rehash！所以，这个过程其实是非常耗时的，而且Map中的元素越多，耗时也就越多。rehash的过程相当于把里面的所有元素都重新hash，重新计算应该分配到那个bucket。那么，有没有人想过一个问题，既然这么麻烦，为什么要扩容呢？HashMap不是数组链表吗？如果不展开，也可以无限存储。为什么要扩张？这实际上与哈希冲突有关。哈希碰撞我们知道，HashMap在底层其实是基于哈希函数实现的，但是哈希函数有以下几个基本特点：如果根据同一个哈希函数计算出的哈希值不同，那么输入的值也必须不同。但是，如果同一个哈希函数计算出的哈希值相同，输入的值不一定相同。两个不同的输入值根据同一个哈希函数计算出的哈希值相同的现象称为碰撞。衡量哈希函数好坏的一个重要指标是碰撞概率和碰撞解决方案。为了解决哈希冲突，有很多种方法，比较常见的是链地址法，这也是HashMap采用的方法。具体可以看全网最透彻的一篇分析Map中hash()的文章，其他的没有了。HashMap结合了数组和链表，充分利用了两者，我们可以理解为链表的数组。HashMap是基于链表数组的数据结构实现的。当我们往HashMap中放入一个元素时，首先需要定位到数组中是在哪个链表中，然后把这个元素挂在链表后面。我们在从HashMap中获取元素的时候，还需要定位到数组中的是哪个链表，然后将链表中的元素一个一个遍历，直到找到需要的元素。但是，如果HashMap中的冲突太高，那么数组的链表就会退化为链表。这时候查询速度会大大降低。所以，为了保证HashMap的读取速度，我们需要想办法保证HashMap的冲突不太高。扩容避免哈希冲突那么如何有效避免哈希冲突呢？让我们先回顾一下。你认为什么会导致HashMap中更多的哈希冲突？有两种情况：1、容量太小。容量越小，碰撞概率越高。狼多肉少，就会有竞争。2.哈希算法不够好。如果算法不合理，它们可能都被分配到同一个或几个桶中。如果分配不均，也会出现竞争。因此，解决HashMap中的哈希冲突也是从这两个方面入手。这两点在HashMap中都有很好的体现。结合这两种方法，在适当的时候扩充数组的容量，然后通过合适的哈希算法计算出元素分配到哪个数组，可以大大降低发生冲突的概率。可以避免查询效率低下的问题。为什么loadFactor默认为0.75至此，我们知道loadFactor是HashMap中的一个重要概念，它表示这个HashMap的最大丰满度。为了避免哈希冲突，HashMap需要适时扩容。也就是当里面的元素个数达到一个临界值的时候，这个临界值跟前面说的loadFactor有关。也就是说，设置合理的loadFactor可以有效避免hash冲突。那么，正确的loadFactor设置是多少？在JDK源代码中这个值现在是0.75：/***构造函数中没有指定时使用的loadfactor.*/staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;那么，为什么选择0.75？其背后有何考量？为什么不是1，不是0.8？不是0.5，而是0.75？在JDK的官方文档中，有这样的描述：作为一般规则，默认的加载因子(.75)在时间和空间成本之间提供了一个很好的折衷。较高的值减少了空间开销但增加了查找成本（反映在HashMap类的大多数操作中，包括get和put）。大概意思是：一般来说，默认的负载因子（0.75）提供了时间和空间成本之间的一个很好的平衡。较高的值减少了空间开销但增加了查找成本（反映在HashMap类的大多数操作中，包括get和put）。试想一下，如果我们将负载因子设置为1，容量使用默认的初始值16，这意味着一个HashMap在“满”之前不会扩容。那么在HashMap中，最好的情况就是这16个元素经过hash算法后落入16个不同的桶中，否则难免会发生hash碰撞。并且随着元素数量的增加，哈希碰撞的概率增加，搜索速度会降低。0.75的数学基础另外，我们可以用一种数学思维来计算这个值的合适值。我们假设桶为空和非空的概率为0.5，我们用s表示容量，n表示添加元素的个数。让s表示添加的键的大小和n个键的数量。根据二项式定理，桶为空的概率为：P(0)=C(n,0)*(1/s)^0*(1-1/s)^(n-0)因此，如果桶中的元素个数小于下面的值，桶可能为空：log(2)/log(s/(s-1))当s趋于无穷大时，如果增加key的个数使P(0)=0.5，然后n/s迅速接近log(2):log(2)~0.693...所以，合理的值大约是0.7。当然，这种数学计算方式并没有体现在Java官方文档中，有没有这样的考虑我们也无从考证，就像我们不知道鲁迅写文章时是怎么想的一样，只能推测。这个推测来自StackOverflow中0.75的必然因素（https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap）理论上，我们认为loadfactor不能太大，否则会导致大量的hash碰撞，也不能太小，浪费空间。通过数学推理，计算出这个值在0.7左右比较合理。那么，为什么最终选择了0.75呢？还记得我们前面提到的公式吗，就是threshold=loadFactor*capacity。我们在《为啥HashMap的默认容量是16?》中介绍过，根据HashMap的扩容机制，会保证capacity的值永远是2的幂。那么，为了保证负载因子（loadFactor）*capacity（capacity）是一个整数，这个值是0.75（3/4），比较合理，因为这个数和2的任意次方的乘积都是整数。总结HashMap是一个K-V结构。为了提高其查询和插入的速度，底层采用链表数组的数据结构来实现。但是因为在计算元素位置的时候需要用到hash算法，而HashMap使用的hash算法是链地址法。这种方法有两个极端。如果HashMap中的hash碰撞概率很高，那么HashMap就会退化为链表（不是真的退化，而是操作起来就像直接操作链表一样），而我们知道链表最大的缺点就是查询速度比较慢。表头开始逐一遍历。因此，为了避免HashMap中出现大量的哈希冲突，需要适时对其进行扩容。展开的条件是当元素个数达到临界值时。HashMap中临界值的计算方法：阈值（threshold）=负载因子（loadFactor）*容量（capacity），其中负载因子表示一个数组所能达到的最大充满度。这个值既不能太大也不能太小。如果loadFactor太大，比如等于1，那么hash碰撞的概率会很大，会大大降低查询速度。如果loadFactor太小，比如等于0.5，那么频繁扩容会浪费很多空间。所以，这个值需要在0.5到1之间。根据数学公式计算。log(2)时这个值比较合理。另外，为了提高扩容效率，HashMap的容量有一个固定的要求，就是必须是2的幂。所以如果loadFactor是3/4，那么就是容量与容量的乘积可以是整数。因此，一般情况下，除非有特殊原因，否则我们不建议修改loadFactor的值。比如我明明知道我的Map只存5kv，永远不会变，所以可以考虑指定loadFactor。但实际上，我不推荐它。我们可以通过指定容量来实现这一点。具体可以参考阿里巴巴Java开发手册，建议在创建HashMap时设置初始容量，但是设置多少合适呢？
