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)时间复杂度。
负载系数的计算方式负载系数决定“何时增加铲斗数量”。
【HashMap中的负载系数】我们可以使用以下公式找到何时增加哈希图大小:
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。

    推荐阅读