HashMap的工作原理-Java快速进阶教程

Java中的HashMap基本上是一个桶数组（也称为HashMap的桶表-bucket table），其中每个桶使用链表来保存元素。链表是节点列表，其中每个节点都包含一个键值对。

简单来说，存储桶是节点的链接列表，其中每个节点都是类 Node<K，V> 的对象。节点的键用于获取哈希值，该哈希值用于从存储桶表中查找存储桶。

HashMap 的工作原理是散列数据结构或技术，该技术使用对象的哈希码将该对象放置在map中。

哈希涉及存储桶、哈希函数（hashCode() 方法）和哈希值。它为对象的插入和检索提供了 O（1） 的最佳时间复杂度。

因此，它是最适合存储键值对的数据结构，日后你可以从中以最短的时间检索回你的内容。

下图显示了用于存储键值对的典型哈希数据结构。

Java HashMap 的初始容量和负载因子

负载因子和初始容量是两个重要因素，它们在Java的HashMap的内部扮演着非常重要角色。

初始容量是在创建 HashMap 时通过 HashMap 在内部衡量存储桶数量或存储桶数组大小的指标。

HashMap 的默认初始容量为 16（即存储桶数量）。它总是以 2（2、4、8、16 等）的幂表示，指数可以 1 至 30 之间变化，所以最大值可以去到2^30。

负载因子是 HashMap 内部用来确定何时需要增加存储桶数组大小的一个因素。默认情况下，它是 0.75。

当 HashMap 中的节点数超过总容量的 75% 时，HashMap 会增加其存储桶数组大小。每次需要增加 HashMap 的存储桶数组大小时，HashMap 的容量总是翻倍。

存储桶表：

一个桶数组称为 HashMap 的桶表。在存储桶表中，存储桶是节点的链接列表，其中每个节点都是类 Node<K、V> 的对象。

节点的键用于获取哈希值，该哈希值用于从放置键值对的存储桶表中计算存储桶的索引。

节点：

链表的每个节点都是类 Node<K，V> 的对象。此类是 HashMap 类的静态内部类，实现 Map.Entry<K，V> 接口。

HashMap 的内部静态节点类的一般语法如下：

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}

final int hash：它是键的哈希值。

final K key：它是节点的键。

V value：它给出节点的值。

Node<K，V> next：它指示指向存储桶或链表中存在的下一个节点的指针。

hashCode（） 和 equals（） 方法在 Java HashMap 内部工作中的作用

hashcode（） 和 equals（） 在 Java 中 HashMap 的内部工作中起着重要作用。因此，在了解 HashMap 的内部工作原理之前，您应该了解 hashCode（） 和 equals（） 方法的基本知识。

hashcode（）：

哈希函数是将键映射到哈希表中的索引的函数。它从键获取索引，并使用该索引检索键的值。

哈希函数首先将搜索键（对象）转换为整数值（称为哈希代码），然后将哈希代码压缩为哈希表的索引。

Java 的对象类（根类）提供了一个其他类需要重写的hashCode()方法。hashCode（） 方法用于检索对象的哈希代码。默认情况下，它返回一个整数哈希代码，该代码是对象的内存地址（内存引用）。

hashCode（） 方法的一般语法如下：

public native hashCode()

The general syntax to call hashCode() method is as follows:
   int h = key.hashCode();

从 hashCode（） 方法获取的值用作存储桶索引号。存储桶索引号是映射中条目（元素）的地址。如果键为 null，则 hashCode（） 返回的哈希值将为 0。

equals（）：

equals()方法是Object类的一个方法，用于检查两个对象是否相等。HashMap使用equals()方法比较key是否相等。

Object类的equals()方法可以被重写。如果重写equals()方法，则必须重写hashCode()方法。

put 操作：Hashmap 的 put（） 方法在 Java 内部是如何工作的？

HashMap 的 put（） 方法用于存储键值对。put（） 方法添加键/值对的语法如下：

