计算Java中HashMap的开销

Question

计算Java中HashMap的开销

javamemory-managementdata-structureshashmapoverhead

4

假设我正在哈希表中存储1000个对象。该哈希表已扩展，可以将三维坐标映射到其中存储的对象；内部的对象有固定大小。哈希键是一个长整型数。

如何通过数学方法计算出此结构的可能开销?

1.如果内部数据约为256MB，它的开销是否足够显著？ 2.除了使用代码分析器外（在某些情况下不可靠），是否有一种可靠的方法来计算其开销应该是多少？

我对哈希表的总大小不感兴趣 - 只关心使用哈希表会产生的开销。例如，如果我有10个int类型，每个占用4个字节，则是40个字节。如果我将它们放入数组中，我得到12个字节的恒定开销- 8个用于对象头，4个用于长度。如果我将它们放入另一个结构（例如TreeSet）中，我的开销将不是恒定的，因为树需要节点-因此我可能会得到以n表示的开销，其中n是集合中的项目数。

这里有一些对我来说很明显的事情，我将从这里开始：

1. 我将至少需要存储1000个longs。这些是可空类型，因此它们实际上是对象。因此，我假设正在使用的8字节长整型具有8字节的对象头。我将添加一个16n的因子。 2. 我还需要对每个对象进行引用，这些引用必须存在，无论对象是否已从映射中召回并正在使用。因此，每个对象需要额外的8字节。我们可以将其纳入数据大小中，但由于引用位于哈希表本身中，所以我认为最好将其作为开销的一部分。我的逻辑是：如果我取出哈希表中的所有数据并将它们存储在变量中，则那些n个引用仍将存在于哈希表中，前提是我没有删除这些数据对象，而我不会这样做。对象集是恒定的，尽管可以使用不同的键对其进行回收。 3. 哈希表本身的开销为8字节。 4. 哈希表必须存储内部项数（或者我认为如此！），因此需要4个字节。 5. 我愚蠢地假设哈希键位于数组中，并按哈希键顺序排序。该数组需要12个字节。 6. 我还假设对象也位于匹配数组中，并且在找到键时将其取消引用。我猜测另外需要12个字节。

这让我得到一个多项式方程：36 + 24n。

因此，我猜测使用长键的1000个数据对象的开销为24036字节。这是一种微不足道的开销，但我的问题是，实际开销是多少呢？

第二个有效的问题是，这在不同的JVM上有多大差异？有没有一种与JVM无关的方法来解决这个问题？举个例子，考虑一个只有32位对象头的JVM - 当查看数组时，你可能会说，即使大小因JVM而异，但在这种情况下，数组的开销将变为8个字节而不是12个字节。

我假设HashMap在相同版本的Java中采用固定的实现方式。

我可以尝试阅读源代码或运行分析，但这可能会产生基于我的JVM的误导性结果。我请求您的帮助 - 也许是了解情况的人 - 获得一些我们都不知道的信息。谢谢！

请参见以下答案，实际估计可以表示为：

每个条目8个字，加上每个长整型8个字节，再加上哈希映射对象头8个字节。

在我目前的环境（32位操作系统）中，1个字=4个字节。

在32位环境中的40n + 8：1000个条目的开销约为40k
在64位环境中的72n + 8：1000个条目的开销约为72k。

因此，似乎不到100k字节。

- user1086498

1

我会放弃第一点，因为我认为哈希映射并不存储实际的键。它计算它们的哈希值，并将其用作哈希映射中的索引（可能存储为数组），我会在你的公式中添加n *（哈希码的大小）。 - Razvan

RiverC，威尔：老实说，我不知道HashMap是否存储键，但冲突问题并不能让我相信它存储了键。假设您有包含x的Long l1和包含y的Long l2，它们的hashCode()方法返回相同的值，那么在Java HashMap中肯定会发生冲突。 - Razvan

@Razvan 的确哈希码并不是唯一的。在你的例子中，equals() 方法被调用来区分键。请参阅 http://docs.oracle.com/javase/6/docs/api/java/util/Map.html#get(java.lang.Object)。 - Will

当然，HashMap会存储键。如果不存储它们，它如何将它们与作为参数传递的键进行比较呢？阅读javadoc：所有内容都在那里解释了。 - JB Nizet

