大多数 JAVA 开发人员都在使用 Maps，尤其是 HashMaps。HashMap 是一种简单而强大的存储和获取数据的方法。但是有多少开发人员知道 HashMap 在内部是如何工作的？几天前，我阅读了大量 java.util.HashMap 的源代码（Java 7 然后是 Java 8），以便深入了解这个基本数据结构。在这篇文章中，我将解释 java.util.HashMap 的实现，介绍 JAVA 8 实现中的新功能，并讨论使用 HashMap 时的性能、内存和已知问题。

内部存储器

JAVA HashMap 类实现了接口 Map<K,V>。该接口的主要方法有：

V put(K键，V值)
V 获取（对象键）
V 移除（对象键）
Boolean containsKey(对象键)

HashMaps 使用一个内部类来存储数据：Entry<K, V>。这个条目是一个简单的键值对，有两个额外的数据：

对另一个条目的引用，以便 HashMap 可以存储单链表等条目
表示键的哈希值的哈希值。存储这个哈希值是为了避免每次 HashMap 需要它时计算哈希。

这是 JAVA 7 中的 Entry 实现的一部分：

HashMap 将数据存储到多个条目的单链表（也称为桶或箱）中。所有列表都注册在一个 Entry 数组（Entry<K,V>[] 数组）中，这个内部数组的默认容量是 16。

下图显示了具有可为空条目数组的 HashMap 实例的内部存储。每个Entry可以链接到另一个Entry，形成一个链表。

所有具有相同哈希值的键都放在同一个链表（桶）中。具有不同哈希值的键最终可能在同一个桶中。

当用户调用 put(K key, V value) 或 get(Object key) 时，该函数计算 Entry 应该在的桶的索引。然后，该函数遍历列表以查找具有相同键的条目（使用键的 equals() 函数）。

在 get() 的情况下，该函数返回与条目关联的值（如果条目存在）。

在 put(K key, V value) 的情况下，如果条目存在，则函数将其替换为新值，否则它会在单链表的头部创建一个新条目（根据参数中的键和值）。

这个bucket的索引（链表）是由map分3步生成的：

它首先获取密钥的哈希码。
它重新散列哈希码以防止来自键的错误散列函数将所有数据放在内部数组的同一索引（存储桶）中
它采用重新散列的散列哈希码并使用数组的长度（减 1）对其进行位掩码。此操作确保索引不能大于数组的大小。您可以将其视为一个计算非常优化的模函数。

这是处理索引的 JAVA 7 和 8 源代码：

为了有效地工作，内部数组的大小需要是 2 的幂，让我们看看为什么。

想象一下数组大小是 17，掩码值将是 16（大小 -1）。16 的二进制表示为 0…010000，因此对于任何哈希值 H，使用按位公式“H AND 16”生成的索引将是 16 或 0。这意味着大小为 17 的数组将仅用于2 个桶：索引 0 的一个和索引 16 的一个，效率不高……

但是，如果您现在采用 2 的幂（如 16）的大小，则按位索引公式为“H AND 15”。15 的二进制表示为 0…001111，因此索引公式可以输出 0 到 15 的值，并且完全使用大小为 16 的数组。例如：

如果 H = 952 ，其二进制表示为 0..0111011 1000，相关索引为 0…0 1000 = 8
如果 H = 1576 其二进制表示为 0..01100010 1000，则关联索引为 0…0 1000 = 8
如果 H = 12356146，则其二进制表示为 0..010111100100010100011 0010，关联索引为 0…0 0010 = 2
如果 H = 59843，其二进制表示为 0..0111010011100 0011，相关索引为 0…0 0011 = 3

这就是为什么数组大小是 2 的幂。这种机制对开发者来说是透明的：如果他选择一个大小为 37 的 HashMap，该 Map 会自动选择 37 之后的下一个 2 的幂（64）作为其内部数组的大小。

自动调整大小

