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
的结构:
如我们所见,我们的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
的结构:
现在,让我们向Map
添加更多条目:
mapWithInitialCapacityAndLF.put("6", "Six");
mapWithInitialCapacityAndLF.put("7", "Seven");
//.. more entries
mapWithInitialCapacityAndLF.put("15", "fifteen");
让我们再次观察我们的Map
结构:
尽管重新哈希处理有助于保持较低的复杂度,但这是一个昂贵的过程。如果我们需要存储大量数据,则应创建具有足够容量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 评论