拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 Java HashMap负载因子

Java HashMap负载因子

白鹭 - 2021-11-24 553 0 0

1.概述

在本文中,我们将看到Java HashMap负载因子的重要性以及它如何影响HashMap的性能。

2.什么是HashMap

HashMap类属于Java Collection框架,并提供Map接口的基本实现。当我们要根据键值对存储数据时,可以使用它。这些键值对称为映射条目,由Map.Entry类表示。

3. HashMap内部

在讨论负载系数之前,让我们回顾一下以下术语:

    • 杂凑
      • 容量
      • 临界点
      • 重新哈希
      • 碰撞

HashMap遵循哈希原理-一种将对像数据映射到某个代表性整数值的算法。哈希函数应用于键对像以计算存储桶的索引,以便存储和检索任何键值对。

HashMap的存储桶数。初始容量是创建M ap时的容量。 HashMap的默认初始容量为16。

HashMap中元素数量的增加,容量也会增加。负载因子是决定何时增加Map容量的度量。默认的负载系数是容量的75%。

HashMap的阈值大约是当前容量和负载因子的乘积。重新哈希是重新计算已存储条目的哈希码的过程。简而言之,当哈希表中的条目数超过阈值时,将Map该Map,使其具有的存储桶数大约是以前的两倍。

当哈希函数为两个不同的键返回相同的存储桶位置时,会发生冲突。

让我们创建我们的HashMap

Map<String, String> mapWithDefaultParams = new HashMap<>();

 mapWithDefaultParams.put("1", "one");

 mapWithDefaultParams.put("2", "two");

 mapWithDefaultParams.put("3", "three");

 mapWithDefaultParams.put("4", "four");

这是我们Map的结构:

Java

如我们所见,我们的HashMap是使用默认的初始容量(16)和默认的负载系数(0.75)创建的。此外,阈值为16 * 0.75 = 12,这意味着添加第12个条目(键值对)后,容量将从16增加到32。

4.自定义初始容量和负载系数

在上一节中,我们使用默认构造函数HashMap在以下各节中,我们将看到如何创建将初始容量和负载因子传递给构造函数HashMap

4.1。具有初始容量

首先,让我们创建一个具有初始容量Map

Map<String, String> mapWithInitialCapacity = new HashMap<>(5);

它将创建一个具有初始容量(5)和默认负载因子(0.75) Map

4.2。具有初始容量和负载系数

同样,我们可以同时使用初始容量和负载因子Map

Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5, 0.5f);

在这里,它将创建一个空的Map ,其初始容量为5,负载系数为0.5。

5.表现

尽管我们可以灵活选择初始容量和负载因子,但我们需要明智地选择它们。它们都影响Map的性能。让我们深入研究这些参数与性能之间的关系。

5.1。复杂

众所周知, HashMap内部使用哈希码作为存储键值对的基础。如果hashCode()方法编写得当,则HashMap将在所有存储桶中分配项目。因此, HashMap O(1)存储和检索条目

但是,当物品数量增加并且铲斗尺寸固定时,就会出现问题。每个存储桶中将有更多物品,并且会打扰时间复杂性。

解决方案是,当增加项目数量时,我们可以增加存储桶的数量。然后,我们可以在所有存储桶中重新分配项目。这样,我们将能够在每个存储桶中保持恒定数量的项目,并保持O(1)的时间复杂度。

在这里,负载系数可帮助我们确定何时增加铲斗数量。在较低的负载系数下,将有更多的自由铲斗,因此发生碰撞的机会更少。这将有助于我们提高Map性能。因此,我们需要保持较低的负载系数,以实现较低的时间复杂度

HashMap O(n)的空间复杂度,其中n是条目数。较高的负载因子值会减少空间开销,但会增加查找成本

5.2。重新整理

当在项目的数量Map越过阈值限制,则容量Map加倍。如前所述,当容量增加时,我们需要在所有存储桶中平均分配所有条目(包括现有条目和新条目)。在这里,我们需要重新哈希。也就是说,对于每个现有的键值对,以容量增加为参数再次计算哈希码。

基本上,当负载系数增加时,复杂度也会增加。进行重新哈希处理以保持所有操作的低负载因子和低复杂度。

让我们初始化Map

Map<String, String> mapWithInitialCapacityAndLF = new HashMap<>(5,0.75f);

 mapWithInitialCapacityAndLF.put("1", "one");

 mapWithInitialCapacityAndLF.put("2", "two");

 mapWithInitialCapacityAndLF.put("3", "three");

 mapWithInitialCapacityAndLF.put("4", "four");

 mapWithInitialCapacityAndLF.put("5", "five");

让我们看一下Map的结构:

Java

现在,让我们向Map添加更多条目:

mapWithInitialCapacityAndLF.put("6", "Six");

 mapWithInitialCapacityAndLF.put("7", "Seven");

 //.. more entries

 mapWithInitialCapacityAndLF.put("15", "fifteen");

让我们再次观察我们的Map结构:

Java

尽管重新哈希处理有助于保持较低的复杂度,但这是一个昂贵的过程。如果我们需要存储大量数据,则应创建具有足够容量HashMap这比自动重新哈希处理更有效。

5.3。碰撞

由于哈希码算法不正确,可能会发生冲突,并且通常会降低Map的性能。

在Java 8之前,Java中的HashMap通过使用LinkedList存储地图条目来处理冲突。如果某个键最终位于已经存在另一个条目的同一个存储桶中,则会将其添加到LinkedList的开头。在最坏的情况下,这将增加O(n)复杂度。

为避免此问题,Java 8和更高版本使用平衡树(也称为红黑树)而不是LinkedList来存储冲突条目。 HashMap的最坏情况性能从O(n)提升为O(log n)

HashMap最初使用LinkedList.然后,当条目数超过某个阈值时,它将用平衡的二叉树LinkedList TREEIFY_THRESHOLD常数决定该阈值。当前,该值为8,这意味着如果同一存储桶中有8个以上的元素,则Map将使用树来保存它们。

六,结论

在本文中,我们讨论了一种最受欢迎的数据结构: HashMap 。我们还看到了负载系数和容量如何影响其性能。

标签:

0 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *