リンクされたリストの配列を使用したハッシュテーブルの実装

Question

この質問はかなり長い間私を悩ませていましたが、今日はハッシュテーブルに関する詳細な記事を読んだことがあります。 の実装例を確認せずに私は最初からハッシュテーブルを書くためのショットを与えたかった。

個別チェーンメソッドは、私にハッシュテーブルを実装する考えを与えました。データ構造の経験がある人なら誰でもこの質問を冗談と考えるかもしれませんが、私は初心者です。コードを直接ダイビングすることなく、実装の効率について話したかったのです。それが効率的か、それとも他の根本的な考え方がこれよりも好まれるだろうか？

Answer 1

私は最初に、ブーストライブラリで実装されたいくつかのハッシュマップのソース（またはドキュメント）を覗くことができます。 unordered_mapと呼ばれます。 (link is here)

これらの実装について知りませんし、ハッシュを使用してSTLにないために迷惑をかけている限り、自分の高速データストアを作成することに興味があります。
しかし、ハッシュマップを実装することは、C++ 11がそのSTLでunordered_mapを持っているほどのものです。あなたはそこにもっと興味深いものがたくさんあることがわかります。

注：別の連鎖をバケットハッシュと呼びます。実際には、ブーストはバケットハッシュを使用します（this linkを参照）。たぶん、いくつかのパフォーマンスの比較を調べることができます。 perfは十分な実装を書くでしょう。

Answer 2

閉じたアドレッシングを使用すると、自己平衡バイナリ検索ツリーを使用することもできます。 red-black tree/std :: mapまたはヒープツリー、内部データ構造、または異なるハッシングアルゴリズムを使用した別のハッシュマップ。

open addressingを使用すると、線形プロービングの別の代替案は、2次プロービングとdouble hashingです。また、鳩のハッシュ、ホップスコッチのハッシュなどの一般的ではない戦略もあります。

ハッシュテーブルを実装する際のポイントは、適切なハッシュアルゴリズム、サイズ変更戦略（負荷係数）、および衝突解決戦略を選択することです。最適な戦略は、各アプローチのトレードオフがあるため、期待しているワークロードのタイプに大きく依存します。