hashmap.put(key, value);

让我们举一个例子，我们将在 HashMap 中插入三个键、值对。

HashMap<String, Integer> hmap = new HashMap<>();  
 
 hmap.put("John", 20);  
 hmap.put("Harry", 5);  
 hmap.put("Deep", 10);

让我们了解这些“键值对”将会被存放到 HashMap 的哪些索引位置上。

当我们调用 put（） 方法将“键值对”添加到 hashmap 时，HashMap 通过调用其 hashCode（） 方法来计算键的哈希值或哈希代码。HashMap 使用该代码来计算将在其中放置键/值对的存储桶索引。

计算桶索引的公式（其中 n 是桶数组的大小）如下：

Index = hashCode(key) & (n-1);

假设“John”的哈希代码值为 2657860。那么“约翰”的索引值为：

Index = 2657860 & (16-1) = 4

值 4 就是经过计算后得到的索引值，因此这个“键值对”将被存放到 HashMap 的4号位置上。

注意：由于 HashMap 只允许一个空键。因为 null 的哈希码始终为 0，因此 hashCode（key） 方法返回的哈希值将为 0。

哈希冲突是如何发生和解决的？

当 hashCode（） 方法为哈希表中的两个或多个键生成相同的索引值时，会发生哈希冲突。为了克服这个问题，HashMap使用了链表技术。

当 hashCode（） 方法为新键生成的索引值和哈希表中已存在的键相同时，HashMap 将使用已经包含链表形式的节点的相同存储桶索引。

在链接列表的最后创建一个新节点，并通过LinkedList将该节点对象连接到现有节点对象。因此，两个key将存储在相同的索引值中。

当使用现有键插入新值对象时，HashMap 会将旧值替换为与键相关的当前值。为此，HashMap 使用 equals（） 方法。

此方法检查两个键是否相等。如果 Keys 相同，则此方法返回 true，并且该节点的值将替换为当前值。

下面我们举一例子来详细说明之前已经讲解过的知识

第 1 步：创建一个空的哈希映射，如下所示

Map map = new HashMap();

HashMap 的默认大小为 16，作为以下大小为 16 的空数组。

您可以看到上图，最初数组中没有元素。

第 2 步：插入第一个元素键值对，如下所示：

map.put(new Key("Dinesh"), "Dinesh");

步骤将按如下方式执行：

1. 首先，它将计算Key{“Dinesh”} 的哈希代码。假定调用hashCode方法，生成哈希代码为 4501。
2. 使用生成的哈希码计算索引，假定根据索引计算公式(此公式在前文介绍过),计算后等到它的结果是5。
3. 接着我们创建一个节点对象，如下所示： { int hash = 4501 Key key = {"Dinesh"} Integer value = "Dinesh" Node next = null }
4. 此节点将放置在索引 5 处。截至目前，索引中并不存在此节点，因为它是第一个元素。

让我们看看下面的 HashMap 图：

第 3 步：添加另一个元素键值对，如下所示：

map.put(new Key("Anamika"), "Anamika");

步骤按如下方式执行：

1. 首先，它将计算Key  {“Anamika”} 的哈希代码。调用hashCode（） 方法后得到哈希代码值为 4498。
2. 使用生成的哈希码计算索引，根据索引计算公式，它将为2。
3. 现在，它创建一个节点对象，如下所示： { int hash = 4498 Key key = {"Anamika"} Integer value = "Anamika" Node next = null }
4. 此节点将放置在索引 2 处。截至目前，此索引中并不存在此节点，因为它同样是本Key的第一个元素。

让我们看看下面的 HashMap 图：

第 4 步：（碰撞情况）添加另一个元素键值对，如下所示：

map.put(new Key("Arnav"), "Arnav");

步骤按如下方式执行：

