当前位置 > 首页 > 国际新闻 > 正文

我说我了解集合类,面试官竟然问我为啥HashMap的负载因子不设置成1!?
  • 发布时间:2020-03-08
  • www.sykntwztd.com
  • 在Java基础中,集合类是一个关键的知识点,并且经常在日常开发中使用。例如,列表和映射在代码中也很常见。

    就个人而言,关于HashMap的实现,JDK工程师实际上已经做了很多优化。要说哪种类型的JDK源代码埋藏了最多的鸡蛋,我认为HashMap至少可以排在前五位。

    也正因为如此,许多细节容易被忽略。今天我们将集中讨论其中一个,那就是:

    为什么哈希映射的负载因子设置为0.75而不是1或0.5?这背后的考虑是什么?

    人们永远不应该低估这个问题,因为负载因子是HashMap中一个非常重要的概念,也是高端面试的一个常见测试站点。

    此外,这是值得设置的,有些人会使用不当。例如,在我几天前的《阿里巴巴Java开发手册建议创建HashMap时设置初始化容量,但是多少合适呢?》文章中,一些读者这样回答:

    由于有些人会试图修改负载系数,将其改为1合适吗?为什么HashMap不使用1作为负载因子的默认值?

    什么是负载因子

    首先,让我们介绍什么是负载因子。如果读者已经知道这一部分,他们可以直接跳过这一段。

    我们知道当第一次创建HashMap时,它的容量将被指定(如果设置没有显示,默认值是16。关于细节,为什么HashMap 16的默认容量是?),那么当我们继续将元素放入HashMap时,它可能会超出它的容量,所以需要一个扩展机制。

    所谓扩展就是扩展HashMap :的容量

    从代码中我们可以看到,在向HashMap添加元素的过程中,如果需要的话,它会自动扩展(调整大小),扩展之后,HashMap中的原始元素需要被重新散列,即原始通信中的元素会被重新分配到新的桶中。

    在哈希映射中,阈值)=负载因子)*容量。

    loadFactor是一个负载因子,它指示哈希表的完整程度。默认值为0.75f,即默认情况下,当哈希映射中的元素数量达到容量的3/4时,将进行自动扩展。(在HashMap中遇到那些没有被愚蠢明确分开的概念)

    你为什么要扩展?

    请记住,我们之前说过HashMap不仅需要扩展其容量,还需要在扩展过程中重新散列!因此,这个过程实际上非常耗时,地图中的元素越多,就越耗时。

    hash过程相当于重新散列所有元素,并重新计算要分配哪个桶。

    那么,有没有人想过一个问题,既然它很麻烦,为什么要扩展呢?哈希映射不是数组链表?没有膨胀,它可以无限期储存。你为什么要扩张?

    这实际上与哈希冲突有关。

    哈希冲突

    我们知道哈希映射实际上是基于底部的哈希函数实现的,但是哈希函数都有以下基本特征:如果基于同一个哈希函数计算的哈希值不同,那么输入值肯定会不同。然而,如果从相同的散列函数计算的散列值是相同的,则输入值不一定是相同的。

    两个不同的输入值根据相同的散列函数计算出相同的散列值的现象称为冲突。

    衡量散列函数质量的一个重要指标是冲突的概率和冲突的解决方案。

    为了解决哈希冲突,有很多方法,其中最常见的是链地址法,这也是HashMap采用的方法。有关详细信息,请参阅关于整个网络上地图中哈希()分析的最全面的文章。没有其他两个。

    HashMap将数组和链表结合在一起,充分发挥它们的优势。我们可以把它理解为一系列链表。

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

    当我们将一个元素放入HashMap中时,我们需要首先确定数组中哪个链表将被列出,然后将这个元素挂在这个链表的后面。

    当我们从HashMap中获取元素时,我们还需要定位数组中的哪个链表,然后逐个遍历链表中的元素,直到找到所需的元素。

    可以看出哈希映射通过链表数组的结构解决了哈希冲突的问题。

    但是,如果HashMap中的冲突太高,数组的链表将退化为链表。这时,查询速度将大大降低。

    因此,为了确保哈希映射读取的速度,我们需要找到方法来确保哈希映射冲突

    避免哈希冲突的扩展

    如何有效避免哈希冲突?

    让我们先回想一下。你认为什么会导致哈希映射有更多的哈希冲突?

    只有两种情况:

    1。容量太小。小容量增加了碰撞的可能性。如果狼有更多的肉而更少的肉,它们会为了力量而竞争。

    2。哈希算法不够好。如果算法不合理,可以将所有算法分成一个或多个桶。不平等的分配会导致力量的竞争。

    因此,解决哈希映射中的哈希冲突也是从这两个方面开始的。

    这两点在HashMap中都有很好的揭示。通过在适当的时间扩大数组容量,并通过适当的哈希算法计算元素分配到的数组,这两种方法的组合可以大大降低冲突的概率。可以避免查询效率低的问题。

    为什么默认的装载因子是0.75

    在这一点上,我们知道装载因子是HashMap中的一个重要概念,他指出了这个HashMap的最大充满度。

    为了避免哈希冲突,哈希映射需要在正确的时间扩展。也就是说,当元素的数量达到一个临界值时,这个临界值就与负载因子有关,换句话说,设置一个合理的负载因子能有效地避免?哈希冲突。

    那么,负载因子的设置合适吗?

    在JDK源代码中,该值当前为0.75:

    1。那么,为什么选择0.75?这背后的考虑是什么?为什么不是1,不是0.8?不是0.5,而是0.75?

    在JDK的官方文件中,有这样一个描述:

    一般来说。默认负载系数(. 75)在时间和空间成本之间提供了一个很好的折衷。较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括获取和放置)。

    一般来说,默认负载系数(0.75)在时间和空间成本之间提供了一个很好的平衡。较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put)。

    想象一下,如果我们将负载因子设置为1,并使用默认的初始值16作为容量,那么HashMap在扩展之前需要“满”。

    那么在hashMap中,最好的情况是这16个元素通过Hash算法后分别归入16个不同的桶中,否则Hash冲突将不可避免地发生。此外,元素越多,哈希冲突的概率越高,搜索速度越慢。

    0.75

    的数学基础另外,我们可以通过数学思维来计算这个值有多合适。

    让我们假设一个桶是空的和非空的概率是0.5。我们用S表示容量,用N表示添加元素的数量。

    使用S表示添加的键的大小和N个键的数量。根据二项式定理,桶为空的概率为:

    因此,如果桶中的元素数小于下列值,桶可能为空:

    当S接近无穷大时,如果增加的键数使P(0)=0.5,则n/s很快接近log(2):

    因此,合理的值约为0.7。

    当然,这种数学计算方法并不是在爪哇的官方文件中发现的,我们也没有办法调查是否有这种考虑,就像我们不知道鲁迅写这篇文章时的想法一样,我们只能推测。这个猜想来自于Flor上的堆栈( . com/Questions//What-the-significance-of-load-factor-in-HashMap)

    0.75 improve factor

    理论上我们认为负载因数不能太大,否则会导致大量的哈希冲突,并且不能太小,这会浪费空间。

    通过数学推理,将该值计算在0.7左右是合理的。

    那么,你为什么最终选择0.75?

    记得我们之前提到过一个公式,那就是。

    我们在《为啥HashMap的默认容量是16?》中介绍,根据HashMap的扩展机制,他将确保容量的值总是2的幂。

    然后,为了确保结果是一个整数,取值为0.75(3/4)是合理的,因为这个数与2的任何幂的乘积都是一个整数。

    Summary

    HashMap是一个K-V结构。为了提高查询和插入的速度,底层采用链表数组的数据结构。

    但是,在计算元素的位置时,有必要使用哈希算法,哈希映射使用的是链地址方法。这种方法有两个极端。

    如果哈希映射有很高的哈希冲突概率,哈希映射将退化成一个链表(它并没有真正退化,但它就像直接操作链表一样)。然而,我们知道链表的最大缺点是查询速度相对较慢,它需要从头部开始一个接一个地遍历。

    因此,为了避免哈希映射中大量的哈希冲突,有必要在适当的时候对其进行扩展。

    而扩展取决于达到临界值的元素数量。HashMap中临界值的计算方法:

    其中负载因子表示数组可以达到的最大满度。该值不应太大或太小。

    loadFactor太大,例如,等于1,那么将有很高的哈希冲突概率,这将大大降低查询速度。

    loadFactor太小,例如,等于0.5,所以频繁的扩展会大大浪费空间。

    因此,该值需要介于0.5和1之间。根据数学公式。该值在对数(2)时是合理的。

    此外,为了提高容量扩展效率,哈希映射对其容量有一个固定的要求,必须是2的幂。

    所以,如果负载因子是3/4,那么负载因子和容量的乘积可以是一个整数。

    因此,一般来说,除非有特殊原因,我们不建议修改负载系数的值。

    例如,如果我清楚地知道我的地图只存储5 kv并且永远不会改变,那么我可以考虑指定负载系数。

    但事实上,我也不推荐它。我们可以通过指定容量来实现这一点。关于细节,为什么HashMap 16的默认容量是?

    References:

    . com/Questions//What-is-the-significance-of-load-factor-in-HashMap

    . html

    福石信息网 版权所有© www.sykntwztd.com 技术支持:福石信息网 | 网站地图