4

ハッシュマップに 1000 個のオブジェクトを格納しているとしましょう。このハッシュマップを拡張して、そこに格納されているオブジェクトに 3 次元座標をマップできるようにします。内部のオブジェクトは固定サイズです。ハッシュ キーは長整数です。

この構造の予想されるオーバーヘッドを (数学的に) 計算するにはどうすればよいでしょうか?

  1. たとえば、内部のデータが約 256 MB の場合、オーバーヘッドが問題になるほど重要ですか?
  2. オーバーヘッドを数学的に計算するための信頼できる方法はありますか(場合によっては信頼できないことがわかったプロファイラーは別として) 。

ハッシュマップの合計サイズには関心がありません。ハッシュマップを使用するオーバーヘッドのみが発生します。たとえば、int が 10 の場合、1 ピースが 4 バイトなので、40 バイトになります。それらを配列に貼り付けると、12 バイトの一定のオーバーヘッドが発生します。オブジェクト ヘッダーの場合は 8、長さの場合は 4 です。それらを別の構造 (たとえば TreeSet) に配置すると、ツリーにはノードが必要なため、オーバーヘッドは一定ではなくなります。そのため、n はセット内のアイテムの数である n で表されるオーバーヘッドが得られる可能性があります。

私には明らかなことがいくつかありますが、それをここでの出発点として挙げます。

  1. 少なくとも 1000 ロングを保管する必要があります。これらは null 許容型であるため、実際にはオブジェクトです。したがって、使用されている 8 バイトの長さの整数には、8 バイトのオブジェクト ヘッダーもあると仮定します。16nの係数を追加します。
  2. オブジェクトがマップから呼び出されて使用されているかどうかに関係なく、すべてのオブジェクトへの参照も必要です。つまり、オブジェクトごとに 8 バイトが追加されます。代わりにデータ サイズに含めることもできますが、参照はハッシュマップ自体にあるため、オーバーヘッドの一部にするのが最善のように感じます。私の論理は次のとおりです。ハッシュマップからすべてのデータを取り出して変数に格納した場合、これらのデータオブジェクトを削除しない限り、これらの n 参照はハッシュマップにまだ存在しますが、これは行いません。 . オブジェクトのセットは一定ですが、別のキーで再利用される場合があります。
  3. ハッシュマップ自体には 8 バイトのオーバーヘッドがあります。
  4. ハッシュマップは、アイテムの数を内部に格納する必要があるため (またはそう思います!)、4 バイトです。
  5. ハッシュキーが配列にあり、ハッシュキーの順序でソートされていると無知に思います。これは、配列の 12 バイトです。
  6. また、オブジェクトが一致する配列にあり、キーが見つかったときに逆参照すると仮定します。さらに12バイトを推測します。

これにより、多項式が得られます: 36 + 24n

したがって、長いキーを使用すると、1000 個のデータ オブジェクトに対して 24036 バイトのオーバーヘッドが発生すると推測されます。これは取るに足らないオーバーヘッドですが、あなたへの私の質問は、そこに座っているだけで、実際のオーバーヘッドはいくらですか?

2 つ目の有効な質問は、これは JVM ごとにどのくらい異なるかということです。それを理解するためのJVMに依存しない方法はありますか? 私が言いたいことを例証するために、32 ビット オブジェクト ヘッダーしかない JVM を考えてみましょう。配列を見ると、サイズは JVM ごとに異なりますが、配列のオーバーヘッドがその場合は12。

私は、同じバージョンの Java での HashMap の固定実装を想定しています。

ソース コードを読み取ったり、プロファイリングを実行したりすることはできますが、JVM に基づいて誤解を招く結果が生じる可能性があります。状況について私たち二人がまだ知らない情報について、あなたの助けを求めています。おそらく知っている人です。ありがとう！

以下の回答を参照してください。実際の見積もりは次のように表すことができます。

エントリごとに 8 ワード、各 long ごとに 8 バイト、ハッシュマップ オブジェクト ヘッダー用に 8 バイト。

私の現在の環境（32ビットOS）では、1ワード= 4バイトになります。

  • 32 ビット環境で 40n + 8: 1000 エントリで ~ 40k
  • 64 ビット環境で 72n + 8: 1000 エントリの場合は ~ 72k。

そのため、100kバイト未満のようです。

4

3 に答える 3

3

次のブログ投稿では、このトピックに関するいくつかの緩い数学を提供しています。
このgoogle code サイトでは、これらの処理がどのように行われるかについて説明しています。

リンクが腐った場合のリンクの引用: 

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
  1. たとえば、内部のデータが約 256 MB の場合、オーバーヘッドが問題になるほど重要ですか?

絶対にありません。HashMap 内の 1000 個のオブジェクトのオーバーヘッドは、どのような場合でも心配する価値はありません。合計でそれぞれ 256 MB であれば、さらに少なくなります。オーバーヘッドが 256k の場合、実際にはそうではありませんが、それはわずか 1% です。重要ではありません。

  1. オーバーヘッドを数学的に計算するための信頼できる方法はありますか (場合によっては信頼できないことがわかったプロファイラーは別として)。

（1）に対する私の答えを考えると、質問は意味がありません。

于 2012-07-20T10:09:09.297 に答える
0

すべてのオブジェクトを作成して単純な配列に格納するプログラムを作成します。使用メモリを測定します (ランタイムを参照)。

次に、それらを HashMap に格納します。使用メモリを測定します。

最初に測定されたメモリを 2 番目に使用されたメモリから差し引くと、HashMap のオーバーヘッドが得られます。

于 2012-07-19T17:00:33.533 に答える