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

Question

我想使用 HashSet<Long> 在内存中存储大量唯一数字。我计算了大约要消耗的内存（64 位指针大小）：

Long 将占用 space 的 16 个字节。所以最初我将条目数乘以 16 以获得内存。但实际上，每个条目的内存远远超过 16 个字节。之后我研究了 HashSet 实现。简而言之，在底层实现中，它实际上为 hashset 的每个条目存储了一个额外的虚拟对象（12 字节）。以及指向下一个条目的指针（8 字节）。因此每个条目允许额外的 12+8 个字节。

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

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

Answer 1

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

Answer 2

您可以使用此测试准确测量此尺寸：

    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键； V值；下一个节点。 HashSet 仅使用键并在值中放置一个虚拟对象。

Answer 3

对象的大小是一个实现细节。不能保证如果它在一个平台上是 x 字节，在另一个平台上也是 x 字节。

Long如你所知是装箱的，但是16个字节是错误的。原语 long 占用 8 个字节，但 long 周围框的大小取决于实现。根据this Hotspot related answer overhead words 和 padding 意味着装箱的 4 字节 int 可以达到 24 字节！

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

Answer 4

HashMap 默认大小为 16 个 HashMapEntry 条目。每个 HashMapEntry 上都有四个对象（int keyHash、Object next、Object key、Object value）。所以它通过包装元素引入了空条目的开销。此外，hashmap 的扩展率为 2x，因此对于 17 个元素，您将有 32 个条目，其中 15 个为空。

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

Answer 5

A HashSet 是一头复杂的野兽。在我的头脑中，在查看了一些评论之后，这里有一些你没有考虑到的消耗内存的项目：

Java 集合（真正的集合，不是普通数组）只能接受对象引用，不能接受基元。因此，您的 long 基元被装箱到 java.lang.Long 对象中，并且添加到 HashSet. Somebody mentioned that aLong` 对象的引用将是 24 个字节。加上引用，即 8 个字节。
哈希 table 桶是集合。我不记得他们是数组还是ArrayList，还是LinkedList，等等，但是因为散列算法会产生冲突，所以HashSet的元素必须放入集合中，这由哈希码组织。最好的情况是 ArrayList 只有 1 个元素：您的 Long 对象。 ArrayList 的默认后备数组大小为 10，因此对象中有 10 个对象引用，因此现在每个 Long 至少有 80 个字节。由于 Long 是一个整数，我怀疑散列算法可以很好地把事情分散开来。我不确定值超过 Integer.MAX_VALUE 的多头会发生什么。由于生日悖论，这将不得不以某种方式发生冲突。
实际散列 table - HashSet 基本上是一个 HashMap，其中的值并不有趣。在底层，它创建了一个 HashMap，其中有一个桶数组来表示散列 table。数组大小是根据容量来的，根据你添加的元素个数不清楚。
散列的大小 table 通常会有意地拥有比需要更多的桶，以使未来的增长更容易。希望它不会更多。但是不要指望 5 个元素恰好需要 5 个桶。

长话短说，哈希 table 是一种内存密集型数据结构。这是 space/time 的权衡。假设一个良好的散列分布，你会得到，以额外内存使用为代价的恒定时间查找。

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

How much memory Java HashSet<Long> should take

java

hashset

data-structures