2009-10-15 8 views
22

私はConcurrentHashMapを構築するためのパラメータについて疑問に思って:ConcurrentHashMapコンストラクタのパラメータ?

  • initialCapacityは、デフォルトでは16である(理解)。
  • loadFactorは、デフォルトで0.75です。
  • concurrencyLevelは、デフォルトでは16です。

私の質問は以下のとおりです。

  • どのような基準は、アップloadFactorまたはダウンを調整するために使用すべきですか?
  • 同時に更新するスレッドの数はどのように設定するのですか?
  • concurrencyLevelを上下に調整するためにはどの基準を使用する必要がありますか?

さらに:

  • 良いハッシュコードの実装の特徴は何ですか? (SOの質問がこれに対処すれば、それにリンクするだけです)

ありがとう!

+0

ありがとうございました。 –

答えて

15

短い答え:マップに入れるマップの数をおおまかに設定し、他のパラメータはデフォルトのままにしておきます。

ロング答えは:

  • 負荷率マップと 予想される要素の数に「バケット」の 数との比です。

  • 0.75は、通常、合理的な妥協点です。つまり、 良いハッシュ関数を使用すると、平均で が約1となることを意味します。6はリダイレクトされ、マップ(またはその図の周り)に 要素が見つかります。

    • 負荷 要因は、要素を見つけるために よりリダイレクトの間の妥協を変更しますが、 少ない無駄space--は0.75を入れ、通常は本当に良い値 で変更します。原則として

    • 、あなたがマップを変更持つことを期待 同時実行スレッド数を するのconcurrencyLevelを設定し、 過大評価が、これは は、私は少しを書きました(メモリを無駄にするよりも 他の悪い影響を持つように表示されません。 ConcurrentHashMap performanceにしばらく前にあなたが興味を持っ している場合)

非公式に、あなたのハッシュ基本的にビットの中に可能な限り多くの「ランダム性」を持たせることを目指すべきである。厳密に言えば、与えられた要素のハッシュコードは、各ビットに約50%の確率で設定する必要があります。実際に例を挙げて説明すると、実際にはわかりやすくなります。私はhow the String hash function worksについて書いたものと、hash function guidelinesというものに興味があるかもしれません。フィードバックは、このようなことのいずれかに不快な歓迎です。

私はまた、実際にはあまりにも妄想的である必要はないということを言います。もしあなたのハッシュ関数がビットのに「妥当な」量の乱数を生成するならば、 OKにしてください。最悪の場合、代表的なデータを文字列に貼り付け、文字列のハッシュコードを取ることは実際にはあまりうまくいきません。

0

loadFactor:実装がハッシュテーブルのサイズを変更することを決定したときに制御します。値が大きすぎるとスペースが浪費されます。値が小さすぎると、高価なサイズ変更操作になります。

concurrencyLevel:指定された数の書き込みスレッドに対して最適化を試みるように実装に指示します。 APIドキュメントによれば、最大10倍になるとパフォーマンスに大きな影響はないはずです。

更新 動作のうち許容同時実行は、内部サイジングのためのヒント として使用される任意 のconcurrencyLevelコンストラクタ引数 (デフォルト16)によって案内されます。表は内部で にパーティション化されており、 を指定すると、同数の 同時更新が競合することなく許可されます。 ハッシュテーブル内の配置は実質的にランダムで なので、実際の の同時性は異なります。理想的には は、 に対応する値を選択して、 が同時にテーブルを変更する数のスレッドを選択する必要があります。 よりもかなり高い値を使用すると、スペースと時間が浪費され、 値が大幅に低くなると、スレッドの競合が発生する可能性があります( )。しかし、 を過大評価し、 のオーダー内で過小評価すると、通常はあまり影響がありません

優れたハッシュコードの実装では、任意の間隔で均等にハッシュ値を配信します。キーのセットが事前にわかっている場合、各キーの固有のハッシュ値を作成する「完全な」ハッシュ関数を定義することが可能です。

0

loadFactorは、デフォルトでは0.75に設定されている、 どんな基準が この上または下を調整するために使用すべきですか?

この仕組みが理解できるようになる前に、ハッシュマップの仕組みを理解しておく必要があります。マップは基本的に一連のバケットです。マップの各値は、そのハッシュコードが何であるかに応じてバケットに入れられます。 loadFactorはバケットが75%以上満杯であれば、地図

のconcurrencyLevelがどのように我々は同時に スレッドを更新 数を確立するか、 デフォルトで16に設定されているの?リサイズする必要があり、意味しますか これを調整するにはどの基準を使用しますか?あなたが同時に地図を修正することを期待し

この

はどのように多くのスレッドを求めている(同時に)ハッシュコードについて

、ジョシュア・ブロックのEffective Java

4

負荷率は、主にハッシュの品質に関連して見ます関数。負荷係数がゼロに近いほど、ハッシュ関数がそれほど大きくなくても衝突する可能性は低くなります。トレードオフは、メモリフットプリントが大きいことです。言い換えれば、HashMapは、別々のハッシュコードごとに別々のバケットにエントリを分散していないので、それらを近接でグループ化しているため、バケットが多いほど分散が広がり、衝突が起こりにくくなります。

要するに、あなたのニーズとマップに保存しているオブジェクトに応じて、読み込み時間を改善したり、メモリを減らしたりするために負荷率を調整することが重要です。

ConcurrencyLevelは実際にアプリケーションによって異なります。アプリケーション内で2つまたは3つのスレッドしか実行していない場合は、そこに移動します。スレッド数が任意のアプリケーションサーバーの場合は、負荷容量と最適化ポイントを理解する必要があります。

良質なハッシュコードの実装は、契約を尊重しながら、できるだけ少ない数の衝突でオブジェクトの潜在的な価値を可能な限り広く分布させます。言い換えれば、HashMap(または場合によってはSet)は、オブジェクトを別々のバケットに分散して検索を高速化することができます。

関連する問題