Java 中 HashMap 的工作原理

什么是哈希 (Hashing)

它是将一个对象转换为一个整数值的过程。整数值用于索引和更快的搜索。

换句话说，哈希是一种用于从一组相似对象中唯一标识特定对象的技术。

什么是 HashMap

HashMap 是 Java 集合框架的一部分。它使用一种称为哈希的技术。它实现了 Map 接口。它以键值对的形式存储数据。HashMap 包含一个节点数组，节点由类表示。它在内部使用数组和链表数据结构来存储键和值。HashMap 中有四个字段。

在理解 HashMap 的内部工作原理之前，我们必须了解 hashCode() 和 equals() 方法。

• equals(): 它检查两个对象的相等性。它比较键，看它们是否相等。它是 Object 类的一个方法。它可以被重写。如果你重写了 equals() 方法，那么重写 hashCode() 方法是强制性的。
• hashCode(): 这是 Object 类的一个方法。它以整数形式返回对象的内存引用。从该方法获得的值用作存储桶编号。存储桶编号是 Map 中元素的地址。null 键的哈希码为 0。
• 存储桶 (Buckets): 节点数组称为存储桶。每个节点都有一个像链表这样的数据结构。一个存储桶可以共享多个节点。它们的容量可能不同。

哈希函数

给定一个输入（或键）后，哈希函数会输出一个固定长度的字符串或数字，通常是哈希码。要索引哈希表，请使用此哈希码（类似于 HashMap 中的数组）。哈希函数的主要目标是最小化冲突并将输入均匀地分布到整个哈希表中。

在 HashMap 中插入键值对

我们使用 put() 方法将键值对插入 HashMap，其默认大小为 16（0 到 15）。

示例

在以下示例中，我们想在 HashMap 中插入三个（键，值）对。

让我们看看键值对将存储在 Hash Map 的哪个索引处。当我们调用 put() 方法时，它会计算键“Aman”的哈希码。假设“Aman”的哈希码为 2657860。要将键存储在内存中，我们需要计算索引。

计算索引

索引最小化了数组的大小。计算索引的公式是

其中 n 是数组的大小。因此，“Aman”的索引值为

值 4 是计算出的索引值，键和值将存储在 HashMap 中的该位置。

哈希冲突 (Hash Collision)

当计算出的索引值对于两个或多个键来说相同时，就会发生这种情况。让我们计算另一个键“Sunny”的哈希码。假设“Sunny”的哈希码为 63281940。要将键存储在内存中，我们需要使用索引公式计算索引。

值 4 是计算出的索引值，键将存储在 HashMap 中的该位置。在这种情况下，equals() 方法检查两个键是否相等。如果键相同，则用当前值替换该值。否则，通过链表将此节点对象连接到现有节点对象。因此，两个键都将存储在索引 4 处。

类似地，我们将存储键“Ritesh”。假设该键的哈希码为 2349873。索引值为 1。因此，该键将存储在索引 1 处。

处理冲突

尽管已尽力最小化冲突，但冲突仍然不可避免。处理冲突的两种主要策略是：

• 链式法 (Chaining): 在哈希到相同索引的所有元素存储在该索引处的链表或树中
• 开放寻址法 (Open Addressing): 当发生冲突时，通过探测（例如，线性探测、二次探测）在哈希表中找到另一个开放的槽。

HashMap.get() 方法

get() 方法用于通过其键获取值。如果我们不知道键，它将不会获取值。调用 get(K Key) 方法时，它会计算键的哈希码。

假设我们需要获取键“Aman”。将调用以下方法：

它生成哈希码 2657860。现在使用索引公式计算 2657860 的索引值。如上所述，索引值将为 4。get() 方法搜索索引值 4。它将节点中的第一个元素键与给定的键进行比较。如果两个键都相等，则返回该值，否则检查节点中的下一个元素（如果存在）。在我们的场景中，它被找到为节点中的第一个元素，并返回值 19。

让我们获取另一个键“Sunny”。

键“Sunny”的哈希码为 63281940。63281940 的计算出的索引值为 4，正如我们在 put() 方法中计算的那样。转到数组的索引 4，并将第一个元素的键与给定的键进行比较。它也比较键。在我们的场景中，给定的键是第二个元素，并且节点的下一个是 null。它将第二个元素的键与指定的键进行比较，并返回值 29。如果节点的下一个是 null，则返回 null。

HashMap 遍历

Java 提供了各种方法，如 entrySet()、keySet() 和 values() 来遍历 hash map。这些方法允许我们迭代 HashMap 的键、值或键值对。请看以下代码片段。

Rehashing 和负载因子

为了保持性能，HashMap 需要在元素数量显著增长时调整自身大小（rehash）。它由负载因子控制，负载因子衡量哈希表在容量自动增加之前允许填充的程度。

• 负载因子 (Load Factor): HashMap 的默认负载因子为 0.75。这意味着当哈希表填充到 75% 时，它将通过将其当前容量加倍来进行调整。
• Rehashing: 当发生 rehashing 时，会创建一个新的、更大的数组，并将所有现有条目重新哈希到新数组中的新索引。它确保哈希表在时间和空间复杂度之间保持良好的平衡。

HashMap 的优点和缺点

优点

1. 快速访问: 为 put 和 get 操作提供平均 O(1) 的时间复杂度。
2. 灵活性: 可以存储 null 键和值。
3. 非同步: 由于缺乏同步开销，性能更高（但不线程安全）。

缺点

1. 非同步: 非线程安全，在多线程环境中需要手动同步。
2. 内存开销: 由于其内部结构，可能会消耗大量内存。
3. 无序: 不维护其键或值的任何顺序。

结论

Java 的 HashMap 数据结构是一种灵活且流行的数据结构，它提供了有效的基于哈希的存储和检索。要成功使用它，必须了解其内部工作原理，包括遍历方法、处理冲突、rehashing 和哈希函数。

尽管它为大多数活动提供了出色的效率，但开发人员应该意识到它的缺点，包括内存成本和缺乏线程安全性。通过遵循推荐的实践并考虑应用程序的特定需求，您可以使用 HashMap 来获得最佳的性能和功能。