获取索引后，函数（get、put 或 remove）访问/迭代关联的链表以查看是否存在给定键的现有条目。如果不进行修改，此机制可能会导致性能问题，因为该函数需要遍历整个列表以查看条目是否存在。假设内部数组的大小是默认值（16），您需要存储 200 万个值。在最好的情况下，每个链表的大小为 125 000 个条目（2/16 百万）。因此，每个 get()、remove() 和 put() 将导致 125 000 次迭代/操作。为了避免这种情况，HashMap 可以增加其内部数组以保持非常短的链表。

创建 HashMap 时，可以使用以下构造函数指定初始大小和 loadFactor：

如果不指定参数，则默认 initialCapacity 为 16，默认 loadFactor 为 0.75。initialCapacity 表示链表内部数组的大小。

每次使用 put(...) 在 Map 中添加新的键/值时，该函数都会检查是否需要增加内部数组的容量。为此，地图存储了 2 个数据：

map的大小：表示HashMap中的条目数。每次添加或删除条目时都会更新此值。
一个阈值：它等于（内部数组的容量）* loadFactor，并且在每次调整内部数组大小后刷新

在添加新条目之前，put(...) 检查大小是否 > 阈值，如果是，则重新创建一个大小加倍的新数组。由于新数组的大小发生了变化，索引函数（返回按位运算“hash(key) AND (sizeOfArray-1)”）发生了变化。因此，数组的大小调整创建了两倍的桶（即链表）并将 所有现有条目重新分配到桶中（旧的和新创建的）。

此调整大小操作的目的是减小链表的大小，以便 put()、remove() 和 get() 方法的时间成本保持较低。调整大小后，其键具有相同哈希的所有条目将保留在同一个桶中。但是，之前在同一个桶中的 2 个具有不同哈希键的条目在转换后可能不在同一个桶中。

图片显示了调整内部数组大小之前和之后的表示。在增加之前，为了得到Entry E，map 必须遍历一个包含5 个元素的列表。调整大小后，相同的 get() 只是遍历 2 个元素的链表，调整大小后 get() 快 2 倍！

注意：HashMap 只增加内部数组的大小，它不提供减小它的方法。

线程安全

如果您已经了解 HashMaps，那么您就知道这不是线程安全的，但为什么呢？例如，假设您有一个仅将新数据放入 Map 的 Writer 线程和一个从 Map 读取数据的 Reader 线程，为什么它不能工作？

因为在自动调整大小机制期间，如果一个线程试图放入或获取一个对象，映射可能会使用旧的索引值，而不会找到该条目所在的新存储桶。

最坏的情况是当 2 个线程同时放置一个数据并且 2 个 put() 调用同时调整 Map 的大小。由于两个线程同时修改链表，因此 Map 可能最终在其链表之一中出现内循环。如果您尝试使用内部循环获取列表中的数据，则 get() 将永远不会结束。

HashTable实现是一种线程安全的实现，可以防止这种情况发生。但是，由于所有的 CRUD 方法都是同步的，所以这个实现非常慢。例如，如果线程 1 调用 get(key1)，线程 2 调用 get(key2)，线程 3 调用 get(key3)，则一次只有一个线程能够获取其值，而线程 3 可以访问数据同时。

自 JAVA 5 以来存在线程安全 HashMap 的更智能实现：ConcurrentHashMap。只有桶是同步的，因此如果不意味着访问同一个桶或调整内部数组的大小，多个线程可以同时获取（）、删除（）或放置（）数据。最好在多线程应用程序中使用此实现。

密钥不变性

为什么字符串和整数是 HashMap 键的良好实现？主要是因为它们是不可变的！如果您选择创建自己的 Key 类并且不使其不可变，则可能会丢失 HashMap 中的数据。

查看以下用例：

