迹忆客 专注技术分享

什么是哈希

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

什么是 HashMap

HashMap 是 Java 集合框架的一部分。 它使用一种称为散列的技术。 它实现了 Map 接口。 它将数据存储在 Key 和 Value 对中。 HashMap 包含一个节点数组，节点表示为一个类。 它在内部使用数组和 LinkedList 数据结构来存储 Key 和 Value。 HashMap 中有四个字段。

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

• equals() ：检查两个对象的相等性。 它比较 key，无论它们是否相等。 它是 Object 类的一个方法。 它可以被覆盖。 如果重写 equals() 方法，则必须重写 hashCode() 方法。
• hashCode() ：这是 object 类的方法。 它以整数形式返回对象的内存引用。 从方法接收到的值用作桶号。 桶号是 Map 内元素的地址。 null Key 的哈希码为 0。
• Buckets ：节点的数组称为桶。 每个节点都有一个类似于 LinkedList 的数据结构。 多个节点可以共享同一个桶。 容量可能不一样。

在 HashMap 中插入键、值对

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

示例

在下面的示例中，我们要在 HashMap 中插入三个 (Key, Value) 对。

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

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

计算索引

索引最小化数组的大小。 指数计算公式为：

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

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

Index = 2657860 & (16-1) = 4  

值 4 是计算的索引值，其中 Key 和 value 将存储在 HashMap 中。

哈希冲突

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

Index=63281940 & (16-1) = 4  

4 是我们计算出来的索引值，其中 Key 将存储在 HashMap 中。 在这种情况下，equals() 方法检查两个 Key 是否相等。 如果 Keys 相同，则将值替换为当前值。 否则，通过 LinkedList 将此节点对象连接到现有节点对象。 因此，两个 Key 都将存储在索引 4 处。

同样，我们将存储key “Ritesh”。 假设 Key 的哈希码为 2349873。索引值为 1。因此，此 Key 将存储在索引 1 处。

HashMap 中 get() 方法

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

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

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

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

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

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