Java HashSet<Long>应该占用多少内存？

Question

我想用一个HashSet<Long>来存储大量唯一数字的列表，并且在内存中。我计算了所需的近似内存（以64位指针大小为单位）：

Long占用16个字节的空间。因此，最初我将条目数乘以16以获取内存。但实际上，每个条目的内存要比16字节多得多。之后我研究了 HashSet 的实现。简而言之，在底层实现中，它实际上会在hashset的每个条目中存储一个额外的虚拟对象（12字节）。并且还有一个指向下一个条目的指针（8字节），从而使每个条目多出12+8字节。

因此，每个条目的总内存：16+12+8 = 36字节。但当我运行代码并检查内存时，每个条目的内存仍然比36字节多得多。

我的问题（简而言之）：HashSet需要多少内存（例如，在64位机器上）？

- Syed Aqeel Ashiq

---

你忘记考虑到容量了。 - user3248346

http://java-performance.info/memory-consumption-of-java-data-types-2/ - nafas

为什么？Long类型需要占用16个字节的空间。 - weston

@nafas 阅读了那篇文章，但仍然没有解释为什么要将32乘以大小，然后将4乘以容量。 - Aqeel Ashiq

每个桶都是某种列表（不确定是数组，还是ArrayList，或者LinkedList，或其他什么）。理想的哈希算法会将元素均匀分布，使得每个桶/列表只有一个项，但是存在碰撞的可能性，因此桶必须是能够容纳多个值的数据结构。 - Brandon

Answer 1

您可以使用以下测试来精确测量此尺寸：

    long m1 = Runtime.getRuntime().freeMemory();
    // create object (s) here
    long m2 = Runtime.getRuntime().freeMemory();
    System.out.println(m1 - m2);

需要使用-XX:-UseTLAB选项运行

在我的64位HotSpot上，空的HashSet占用480字节。

为什么这么多？因为HashSet有一个复杂的结构（顺便说一下，在调试模式下的IDE可以帮助查看实际字段）。它基于HashMap（适配器模式）。因此，HashSet本身包含对HashMap的引用。HashMap包含8个字段。实际数据存储在节点数组中。一个节点具有：int hash; K key; V value; Node next。HashSet仅使用键并在值中放置虚拟对象。

- Evgeniy Dorofeev

---

这是一个非常适合好奇思维的食物。我会尝试并回来。 - Aqeel Ashiq

嗯，这很有趣，我从来不知道Set占用的空间比Map多。 - nafas

@nafas HashSet 内部使用了 HashMap。尽管所有的值都指向同一个虚拟对象。 - dkatzel

Answer 2

物体的大小是一项具体实现的细节。如果在一个平台上它是 x 个字节，在另一个平台上也可能不是 x 个字节。

正如你所知，Long 被装箱了，但 16 字节是错误的。原生的 long 占用 8 个字节，但包围 long 的盒子的大小取决于具体实现。根据这个与 Hotspot 相关的答案，开销词和填充意味着装箱的 4 字节的 int 可以达到 24 字节！

该（Hotspot 特定）答案中提到的字节对齐和填充也会适用于 Entry 对象，这也将推高消耗。

- weston

---

因此，使用包装类的惩罚（每个对象16字节）是主要问题。谢谢。 - Aqeel Ashiq

Answer 3

使用的内存为32 * SIZE + 4 * CAPACITY + (16 * SIZE)，其中"SIZE"是元素数量。

- FuRioN

---

你的意思是64 * SIZE吗？ - nafas

不是，它是12字节的标题 + 16字节的数据 + 4字节的填充。 - FuRioN

请问您能解释一下这个公式吗：为什么我们要用32乘以大小，4乘以容量，然后再用16乘以大小呢？ - Aqeel Ashiq

请提供一个来源。 - Sibbo

那么为什么头部的大小是32字节？容量为什么要乘以4？Long对象的大小为什么是16字节？ - Sibbo

Answer 4

HashMap 的默认大小为 16，每个 HashMapEntry 上有四个对象（int keyHash、Object next、Object key、Object value）。因此，仅仅为了包装元素的空条目而引入开销。此外，哈希映射具有 2x 的扩展速率，因此对于 17 个元素，您将拥有 32 个条目，其中 15 个为空。

更简单的方法是使用内存分析器检查堆转储。

- Fran Montero

Answer 5

HashSet是一个复杂的数据结构。就我目前所知和评论的回顾，以下是一些你没有考虑到的占用内存的因素：

1. Java集合（真正的集合，而不是普通数组）只能存储对象引用，不能存储原始类型。因此，您的long原始类型会被装箱为java.lang.Long对象，并将其引用添加到HashSet中。有人提到Long对象将占用24个字节。再加上引用，即8个字节。
2. 哈希表桶是集合。我不记得它们是数组还是ArrayList、LinkedList等，但由于哈希算法可能会产生冲突，HashSet的元素必须放入集合中，并按哈希码组织。最好的情况是一个只有1个元素的ArrayList：您的Long对象。ArrayList的默认后备数组大小为10，因此现在每个Long至少有80个字节。由于Long是一个整数，我怀疑哈希算法会很好地分散事物。我不确定值超过Integer.MAX_VALUE的long会发生什么。由于生日悖论，它必须以某种方式发生碰撞。
3. 实际的哈希表- HashSet基本上是一个HashMap，其中值不重要。在底层，它创建了一个HashMap，其中包含表示哈希表的桶的数组。该数组的大小基于容量，根据您添加的元素数量，容量不清楚。
4. 哈希表的大小通常故意比所需的要大，以便将来增长更容易。希望它不会太多。但是不要期望5个元素恰好需要5个桶。

长话短说，哈希表是一种内存密集型的数据结构。这是时间和空间之间的权衡。假设哈希分布良好，您将获得常数时间的查找，但需要额外的内存使用。

- Brandon

---

哈希表桶是集合。哈希桶是一个链表，现在可能是一棵树结构。它们是Map.Entry的包私有子类型，与我们可见的任何集合无关。 - Radiodef