4

使用したいキーが一意であることが保証されている場合 (または、少なくともキーが一意であると仮定できる場合)、「バニラ」ConcurrentHashMapを使用すると最高のパフォーマンスが得られますか、またはハッシュ関数または put メソッドを使用する必要がありますか?不必要なハッシュを避けるために変更されますか?

また、数値キーには、数値以外のキー (適切なハッシュ関数を使用した文字列や POJO など) よりもパフォーマンス上の利点がありますか?

4

5 に答える 5

8

コメントで既に述べたように、スレッドセーフな側面が必要ない場合は、使用しないでくださいConcurrentHashMap。

絶対に最高のパフォーマンスが必要な場合は、キーをインターンしてIdentityHashMapを使用することを検討してください。これにより、オブジェクトのハッシュの計算が回避され（コメントで述べたように、equals評価される必要がなくなります）、代わりに参照自体がハッシュであると想定されます。

同じキーの 2 つのインスタンスが同じオブジェクトであることを確認する必要があることに注意してください (たとえば、オブジェクトの等価性だけでなく、参照の等価性も保証する必要があります)。すべてのキーをインターンすることは、これを達成するための 1 つのアプローチです。

実装上の注意: これは、Sedgewick と Knuth によるテキストの例で説明されているように、単純な線形プローブ ハッシュ テーブルです。配列はキーと値を交互に保持します。(これは、個別の配列を使用するよりも、大きなテーブルの局所性が優れています。) 多くの JRE 実装と操作の組み合わせでは、このクラスは HashMap (線形プローブではなくチェーンを使用) よりも優れたパフォーマンスをもたらします。

すべてのキーを知っている場合は、おそらく完全ハッシュも検討できますか? それとも単純な配列構造にマップしますか?

于 2011-07-12T12:45:35.510 に答える
1

私が使用したいキーが一意であることが保証されている場合（または少なくともキーが一意であると仮定できる場合）、「バニラ」ConcurrentHashMapを使用すると最高のパフォーマンスが得られます。

通常、が潜在的な同時実行のボトルネックであるConcurrentHashMap場合に使用します。Mapアプリケーションがシングルスレッドの場合、または競合がない場合は、ConcurrentHashMapよりも遅くなりHashMapます。

または、不必要なハッシュを回避するために、ハッシュ関数またはputメソッドを変更する必要がありますか？

ハッシュ関数は、ハッシュテーブルの「プローブ」ごとに1回評価されます。たとえば、getまたはput操作ごとに1回。結果をキャッシュすることでハッシュ関数のコストを削減できますが、これにはキーオブジェクトごとに4バイトの追加ストレージが必要になります。キャッシングが価値のある最適化であるかどうかは、以下に依存します。

  • ハッシュの相対コストをアプリケーションの他の部分と比較すると、
  • それに対する呼び出しの割合は、hashCode()実際にはキャッシュされた値を利用します。

これらの要因は両方とも、アプリケーション固有のものです。

（ちなみに、ハッシュ値としてIDハッシュコードを使用するための長期的なコストも4バイトの余分なストレージです。）

また、数字キーには、非数字キー（適切なハッシュ関数を使用した文字列やPOJOなど）よりもパフォーマンス上の利点がありますか？

ハッシュ関数は数値の場合は安価になる可能性がありますが、それが価値があるかどうかは、数値キーを使用することのアプリケーション固有の欠点があるかどうかによって異なります。また、上記のように、相対的なコストはアプリケーション固有のものです。たとえば、のコストはString.hashCode()ハッシュされる文字列の長さに比例します。

于 2011-07-12T13:06:56.967 に答える
1

ConcurrentHashMap は、HashMap 実装の中で最も高価です。これは、スレッドセーフであるためです。

すべてのマップには一意のキーが必要なので、これは当然のことです。

TLongHashMap などのプリミティブをサポートするコレクションを使用する場合、数値を使用するとパフォーマンスが向上しますが、カスタム ハッシュ マップを使用すると、はるかに高速に処理できる場合があります。

http://vanillajava.blogspot.com/2011/07/low-gc-in-Java-using-primitives.htmlから

Test                                    Performance Memory used
Use Integer wrappers and HashMap        71 - 134 (ns)   53 MB/sec
Use int primitives and HashMap          45 - 76 (ns)    36 MB/sec
Use int primitives and FastMap          58 - 93 (ns)    28 MB/sec
Use int primitives and TIntIntHashMap   18 - 28 (ns)    nonimal
Use int primitives and simple hash map   6 - 9 (ns)     nonimal
于 2011-07-12T12:46:05.947 に答える
0

Java の HashMaps は、最終的にEntry<K,V>、K のハッシュコードを使用して、エントリが格納されている配列内のスロットを決定する配列によってサポートされます。

使用される配列のサイズ (通常は 16 から始まる) は、可能なハッシュコードの数 (2^32 ~= 40 億) よりもはるかに小さいため、ハッシュコードが一意であっても、この配列で衝突が発生することは間違いありません。

hashcode() メソッドが高速である限り、キーとして使用される型に違いはありません。hashcode() メソッドは何度も呼び出される可能性があるため、遅い場合はオブジェクトの内部にキャッシュできます。

于 2011-07-12T12:49:03.313 に答える
0

マルチスレッドでアクセスする ConcurrentHashMap インスタンスマップがあります。以下のコードスニペットを参照してください。これらはどうですか？

Iterator<String> it = new TreeSet<String>(map.keySet()).iterator();
            while(it.hasNext())
            {
                id = it.next();
                synchronized(map)
                {
                    msg = map.get(id);
                    if(msg != null)
                        map.remove(id);
                }
                if(msg != null)
                listener.procMessage(msg);
            }
于 2011-07-15T11:05:32.717 に答える