C ++ STLにあるように、Cでハッシュマップを最初から作成するにはどうすればよいですか？
どのパラメータが考慮され、ハッシュマップをどのようにテストしますか？のように、ハッシュマップが完成したと言う前に実行するベンチマークテストケースは何でしょうか？
質問する
144194 次
4 に答える
64
それらの背後にある基本を知っているなら、それはそれほど難しいことではないはずです。
通常、リンクリストを作成するためのオプションのポインタを使用して、キーと値を含む「バケット」と呼ばれる配列を作成します。
キーを使用してハッシュテーブルにアクセスする場合、整数を返すカスタムハッシュ関数を使用してキーを処理します。次に、結果のモジュラスを取得します。これは、配列インデックスまたは「バケット」の場所です。次に、ハッシュされていないキーと保存されているキーを確認し、一致する場合は適切な場所を見つけました。
そうしないと、「衝突」が発生し、リンクリストをクロールして、一致するまでキーを比較する必要があります。（一部の実装では、衝突にリンクリストの代わりにバイナリツリーを使用することに注意してください）。
この高速ハッシュテーブルの実装を確認してください。
于 2009-05-08T05:55:41.213 に答える
5
最善のアプローチは、予想されるキーの分布と衝突の数によって異なります。衝突が比較的少ないと予想される場合は、どちらの方法を使用してもかまいません。多数の衝突が予想される場合、どちらを使用するかは、拡張可能なバケットデータ構造の再ハッシュまたはプロービングのコストと操作のコストによって異なります。
しかし、これがCでのハッシュマップ実装のソースコード例です。
于 2009-05-08T05:52:48.410 に答える
3
ハッシュマップの主な目的は、データセットを保存し、一意のキーを使用してほぼ一定時間のルックアップを提供することです。ハッシュマップの実装には、次の2つの一般的なスタイルがあります。
- 個別のチェーン：バケットの配列を持つチェーン（リンクリスト）
- オープンアドレッシング：エントリを隣接するスロットに配置することでインデックスの衝突を解決できるように、余分なスペースが割り当てられた単一の配列。
ハッシュマップのハッシュ関数が不十分な場合、未使用の可能性のあるスロットにストレージを事前に割り当てることが望ましくない場合、またはエントリのサイズが可変である場合は、個別のチェーンを使用することをお勧めします。このタイプのハッシュマップは、負荷率が1.0を超えた場合でも、比較的効率的に機能し続ける可能性があります。明らかに、リンクリストポインタを格納するために各エントリに追加のメモリが必要です。
オープンアドレッシングを使用するハッシュマップは、負荷率が特定のしきい値（通常は約0.7）未満に保たれ、適度に優れたハッシュ関数が使用される場合に、潜在的なパフォーマンス上の利点があります。これは、潜在的なキャッシュミスや、リンクリストに関連付けられた多くの小さなメモリ割り当てを回避し、すべての操作を連続した事前に割り当てられた配列で実行するためです。すべての要素の反復も安価です。キャッチは、オープンアドレッシングを使用するハッシュマップをより大きなサイズに再割り当てし、理想的な負荷率を維持するために再ハッシュする必要があることです。そうしないと、パフォーマンスが大幅に低下します。それらの負荷率が1.0を超えることは不可能です。
ハッシュマップを作成するときに評価するいくつかの主要なパフォーマンスメトリックには、次のものが含まれます。
- 最大負荷率
- 挿入時の平均衝突数
- 衝突の分布：不均一な分布（クラスタリング）は、ハッシュ関数が不十分であることを示している可能性があります。
- さまざまな操作の相対時間：既存および存在しないエントリの配置、取得、削除。
これが私が作成した柔軟なハッシュマップの実装です。衝突解決にはオープンアドレス法と線形プロービングを使用しました。
于 2016-11-11T10:50:19.887 に答える
1
オーバーフローを処理するメカニズムは、オーバーフローエントリの単純なリンクリスト以外にもあります。たとえば、大量のメモリを浪費します。
どのメカニズムを使用するかは、とりわけ、ハッシュ関数を選択でき、複数を選択できるかどうかによって異なります（たとえば、衝突を処理するためのダブルハッシュを実装するため）。アイテムを頻繁に追加する予定の場合、またはマップが埋められた後は静的である場合。アイテムを削除するかどうか。..。
これを実装する最良の方法は、最初にこれらすべてのパラメーターについて考え、次にそれを自分でコーディングするのではなく、成熟した既存の実装を選択することです。Googleにはいくつかの優れた実装があります-例：http ：//code.google.com/p/google-sparsehash/
于 2009-05-08T06:32:21.937 に答える