您有一个内部值为“1”的键
您使用此键将对象放入 HashMap
HashMap 从 Key 的哈希码生成一个哈希（所以从“1”开始）
Map 将此哈希存储 在新创建的条目中
您将键的内部值修改为“2”
修改了key的hash值但是HashMap不知道（因为存储了旧的hash值）
您尝试使用修改后的密钥获取对象
该映射计算您的键的新哈希（因此从“2”开始）以查找条目在哪个链表（桶）中
- 案例 1：由于您修改了密钥，因此 map 尝试在错误的存储桶中查找条目，但没有找到
- 案例 2：幸运的是，修改后的密钥生成与旧密钥相同的桶。然后映射遍历链表以找到具有相同键的条目。但是为了找到key，map首先比较hash值，然后调用equals()比较。由于您修改后的密钥与旧哈希值（存储在条目中）的哈希值不同，因此映射不会在链表中找到该条目。

这是Java中的一个具体示例。我在我的 Map 中放置了 2 个键值对，我修改了第一个键，然后尝试获取这 2 个值。地图只返回第二个值，第一个值在 HashMap 中“丢失”：

输出为：“test1= null test2=test 2”。正如预期的那样，Map 无法使用修改后的键 1 检索字符串 1。

JAVA 8 改进

HashMap 的内部表示在 JAVA 8 中发生了很大变化。确实，JAVA 7 中的实现需要 1k 行代码，而 JAVA 8 中的实现需要 2k 行。除了条目的链接列表之外，我之前所说的大部分内容都是正确的。在 JAVA8 中，您仍然有一个数组，但它现在存储包含与 Entries 完全相同的信息的节点，因此也是链表：

以下是 JAVA 8 中 Node 实现的一部分：

那么与 JAVA 7 最大的区别是什么？那么，Nodes 可以扩展到 TreeNodes。TreeNode 是一个红黑树结构，它存储了更多信息，因此它可以添加、删除或获取 O(log(n)) 中的元素。

仅供参考，这是存储在 TreeNode 中的数据的详尽列表

红黑树是自平衡二叉搜索树。尽管新添加或删除节点，它们的内部机制确保它们的长度始终在 log(n) 中。使用这些树的主要优点是在许多数据位于内部表的同一索引（桶）中的情况下，在树中的搜索将花费 O(log(n))而它会花费O(n)带有链表。

如您所见，树实际上比链表占用更多的空间（我们将在下一部分讨论它）。

通过继承，内表可以同时包含Node（链表）和TreeNode（红黑树）。Oracle 决定使用这两种数据结构的规则如下：
– 如果内表中的给定索引（桶）有超过 8 个节点，则链表转换为红黑树
– 如果给定索引（桶） ) 在内表中少于6个节点，将树转化为链表

这张图片显示了一个 JAVA 8 HashMap 的内部数组，其中包含两个树（位于桶 0）和链表（位于桶 1,2 和 3）。Bucket 0 是一棵树，因为它有超过 8 个节点。

内存开销

JAVA 7

HashMap 的使用是以内存为代价的。在 JAVA 7 中，HashMap 将键值对包装在 Entries 中。一个条目有：

对下一个条目的引用
预先计算的哈希（整数）
对密钥的引用
对值的引用

此外，一个 JAVA 7 HashMap 使用一个内部的 Entry 数组。假设一个 JAVA 7 HashMap 包含 N 个元素并且它的内部数组有一个容量 CAPACITY，额外的内存成本大约是：

sizeOf(整数) N + sizeOf(参考) (3*N+C)

在哪里：

整数的大小取决于等于 4 个字节
引用的大小取决于 JVM/OS/Processor，但通常为 4 个字节。

这意味着开销通常是 16 N + 4 CAPACITY 字节

提醒：在自动调整地图大小后，内部数组的容量等于 N 之后的 2 的下一个幂。

注意：从 JAVA 7 开始，HashMap 类有一个惰性初始化。这意味着即使您分配了一个 HashMap，在第一次使用 put() 方法之前，不会在内存中分配内部条目数组（花费 4 * CAPACITY 字节）。

JAVA 8

使用 JAVA 8 实现，获取内存使用量变得有点复杂，因为节点可以包含与条目相同的数据或相同的数据加上 6 个引用和一个布尔值（如果它是 TreeNode）。

如果所有的节点都是Nodes，那么JAVA 8 HashMap的内存消耗和JAVA 7 HashMap是一样的。

