共计 6496 个字符，预计需要花费 17 分钟才能阅读完成。
大多数 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 字节）。
论断
对于简略的用例，您不须要晓得 HashMap 是如何工作的，因为您不会看到 O(1) 和 O(n) 或 O(log(n)) 操作之间的区别。然而理解最罕用的数据结构之一的底层机制总是更好。此外，对于 Java 开发人员职位来说，这是一个典型的面试问题。
在高容量时，理解它的工作原理并理解密钥散列函数的重要性变得很重要。
心愿这篇文章能帮忙你深刻理解 HashMap 的实现。
对于 HashMap，你学废了么？
