HashMap中的负载系数

本文概述

• HashMap的初始容量
• 负载系数
• 负载系数的计算方式

HashMap是Java集合框架中的高性能数据结构之一。它为插入和检索提供了恒定的时间性能。有两个因素会影响哈希图的性能。

• 初始容量
• 负载系数

在创建HashMap对象时, 我们必须非常仔细地选择这两个因素。当我们创建HashMap类的构造函数时, 可以配置负载因子和初始容量, 如下所示：

HashMap hm=new HashMap(int initialCapacity, float loadFactor);

HashMap的初始容量

HashMap的初始容量是哈希表中存储桶的数量。它是在创建HashMap类的对象时创建的。 HashMap的初始容量为24, 即16。每次达到阈值时, HashMap的容量都会加倍。容量增加到25 = 32、26 = 64, 依此类推。

假设我们已经实现了hashCode()方法, 该方法确保键值对在16个存储桶之间平均分配。

请考虑以下情形：

• 如果HashMap中有16个元素, 则hashCode()方法将在每个存储桶中分配一个元素。在这种情况下, 搜索任何项目将仅进行查找。
• 如果HashMap中有32个元素, 则hashCode()方法将在每个存储桶中分配两个元素。在这种情况下, 搜索任何项目将最多进行两次查找。
• 同样, 如果HashMap中有128个元素, 则hashCode()方法将在每个存储桶中分配八个元素。在这种情况下, 搜索任何项目将最多进行八次查找。

从以上场景中我们可以看到, HashMap中的项目数量增加了一倍。每个存储桶中的最大查找时间并没有增加太多, 而是几乎保持不变。

或者, 哈希图以2n的幂增长, 并在起点达到其极限时继续增长。

负载系数

负载因子是一种决定何时增加HashMap容量以维护O（1）的get()和put()操作复杂度的度量。 HashMap的默认加载因子为0.75f（地图大小的75％）。

问题

问题是, 在保持固定的存储桶大小（即16）的情况下, 我们不断增加地图中的项目总数, 这会干扰时间复杂度。

解

当我们增加存储桶总数时, 每个存储桶中的总项开始增加。现在, 我们能够在每个存储桶中保持恒定数量的项目, 并保持get()和put()操作的O（1）时间复杂度。

负载系数的计算方式

负载系数决定“何时增加铲斗数量”。

我们可以使用以下公式找到何时增加哈希图大小：

initial capacity of the hashmap*Load factor of the hashmap.

哈希图的初始容量为= 16哈希图的默认加载因子= 0.75根据上述公式：16 * 0.75 = 12

它表示哈希映射的第12个键值对将保持其大小为16。第13个元素（键值对）进入Hashmap后, 它将其大小从默认的24 = 16个存储桶增加到25 = 32个存储桶。

另一种计算大小的方法：

当那时的负载因子比率（m / n）达到0.75时, hashmap会增加其容量。

哪里,

m是哈希图中的条目数。

n是哈希图的总大小。

负载系数示例

让我们通过一个例子来了解负载系数。

我们知道哈希表的默认存储区大小为16。我们插入第一个元素, 现在检查是否需要增加哈希表的容量。可以由以下公式确定：

Size of hashmap (m)/number of buckets (n)

在这种情况下, 哈希图的大小为1, 存储桶大小为16。因此, 1/16 = 0.0625。现在, 将该值与默认负载因子进行比较。

0.0625<0.75

因此, 无需增加哈希图的大小。

我们不需要将哈希图的大小增加到第12个元素, 因为

12/16=0.75

该负载系数等于默认负载系数0.75。

一旦我们在哈希图中插入第13个元素, 哈希图的大小就会增加, 原因是：

13/16=0.8125

大于默认的哈希图大小。

0.8125>0.75

现在我们需要增加哈希图的大小。

如果要保持获取和放置复杂度O（1）, 建议负载系数约为0.75。