Java中的HashMap内部实现或者HashMap如何在Java中内部工作是一个非常重要的面试问题。我们应该知道的一些重点是

• HashMap在哪里将其元素存储在内部？
• HashMap中的"存储桶"是什么意思？
• 什么是哈希概念，它与HashMap有什么关系？
• HashMap中的put()方法如何工作？
• 如果为密钥计算了相同的哈希，或者在哈希冲突的情况下如何存储元素，会发生什么？
• 如果添加了null键，会发生什么情况。
• HashMap中的get()方法如何工作？
• HashMap中的remove()方法如何工作？

在本文中，我们将介绍Java中的HashMap内部实现，并尝试解释上述要点。请注意，本文中提供的HashMap类的所有代码段均来自JDK 10.

HashMap在哪里存储其元素

Java内部的HashMap类在内部使用Node类型的Array(命名表)存储其元素。其中Node <K，V>是HashMap类中的内部类。 HashMap类中的数组定义如下。

transient Node<K,V>[] table;

在HashMap中，元素存储为(键，值)对，并且此(键，值)对由接口Map.Entry表示。 Node类是Map.Entry接口的实现。

HashMap中的术语存储桶是什么

当使用该键将(键，值)对添加到HashMap时，将计算哈希值，该哈希值给出将在其中添加(键，值)对的数组中的索引。

这里使用的术语存储桶实际上是数组的每个索引。默认情况下，HashMap数组的长度为16，因此HashMap中有16个存储桶。由于该数组的名称为table，因此table [0]为bucket0，table [1]为bucket1，依此类推，直到bucket15.

将元素添加到HashMap时，不会将其直接添加到数组中的该索引中。 HashMap的每个存储区都有一个关联的链表，每个数组索引都包含对该链表的引用。一旦根据计算出的哈希值确定必须向其添加元素的存储桶，便会在链表中创建一个新节点，该节点将具有(key，value)对。

下图显示了在HashMap的内部实现中，链表中的存储桶和存储的元素的外观。

HashMap内部结构

hashCode()和equals()方法

为了计算哈希，将调用hashCode()方法。 equals()方法用于比较对象是否相等。

这两种方法都在Java的Object类中定义，因此可用于所有类，因为Object类是Java中所有类的超类。如果使用任何自定义对象作为键，请确保实现了这两个方法hashCode()和equals()。

在HashMap中，哈希是使用密钥来计算的，因此正确实现hashCode()以便在所有存储桶之间公平分配密钥且哈希冲突较少的情况非常重要。例如，假设我们使用自定义对象作为键，并且hashCode()实现不好。如果将50个元素添加到HashMap中，并为其中的30个计算相同的哈希值，则与该存储桶关联的链表将包含30个元素，而其他存储桶相对较空，这会影响HashMap的整体性能。

equals()方法的实现用于验证插入的键是否等于任何已插入的键。因此，正确实现equals()方法以确保唯一标识对象非常重要。

HashMap中的put()方法如何工作

到目前为止，通过遍历bucket，hash和hashCode()和equals()方法完成了所有基础工作，现在我们可以轻松了解Java中HashMap的内部实现。

当使用put()方法添加新的(键，值)对时，首先将使用哈希计算哈希，该哈希将确定(键，值)对将进入的存储桶。

如果该存储桶为空，则将创建一个新的链表，其中链表的第一个节点将是(键，值)对，而存储桶(该数组索引)将保存对该链表的引用。

如果存储桶不为空，则表示链表已经存在。在那种情况下，equals()方法用于验证该存储桶中是否已存在这样的密钥，如果找不到，则在已经存在的链表中创建一个新节点。如果equals()方法返回true，则表示该存储桶中已存在密钥。在这种情况下，匹配键的新值将覆盖旧值。

在HashMap类的实现中，put()方法编写如下：

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

如我们所见，第一件事是通过传递密钥来计算哈希。

对put()方法的解释还涵盖了针对多个密钥计算相同哈希的场景(哈希冲突场景)。

添加空键时会发生什么

在HashMap中，允许添加一个null键。如果在key为空的情况下添加了(key，value)对，则不会进行哈希计算，并且该(key，value)对始终会添加到存储区0。

我们可以从hash()方法的内部实现中看到它。

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap中的get()方法如何工作

在Java中，使用键作为参数调用HashMap的get()方法。使用该键，计算哈希值以确定存储该元素的存储桶。如果与该存储桶关联的链表具有多个节点，则使用equals方法对链表进行迭代，以将存储的密钥与传递的密钥进行匹配。找到匹配的键后，将返回关联的值。

在HashMap类的实现中，get()方法的实现如下：

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}

HashMap中的remove()方法如何工作

remove()方法的实现与get()方法类似。使用传递的密钥，计算哈希值以确定存储该元素的存储桶。如果与该存储桶关联的链表具有多个节点，则使用equals方法对链表进行迭代以将存储的密钥与传递的密钥进行匹配。当找到匹配键时，链表的节点被取消引用。

Java 8中的HashMap更改

HashMap实现旨在为基本操作(获取和放置)提供恒定时间的性能。但是，如果未正确实现hashCode()且存在很多哈希冲突，则HashMap的性能可能会下降。

正如我们已经看到的，在发生哈希冲突的情况下，其中一个存储桶将具有更多的负载，并且更多(键，值)对将添加到与该存储桶关联的链表中。对于在链表中进行搜索(get()方法)，完成了链表的线性迭代，这意味着如果搜索的键是链表的最后一个节点，则O(n)的性能最差。

为了解决具有更多元素的特定链表的问题，在Java 8中更改了HashMap实现。在达到某个阈值后，用平衡树替换链表以存储元素。此更改可确保在最坏的情况下O(log(n))的性能，而不是在链表的情况下确保O(n)的性能。