如果所有节点都是TreeNodes，一个JAVA 8 HashMap的内存消耗变为：

N sizeOf(integer) + N sizeOf(boolean) + sizeOf(reference) (9N+CAPACITY )

在大多数标准 JVM 中，它等于 44 N + 4 CAPACITY 字节

性能问题

倾斜的 HashMap 与平衡良好的 HashMap

在最佳情况下，get() 和 put() 方法的时间复杂度为 O(1)。但是，如果您不注意密钥的散列函数，您可能会得到非常缓慢的 put() 和 get() 调用。put() 和 get 的良好性能取决于将数据重新分区到内部数组（桶）的不同索引中。如果您的密钥的哈希函数设计不当，您将有一个倾斜的重新分区（无论内部数组的容量有多大）。所有使用最大条目链接列表的 put() 和 get() 都会很慢，因为它们需要迭代整个列表。在最坏的情况下（如果大多数数据都在同一个桶中），您最终可能会得到 O(n) 的时间复杂度。
这是一个视觉示例。第一张图显示了一个倾斜的 HashMap，第二张图是一个平衡良好的图。

在这种倾斜的 HashMap 的情况下，桶 0 上的 get()/put() 操作成本很高。获取条目 K 将花费 6 次迭代

在这个平衡良好的 HashMap 的情况下，获取 Entry K 将花费 3 次迭代。两个 HashMap 存储相同数量的数据并且具有相同的内部数组大小。唯一的区别是散列（键的）函数在桶中分配条目。

这是 JAVA 中的一个极端示例，我创建了一个哈希函数，将所有数据放在同一个存储桶中，然后添加 200 万个元素。

在我的核心 i5-2500k @ 3.6Ghz 上，使用 java 8u40 需要超过 45 分钟（我在 45 分钟后停止了该过程）。

现在，如果我运行相同的代码，但这次我使用以下哈希函数

它需要46 秒，这要好得多！此哈希函数比前一个具有更好的重新分区，因此 put() 调用更快。

如果我使用以下散列函数运行相同的代码，它提供了更好的散列重新分区

现在需要2 秒。

我希望你意识到散列函数的重要性。如果在 JAVA 7 上运行相同的测试，第一种和第二种情况的结果会更糟（因为 put 的时间复杂度在 JAVA 7 中为 O(n)，而在 JAVA 8 中为 O(log(n))）

使用 HashMap 时，您需要为您的键找到一个散列函数，将键分散到最可能的存储桶中。为此，您需要避免散列冲突。String Object 是一个很好的键，因为它具有很好的散列函数。整数也很好，因为它们的哈希码是它们自己的值。

调整开销

如果您需要存储大量数据，则应创建初始容量接近预期容量的 HashMap。

如果你不这样做，地图将采用默认大小 16，factorLoad 为 0.75。第 11 个 put() 将非常快，但第 12 个 (160.75) 将重新创建一个新的内部数组（及其关联的链表/树），新容量为 32。第 13 到第 23 会很快，但第 24 (320.75) 将重新创建（再次）一个代价高昂的新表示，它将内部数组的大小加倍。内部调整大小操作将出现在第 48、96、192、... put() 调用处。在低音量下，内部阵列的完全重建速度很快，但在高音量下可能需要几秒钟到几分钟。通过最初设置您的预期大小，您可以避免这些 代价高昂的操作。

但是有一个缺点：如果你设置了一个非常高的数组大小，比如 2^28 而你只在数组中使用了 2^26 个桶，你会浪费很多内存（在这种情况下大约是 2^30 字节）。

结论

对于简单的用例，您不需要知道 HashMap 是如何工作的，因为您不会看到 O(1) 和 O(n) 或 O(log(n)) 操作之间的区别。但是了解最常用的数据结构之一的底层机制总是更好。此外，对于 Java 开发人员职位来说，这是一个典型的面试问题。

在高容量时，了解它的工作原理并了解密钥散列函数的重要性变得很重要。

^28 而你只在数组中使用了 2^26 个桶，你会浪费很多内存（在这种情况下大约是 2^30 字节）。

结论