4

假设我在哈希图中存储了 1000 个对象。这个 hashmap 被扩展为允许我将三维坐标映射到存储在其中的对象;里面的对象有固定的大小。哈希键是一个长整数。

我将如何计算(数学上)这个结构的可能开销?

  1. 例如,如果内部数据约为 256mb,那么开销是否重要?
  2. 有没有一种可靠的方法(除了我发现在某些情况下不可靠的分析器)来数学计算它的开销应该是多少?

我对哈希图的总大小不感兴趣——只有使用哈希图会产生的开销。例如,如果我有 10 个整数,它们是 4 个字节,所以是 40 个字节。如果我将它们放在一个数组中,我会得到 12 个字节的恒定开销 - 对象标头为 8 个字节,长度为 4 个字节。如果我将它们放在另一个结构中(例如 TreeSet),我的开销将不会是恒定的,因为树需要节点 - 所以我可能会得到以 n 表示的开销,其中 n 是集合中的项目数。

有几件事对我来说是显而易见的,我将在这里作为我的起点。

  1. 我需要存储至少 1000 条长条。这些是可为空的类型,因此它们实际上是对象。因此,我假设正在使用的 8 字节长整数也有一个 8 字节的对象头。我将添加一个 16n 的因子。
  2. 我还需要对每个对象的引用,无论该对象是否已从地图中调用并正在使用,这些引用都必须存在;所以这是每个对象额外的 8 个字节。我们可以将其计入数据大小,但由于引用在 hashmap 本身中,我觉得最好将它们作为开销的一部分。我的逻辑如下:如果我从 hashmap 中取出所有数据并将其存储在变量中,那么这些 n 引用仍然存在于 hashmap 中,前提是我没有删除这些数据对象,我不会这样做. 对象集是恒定的,尽管它们可以用不同的键回收。
  3. hashmap 本身有 8 个字节的开销。
  4. hashmap必须存储里面的项目数(或者我认为!)所以这是 4 个字节。
  5. 我会无知地假设哈希键在一个数组中,按哈希键顺序排序。数组有 12 个字节。
  6. 我也会无知地假设对象位于匹配的数组中,当它找到键时它会取消引用。我会猜另外 12 个字节。

这给了我一个多项式方程:36 + 24n

因此,我猜测使用长键的 1000 个数据对象的开销为 24036 字节。这是一个微不足道的开销,但我的问题是,真正的开销是什么,只是坐在那里?


第二个有效的问题是,这从 JVM 到 JVM 有多大不同?有没有任何独立于JVM的方法来解决它?为了举例说明我的意思,考虑一个只有 32 位对象头的 JVM - 当查看数组时,您可能会说,即使大小因 JVM 不同而异,但公平估计数组的开销将变为 8 个字节而不是12 在这种情况下。

我假设 HashMap 跨相同版本的 Java 的固定实现。


我可以尝试阅读源代码或运行分析,但这可能会根据我的 JVM 产生误导性结果。我正在寻求你的帮助——也许是知道的人——提供一些我们都不知道的信息。谢谢!


看下面的答案,实际估计可以表示如下:

每个条目 8 个字,每个 long 加上 8 个字节,以及 hashmap 对象标头的 8 个字节。

在我目前的环境(32 位操作系统)中,1 个字 = 4 个字节。

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

所以它似乎低于 100kbytes。

4

3 回答 3

3

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

在链接腐烂的情况下引用链接:

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
于 2012-07-19T17:22:04.500 回答
0

创建一个程序,在其中创建所有对象并将它们存储在一个简单的数组中。测量使用的内存(参见运行时)。

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

将第一个测量的内存减去第二个使用的内存,你就有了 HashMap 的开销。

于 2012-07-19T17:00:33.533 回答
0
  1. 例如,如果内部数据约为 256mb,那么开销是否重要?

当然不。HashMap 中的 1000 个对象的开销在任何情况下都不值得担心:如果它们总共是 256mb,那就更少了。如果开销是 256k,而事实并非如此,那只会是 1%。不重要。

  1. 有没有一种可靠的方法(除了我发现在某些情况下不可靠的分析器)来数学计算它的开销应该是多少?

鉴于我对(1)的回答,这个问题没有实际意义。

于 2012-07-20T10:09:09.297 回答