Java中的HashMap工作

本文概述

• 什么是散列
• 什么是HashMap
• 在HashMap中插入键, 值对
• 哈希冲突
• HashMap中的get()方法

什么是散列

这是将对象转换为整数值的过程。整数值有助于索引编制和更快的搜索。

什么是HashMap

HashMap是Java收集框架的一部分。它使用一种称为哈希的技术。它实现了map接口。它将数据存储在“键和值”对中。 HashMap包含节点的数组, 并且该节点表示为一个类。它内部使用数组和LinkedList数据结构存储键和值。 HashMap中有四个字段。

在了解HashMap的内部工作之前, 你必须了解hashCode()和equals()方法。

• equals()：检查两个对象的相等性。它比较密钥, 无论它们是否相等。它是Object类的方法。它可以被覆盖。如果覆盖equals()方法, 则必须覆盖hashCode()方法。
• hashCode()：这是对象类的方法。它以整数形式返回对象的内存引用。从该方法接收的值用作存储桶编号。值区编号是地图内元素的地址。空键的哈希码为0。
• 存储桶：节点的数组称为存储桶。每个节点都有一个像LinkedList这样的数据结构。多个节点可以共享同一存储桶。容量可能有所不同。

在HashMap中插入键, 值对

我们使用put()方法在HashMap中插入键和值对。 HashMap的默认大小为16（0到15）。

例

在下面的示例中, 我们想在HashMap中插入三个（键, 值）对。

HashMap<String, Integer> map = new HashMap<>();
map.put("Aman", 19);
map.put("Sunny", 29);
map.put("Ritesh", 39);

让我们看一下键值对将在哪个索引处保存到HashMap中。当我们调用put()方法时, 它将计算键“ Aman”的哈希码。假设“ Aman”的哈希码为2657860。要将Key存储在内存中, 我们必须计算索引。

计算指标

索引使阵列的大小最小化。计算指标的公式为：

Index = hashcode(Key) & (n-1)

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

Index = 2657860 & (16-1) = 4

值4是键和值将存储在HashMap中的计算索引值。

哈希冲突

当两个或多个键的计算索引值相同时, 就是这种情况。让我们计算另一个键“ Sunny”的哈希码。假设“ Sunny”的哈希码为63281940。要将Key存储在内存中, 我们必须使用索引公式来计算索引。

Index=63281940 & (16-1) = 4

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

同样, 我们将存储密钥“ Ritesh”。假设该键的哈希码为2349873。索引值为1。因此, 此键将存储在索引1中。

HashMap中的get()方法

get()方法用于通过其Key获取值。如果你不知道密钥, 它将不会获取值。调用get（K Key）方法时, 它将计算Key的哈希码。

假设我们必须获取密钥“ Aman”。将调用以下方法。

map.get(new Key("Aman"));

它生成的哈希码为2657860。现在, 使用索引公式来计算2657860的索引值。正如我们上面计算的, 索引值为4。 get()方法搜索索引值4。它将第一个元素Key与给定的Key相比较。如果两个键相等, 则返回值, 否则检查节点中的下一个元素是否存在。在我们的场景中, 将其作为节点的第一个元素并返回值19。

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

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