1

是的，键也被存储了。我在谈论一个理论实现 :). @RiverC：这两个可能会有帮助：http://docs.oracle.com/javase/6/docs/api/java/util/Map.html#get%28java.lang.Object%E2%80%8C%E2%80%8B http://docs.oracle.com/javase/6/docs/api/java/lang/Object.html#hashCode%28%29 - Razvan

显示剩余8条评论

3个回答

0

创建一个程序，在其中创建所有对象并将它们存储在一个简单的数组中。测量使用的内存（参见Runtime）。

然后将它们存储在HashMap中。测量使用的内存。

将第二次使用的内存减去第一次测量的内存，即可得到HashMap的开销。

- JB Nizet

1

不...如果我愿意的话，我可以这样做，但我正在寻求数学上的解释。 - user1086498

对于数学部分，您需要精确了解对象在映射中的存储方式，精确了解引用、数组等在您的JVM上的成本，并执行您在问题中所做的操作。阅读HashMap的源代码和您的JVM文档。 - JB Nizet

我两件事都可以做，但是两者都不一定能回答这个问题。毕竟，我对源代码的阅读可能是错误的，而且我的JVM文档显然可能不适用于其他使用我的程序的人的JVM。 - user1086498

这就是为什么最好的方法是在两个JVM上进行测量。64位JVM消耗的内存与32位JVM不同。如果您不想做数学计算，也不想进行测量，那还剩下什么呢？ - JB Nizet

因为我需要知道实际的计算结果。根据我的第一个猜测，JVM的差异并不重要 - 即使内存使用量增加一倍也没有意义。如果有人知道数学公式，请告诉我，而不是让我去查阅文档。请考虑O(n^2)的开销是很大的，但是O(n)的开销不会很大，除非常数很大。如果有人真正知道内部发生了什么，那么在我的JVM上进行试验就毫无意义了。你知道吗？ - user1086498

计算很简单：检查您的JVM以查看引用成本、int成本、数组成本等，然后添加由JVM使用的HashMap实现的内部结构使用的所有引用、数组、int等使用的内存。 HashMap基本上是一个存储链接列表的数组，希望尽可能少地存储元素（如果一切正常，则为0或1）。它不能是O（n ^ 2）。它是O（n）。 - JB Nizet

0

这个有意义吗？例如，如果里面的数据大约为256mb，那么开销会很重要吗？

绝对不是。在任何情况下，HashMap中1000个对象的开销都不值得担心：如果它们总共每个256mb，那么更不用说了。如果开销是256k，但它不是，那只有1％。不重要。

有一种可靠的方法（除了分析器之外，在某些情况下我发现它们不可靠）可以数学计算它的开销吗？

考虑到我的答案（1），这个问题是无意义的。

- user207421

虽然我已经得到了一个合理的估计方式 - 但无论如何还是感谢你的回答！ - user1086498

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Woot4Moo · Accepted Answer

以下博客文章提供了一些关于该主题的松散数学知识。
这个谷歌代码网站展示了如何完成这些事情。

引用链接以防链接失效：

This is the cheat-sheet I compiled.

To compute the cost of a single (key, value) entry:

    If you use HashMap or ConcurrentHashMap, the cost is 8 words (32 bytes)


 So, consider this example from the javadoc:

   LoadingCache graphs = CacheBuilder.newBuilder()
       .maximumSize(10000)
       .expireAfterWrite(10, TimeUnit.MINUTES)
       .removalListener(MY_LISTENER)
       .build(
           new CacheLoader() {
             public Graph load(Key key) throws AnyException {
               return createExpensiveGraph(key);
             }
           });


The cost of an Entry in this structure this is computed as follows:

    It's a Cache: +12 words
    It uses maximumSize(): +4 words
    It uses expiration: +4 words

Thus, each (key, value) entry would have a footprint of 20 words (thus 80 bytes in a 32bit VM, or 160 in a 64bit one). 

To estimate the overhead imposed in the garbage collector, one could count how many references (pointers) each entry introduces, which the garbage collector would have to traverse to compute object reachability. The same list again, this time only counting references:

    If you use HashMap or ConcurrentHashMap, the cost is 5 references