1. 首先，它将计算Key   {“Arnav”} 的哈希代码。调用hashCode（） 方法后得到哈希代码值为 4498。
2. 使用生成的哈希码计算索引，根据索引计算公式，它将为2。
3. 现在，它创建一个节点对象，如下所示： { int hash = 4498 Key key = {"Arnav"} Integer value = "Arnav" Node next = null }
4. 如果没有其他对象，则此节点将放置在索引 2 处。
5. 但是在这个索引 2 中，已经出现了一个节点，所以这是冲突的情况。
6. 现在，它将检查hashCode（）和equals（）方法，如果两个键相同，那么它将用当前值替换旧值。
7. 如果两个键不同，那么它将通过链表将此节点连接到前一个节点对象后面，并且两者都存储在索引 2 中。

让我们看看下面的 HashMap 图：

第 5 步：添加另一个元素键值对，如下所示：

map.put(new Key("Rushika"), "Rushika");

步骤按如下方式执行：

1. 首先，它将计算Key   {“Rushika”}的哈希代码。调用hashCode（） 方法后得到哈希代码值为 4515。
2. 使用生成的哈希码计算索引，根据索引计算公式，它将是3。
3. 现在，它创建一个节点对象，如下所示： { int hash = 4515 Key key = {"Rushika"} Integer value = "Rushika" Node next = null }
4. 此节点将放置在索引 3 处。截至目前，此索引中不存在任何节点，因为它是第一个元素。

让我们看看下面的 HashMap 图：

通过上面这个例子，我相信大家已经基本单了解了HashMap 的 put（） 方法的内部工作原理。让我们转到下一节，看看 HashMap 的 get（） 方法在内部是如何工作的。

HashMap 中的 get（） 方法如何在 Java 内部工作？

HashMap 中的 get（） 方法用于通过其键检索值。如果我们不知道KEY，它将不会获取值。调用 get（） 方法的语法如下：

value = hashmap.get(key);

当使用 get(K Key) 方法来获取值时，它使用上述方法计算存储桶的索引。然后，使用 equals（） 方法搜索该存储桶的列表以查找给定的键，并返回最终结果。

同样本节也举一个例子来帮助理解这个方法工作过程

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

Get将按如下步骤来处理上面这个获取指令：

1. 首先，它将计算Key{“Arnav”} 的哈希代码。调用hashCode（） 方法后得到哈希代码值为 4498。
2. 使用生成的哈希码计算索引，根据索引计算公式，它将为2。
3. 转到数组的索引 2，并将第一个元素的键与给定键进行比较。如果两者都相等，则返回该值，否则，检查下一个元素是否存在。
4. 在我们的例子中，它比较后第一个元素后并不相等，因此只能沿着链表往下找。节点对象的第一个元素和下一个元素不为空。
5. 如果节点的下一个为空，则返回空。
6. 如果节点的下一个不为 null，则遍历链表，一直到最后链值。在查找过程中找到则返回实际链点值；直到最后如何都找不到值，则返回空。

put（） 和 get（） 方法的时间复杂度

HashMap 在常量时间O（1）内插入和检索一个键值对。但在最坏的情况下，当所有节点返回相同的哈希值并插入到同一个存储桶中时，它可能是 O（n）。

n 个节点的遍历开销为 O（n）。

重新散列的概念

重新哈希是当映射中的键数达到阈值时由 HashMap 自动发生的过程。阈值计算为阈值 = 容量 *（负载系数为 0.75）。

在这种情况下，将创建一个具有更多容量的新大小的存储桶阵列，并将所有现有内容复制到其中。

例如：

Load Factor: 0.75
Initial Capacity: 16 (Available Capacity initially)
Threshold = Load Factor * Available Capacity = 0.75 * 16 = 12

当第 13 个键值对插入 HashMap 时，HashMap 会将其存储桶数组大小增加到 16*2 = 32。

Now Available capacity: 32

Threshold = Load Factor * Available Capacity = 0.75 * 32 = 24

下次将第 25 个键值对插入 HashMap 时，HashMap 会将其存储桶数组大小增加到 32*2 = 64，依此类推。