HashMap如何占用内存？

Question

我害怕被批评。 无论如何，就像ArrayList会有连续的内存分配一样，LinkedList会有随机的内存分配，那么HashMap如何占用内存？ 它是否也会在内存中占用随机块？ 能否通过内存图形简要介绍Map的桶和其中的LinkedLists在内存中的位置？

我希望这不是一个胡说八道的问题。 没有找到关于Map内存分配图的太多信息。

编辑: 我提出的问题与调试/分析无关。 这只是关于HashMap如何适应内存的问题。 我之前表述得不清楚。

- Nihal Sharma

---

请访问http://www.javacodegeeks.com/2012/09/java-memory-model-simplified.html 了解更多关于Java内存管理的信息。 - Tinman

你可以通过加入一些上下文来增强你的问题，以便说明你为什么需要了解这些信息。你是在尝试调试慢速性能还是内存使用情况？ - Tinman

@tinman - 没有关于调试/分析的内容。只是想了解一下HashMap如何适应内存。谢谢。 - Nihal Sharma

Answer 1

这是两者的结合。

HashMap 的背后有一个基础的、连续的数组。该数组的元素实际上是单向链表。每当向映射中添加一个键值对时，就会对相应槽位（即与该键的哈希值相对应的槽位）添加一个链表条目。

例如，将 k 映射到 v 的映射可能如下所示：

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |
+-X-+-X-+-↓-+-X-+-X-+-X-+-X-+-X-+
          ↓
          ↓
        +---+
        | k |
        | - |
        | v |
        +---+

有一个长的“表”支持这个映射，以及一个支持特定的 k-to-v 对的条目。

最好你自己看一下HashMap源代码。

- arshajii

---

只有一个疑问。这个分配实际上是二维布局，而不是线性的一维，对吗？ - Nihal Sharma

@NihalSharma 再次说明，它有点像混合体。当您添加更多条目时，它会在第二个维度上“增长”（如果您选择这样考虑的话）。请注意，从性能的角度来看，您实际上希望地图尽可能平坦，因此如果添加了许多条目，则会重新分配并增加支持数组的大小。 - arshajii

非常感谢您对HashMap内存布局方面的解答，几乎解决了我所有的疑惑。 - Nihal Sharma

现在您已经有了一个简单的解释。这里是完整的硬核细节。http://en.wikipedia.org/wiki/Hash_table - Tinman

Answer 2

哈希表始终是一个数组，其中哈希码可以确定以获取数组元素的索引（在JDK中，这是条目）。因此，它也应该占用连续的内存。

- Biswajit_86