有很多东西之前在学的时候没怎么注意，笔者也是在重温HashMap的时候发现有很多可以去细究的问题，最终是会回归于数学的，如HashMap的加载因子为什么是0.75？

  HashMap的底层是哈希表，是存储键值对的结构类型，它需要通过一定的计算才能确定数据在哈希表中的存储位置：

  一般的数据结构，不是查询快就是插入快，HashMap就是一个插入慢、查询快的数据结构。

  但这种数据结构易产生两种问题：① 如果空间利用率高，那么经过的哈希算法计算存储位置的时候，会发现很多存储位置已经有数据了（哈希冲突）；② 如果为了尽最大可能避免发生哈希冲突，增大数组容量，就会导致空间利用率不高。

  加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。

  冲突的机会越大，说明需要查找的数据还一定要通过另一个途径查找，这样查找的成本就越高。因此，必须在“冲突的机会”与“空间利用率”之间，寻找一种平衡与折衷。

  H(key)为哈希函数，m为哈希表表长，di为增量序列，i为已发生冲突的次数。其中，开放定址法根据步长不同可大致分为3种：

  简单地说，就是以当前冲突位置为起点，步长为1循环查找，直到找到一个空的位置，如果循环完了都占不到位置，就说明容器已经满了。举个栗子，就像你在饭点去街上吃饭，挨家去看是否有位置一样。

  相对于线性探查法，这就等于的步长为di = i2来循环查找，直到找到空的位置。以上面那个例子来看，现在你不是挨家去看有没有位置了，而是拿手机算去第i2家店，然后去问这家店有没有位置。

  这个就是取随机数来作为步长。还是用上面的例子，这次就是完全按心情去选一家店问有没有位置了。

  这种方法建立起来的哈希表，当冲突多的时候数据容易堆集在一起，这时候对查找不友好；

  删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不可以真正删除结点；

  RHi()函数是不同于H()的哈希函数，用于同义词发生地址冲突时，计算出另一个哈希函数地址，直到不发生冲突位置。这种方法不容易产生堆集，但是会增加计算时间。

  假设哈希函数的值域为[0, m-1]，设向量HashTable[0,…,m-1]为基本表，每个分量存放一个记录，另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录，若发生冲突，不管他们哈希函数得到的哈希地址是什么，都填入溢出表。

  将冲突位置的元素构造成链表。在添加数据的时候，如果哈希地址与哈希表上的元素冲突，就放在这一个位置的链表上。

  处理冲突的方式简单，且无堆集现象，非同义词绝不会发生冲突，因此平均查找长度较短；

  由于拉链法中各链表上的结点空间是动态申请的，所以它更适合造表前无法确定表长的情况；

  从HashMap的底层结构中我们大家可以看到，HashMap采用是数组+链表/红黑树的组合来作为底层结构，也就是开放地址法+链地址法的方式来实现HashMap。

  从上文我们大家都知道，HashMap的底层其实也是哈希表（散列表），而解决冲突的方式是链地址法。HashMap的初始容量大小默认是16，为减少冲突发生的概率，当HashMap的数组长度到达一个临界值的时候，就会触发扩容，把所有元素rehash之后再放在扩容后的容器中，这是一个相当耗时的操作。

  那么为什么选择了0.75作为HashMap的加载因子呢？这个跟一个统计学里很重要的原理——泊松分布有关。

  泊松分布是统计学和概率学常见的离散概率分布，适用于描述单位时间内随机事件发生的次数的概率分布。有兴趣的读者可以了解一下或者阮一峰老师的这篇文章：泊松分布和指数分布：10分钟教程[1]

  等号的左边，P 表示概率，N表示某种函数关系，t 表示时间，n 表示数量。等号的右边，λ 表示事件的频率。

  在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为0.75的情况下，节点出现在频率在Hash桶（表）中遵循参数平均为0.5的泊松分布。忽略方差，即X = λt，P(λt = k)，其中λt = 0.5的情况，按公式：

  计算结果如上述的列表所示，当一个bin中的链表长度达到8个元素的时候，概率为0.00000006，几乎是一个不可能事件。

  所以我们大家可以知道，其实常数0.5是作为参数代入泊松分布来计算的，而加载因子0.75是作为一个条件，当HashMap长度为length/size ≥ 0.75时就扩容，在这个条件下，冲突后的拉链长度和概率结果为：

  HashMap中除了哈希算法之外，有两个参数影响了性能：初始容量和加载因子。初始容量是哈希表在创建时的容量，加载因子是哈希表在其容量自动扩容之前能够达到多满的一种度量。

  对于开放定址法，加载因子是很重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照指数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了加载因子为0.75，超过此值将resize散列表。

  在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少扩容rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，以便减少扩容操作。

  选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。

  公众号“Java精选”所发表内容标注明确来源的，版权归原出处所有（无法查证版权的或者未标注明确出处的均来自互联网，系转载，转载的目的是传递更加多信息，版权属于原作者。如有侵权，请联系，笔者会第一时间删除处理！

  最近有很多人问，有没有读者交流群！加入方式很简单，公众号Java精选，回复“加群”，即可入群！