Load Factor in HashMap

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

• 初始容量
• 负载因子

在创建 HashMap 对象时，我们需要非常谨慎地选择这两个因素。加载因子和初始容量可以在创建 HashMap 类构造函数时进行配置，如下所示：

HashMap 的初始容量

HashMap 的初始容量是哈希表中 **桶** 的数量。它是在我们创建 HashMap 类对象时创建的。HashMap 的初始容量为 **2⁴**，即 **16**。当容量达到阈值时，HashMap 的容量会 **翻倍**。容量会增加到 **2⁵=32，2⁶=64**，依此类推。

假设我们实现了 hashCode() 方法，该方法确保键值对在 16 个桶中均匀分布。

考虑以下场景：

• 如果 HashMap 中有 **16** 个元素，hashCode() 方法会将 **一个** 元素分布到每个桶中。在这种情况下，搜索任何项只需要 **一次** 查找。
• 如果 HashMap 中有 **32** 个元素，hashCode() 方法会将 **两个** 元素分布到每个桶中。在这种情况下，搜索任何项最多需要 **两次** 查找。
• 同样，如果 HashMap 中有 **128** 个元素，hashCode() 方法会将 **八个** 元素分布到每个桶中。在这种情况下，搜索任何项最多需要 **八次** 查找。

从以上场景我们可以观察到，HashMap 中的项目数量是 **翻倍** 的。每个桶的最大查找时间没有显著增加，几乎保持 **恒定**。

或者，hashmap 以 **2ⁿ** 的幂次增长，并在达到其极限的起点继续增长。

负载因子

加载因子是一个度量，它决定何时 **增加** HashMap 的容量，以维持 get() 和 put() 操作的 **O(1)** 复杂度。HashMap 的默认加载因子为 **0.75f**（占映射大小的 75%）。

问题

问题在于，保持桶大小固定（即 16），我们不断增加映射中的总项数，这会扰乱时间复杂度。

解决方案

当我们增加桶的总数时，每个桶中的总项数开始增加。现在，我们可以为每个桶保持恒定的项数，并为 get() 和 put() 操作保持 O(1) 的时间复杂度。

加载因子是如何计算的

加载因子决定“何时增加桶的数量”。

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

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

这表示哈希映射的第 12 个键值对将保持其大小为 16。一旦第 13 个元素（键值对）进入 Hashmap，它将从默认的 **2⁴ = 16** 个桶增加到 **2⁵ = 32** 个桶。

另一种计算大小的方法

当加载因子比率 (m/n) 达到 0.75 时，hashmap 会增加其容量。

其中，

      m 是哈希映射中的条目数。

      n 是哈希映射的总大小。

加载因子的示例

让我们通过一个例子来理解加载因子。

我们知道哈希映射的默认桶大小是 16。我们插入第一个元素，然后检查是否需要增加哈希映射的容量。这可以通过以下公式确定：

在这种情况下，哈希映射的大小为 **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

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

如果要将 get 和 put 的复杂度保持在 O(1)，建议将加载因子设置为 0.75 左右。