HashMapを実装する

Question

Cでゼロからハッシュマップを作成するにはどうすればいいですか？ どのようなパラメータが考慮され、どのようにハッシュマップをテストして、どれくらいうまくいくと思いますか？あなたのハッシュマップが完成する前に実行する必要のあるベンチマークテストケースと同じように。

Answer 1

のソースコードの例です。

通常、キーと値を含む「バケット」と呼ばれる配列を作成し、オプションのポインタを使用してリンクリストを作成します。

キーを使用してハッシュテーブルにアクセスすると、整数を返すカスタムハッシュ関数を使用してキーを処理します。結果のモジュラスを取ると、配列インデックスまたはバケットの位置になります。次に、格納されているキーでunhashedキーをチェックし、一致する場合は正しい場所を見つけました。

それ以外の場合は、「衝突」しています。リンクされたリストをクロールし、一致するまでキーを比較する必要があります。 （いくつかの実装では、衝突のためにリンクされたリストの代わりに2分木を使用することに注意してください）。

この高速なハッシュテーブルの実装をチェックアウト：

http://attractivechaos.awardspace.com/khash.h.html

Answer 2

最適なアプローチは、予想される鍵の配布と番号 の衝突に依存します。比較的少数の衝突が予想される場合は、実際にはどちらの方法を使用しても問題ありません（ ）。多くの衝突が予想される場合は、再ハッシュまたはプロービングと拡張可能なバケットデータ構造の操作のコストに応じて使用されます。ここ

しかし、あなたはそれらの後ろの基本を知っていれば、それはあまりにも難しいことではありませんまあAn Hashmap Implementation in C

Answer 3

例えばオーバーフローエントリのシンプル志向のリンクリストよりオーバーフローを処理するための他のメカニズムがあります。多くのメモリを無駄にする。

どのメカニズムを使用するかは、ハッシュ関数を選択し、可能な場合は複数選択できます（衝突を処理するためのダブルハッシュなど）。アイテムを頻繁に追加する予定がある場合、または地図が一度塗りつぶされた場合は静的です。アイテムを削除するかどうかを判断するには、 ...

これを実装する最良の方法は、まずこれらのすべてのパラメータについて考えてから、自分でコードを作成するのではなく、成熟した既存の実装を選択することです。 Googleにはいくつかの優れた実装があります。 http://code.google.com/p/google-sparsehash/

Answer 4

ハッシュマップの主な目的は、データセットを保存し、固有のキーを使用してデータセットをほぼ一定の時間で検索することです。

• セパレートチェーン：：ハッシュマップの実装の2つの一般的なスタイルがあります
• オープンアドレッシングバケットの配列（リンクリスト）との1：余分なスペースに割り当てられた単一のアレイは、インデックス衝突が置くことによって解決することができるので、隣接するスロットに入る。

ハッシュマップのハッシュ関数が不十分であり、使用されていないスロットのためにストレージを事前に割り当てることは望ましくない場合や、エントリのサイズが可変である可能性がある場合は、このタイプのハッシュマップは、負荷係数が1.0を超えても比較的効率的に機能し続けることがあります。明らかに、リンクされたリストポインタを格納するためには、各エントリに余計なメモリが必要です。

オープン・アドレッシングを使用するハッシュ・マップは、負荷率が特定のしきい値（一般に約0.7）以下に保たれ、合理的に良好なハッシュ関数が使用される場合、潜在的なパフォーマンス上の利点があります。これは、潜在的なキャッシュミスやリンクされたリストに関連付けられた多数の小さなメモリ割り当てを回避し、連続した事前割り当ての配列ですべての操作を実行するためです。すべての要素を通る反復も安いです。キャッチは、オープンアドレスを使用するハッシュマップは、より大きなサイズに再割り当てし、理想的な負荷要因を維持するために再ハッシュしなければならないか、または大幅なパフォーマンスの低下に直面することです。負荷率が1.0を超えることは不可能です。

ハッシュマップを作成する際に評価するためにいくつかの主要なパフォーマンス指標が含まれます

：衝突の

• 最大負荷率
• 平均衝突回数挿入に
• 配布：偏在（クラスタリング）は、貧しい人々を示している可能性がありハッシュ関数。
• さまざまな操作の相対時間：既存エントリと存在しないエントリのput、get、remove。

私が作成した柔軟なハッシュマップの実装です。私は衝突解決のためにオープンアドレッシングとリニアプロービングを使用しました。

https://github.com/DavidLeeds/hashmap