27

ハッシュの衝突を解決するための Open Addressing と Chaining の違いを知っています。のような基本的なハッシュベースのデータ構造のほとんどは、HashSetJavaHashMapでは主にチェーン技術を使用します。ThreadLocal が実際にプローブ スキームを使用していることを読みました。では、Java でオープン アドレッシングがあまり使用されない理由を理解したいと思います。特別な処理でそれらのセルをマークしなければならないという意味で、そのスキームを使用してレコードを削除するのは難しいということです。ただし、オープン アドレッシング方式ではメモリ要件が低くなるようです。

編集：この設計上の決定の主な理由/理由を理解したいだけです。細かいことはいらない。また、なぜ ThreadLocal があまり一般的でないオープン アドレス指定の手法を使用するのかを知りたいです。この 2 つの回答は関連していると思います。そのため、同じ質問自体で質問することを好みます。

4

1 に答える 1

20

私は現在、特に Doug Leaのメモリ コンパクトな再実装について話し合っHashMapています。HashSetこの特定の質問はまだ出ていませんが、この質問に対する私の最初の考えは次のとおりです...

  • チェーン化されたハッシュ テーブルは、適度に適切に劣化します。負荷率が高い場合でも、ハッシュの衝突が多い場合でも、チェーンはオープン アドレッシングほど速く劣化しません。
  • あなたが言ったように、それremoveは...オープンアドレステーブルでの快適な操作ではありません. 原則として、removeハッシュ テーブルに対する操作は最も一般的ではありませんが、より一般的なアプリケーションがあり、パフォーマンスの低下が見られます。
  • また、データはあまりありませんが、「リンクされた」オープン アドレス ハッシュ テーブルを実装するのは、明らかに難しいのではないかと思います。 LinkedHashMapのサブクラスとして書かれておりHashMap、実装の詳細のほとんどを借用しています。エントリが個別のオブジェクトである場合は、エントリのリンクされたリストを実装する方がいくらか簡単です。その時点で、チェーン実装への道はすでにほとんど進んでいます。
  • 仕様では、この実装にそれらを結びつけるものは何もありません。後でいつでも自由にいじることができます。
  • JDKコレクションライブラリ...メモリ消費を特に優先しないでください。メモリが安い。(これに同意するかもしれないし、同意しないかもしれませんが、これは間違いなく顕著な傾向です。)
于 2012-08-18T16:00:03.577 に答える