この質問はかなり長い間私を悩ませてきました。今日、ハッシュ テーブルに関連する詳細な記事を読みました。実装例を確認せずに、ハッシュ テーブルをゼロから作成する方法を試してみました。
セパレート チェーンメソッドは、ハッシュ テーブルを実装するというアイデアを与えてくれました。データ構造の経験がある人なら誰でもこの質問を冗談だと思うかもしれませんが、私は初心者であり、コードに直接飛び込むことなく、実装の効率について話したいと思いました。それは効率的でしょうか、それともこれよりも優先される他の基本的なアイデアはありますか?
クローズド アドレッシングを使用する別の方法として、内部データ構造に赤黒ツリー/std::map やヒープ ツリーなどのセルフ バランシング バイナリ サーチ ツリーを使用したり、別のハッシュ アルゴリズムを使用した別のハッシュ マップを使用したりすることもできます。
オープン アドレッシングを使用する場合、リニア プロービングの別の代替手段として、二次プロービングとダブル ハッシングがあります。カッコウハッシュ、ホップスコッチハッシュなど、あまり一般的ではない戦略もあります。
ハッシュ テーブルを実装する際の重要なポイントは、適切なハッシュ アルゴリズム、サイズ変更戦略 (負荷係数)、および衝突解決戦略を選択することです。各アプローチにはトレードオフがあるため、最適な戦略は予想されるワークロードのタイプに大きく依存します。
まず、boost ライブラリに実装されているいくつかのハッシュ マップのソース (またはドキュメント) を覗いてみるとよいと思います。unordered_map と呼ばれます。（リンクはこちら）
これらの実装について知らず、ハッシュを使用したいと考えていて、それが STL ではないためにイライラしている限り、独自の高速データストアを作成することに興味をそそられます。
しかし、現在、ハッシュマップの実装はゲームから外れているため、C++ 11 の STL には unordered_map があります。もっと面白いものがたくさんあることがわかります。
注: 個別の連鎖はバケット ハッシュと呼ばれます。実際、ブーストはバケット ハッシュを使用します。このリンクを参照してください。たぶん、いくつかのパフォーマンス比較を調べることができます。パフォーマンスを行う人は、十分に優れた実装を作成する可能性があります。