C での HashMap の実装

それらの背後にある基本を知っていれば、それほど難しいことではありません。

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

キーを使用してハッシュ テーブルにアクセスする場合、整数を返すカスタム ハッシュ関数を使用してキーを処理します。次に、結果のモジュラスを取得します。これが配列インデックスまたは「バケット」の場所です。次に、ハッシュされていないキーと保存されているキーを照合し、一致する場合は適切な場所を見つけました。

そうしないと、「衝突」が発生し、リンクされたリストをクロールして、一致するまでキーを比較する必要があります。 (一部の実装では、衝突のためにリンク リストの代わりにバイナリ ツリーを使用することに注意してください)。

この高速ハッシュ テーブルの実装を確認してください:

https://attractivechaos.wordpress.com/2009/09/29/khash-h/


最適なアプローチは、予想される鍵の配布と衝突の数によって異なります。衝突が比較的少ないと予想される場合は、どの方法を使用しても問題ありません。多くの衝突が予想される場合、どちらを使用するかは、拡張可能なバケット データ構造を操作することと、再ハッシュまたはプローブすることのコストによって異なります。

しかし、ここに C でのハッシュマップ実装のソース コード例があります


ハッシュマップの主な目的は、データ セットを格納し、一意のキーを使用してほぼ一定時間のルックアップを提供することです。ハッシュマップの実装には 2 つの一般的なスタイルがあります:

  • 個別のチェーン:バケットの配列 (リンクされたリスト) を持つもの
  • オープン アドレッシング:余分なスペースが割り当てられた単一の配列であるため、エントリを隣接するスロットに配置することでインデックスの競合を解決できます。

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

オープン アドレッシングを使用するハッシュマップは、負荷係数が特定のしきい値 (通常は約 0.7) 未満に保たれ、適度に優れたハッシュ関数が使用されている場合に、潜在的なパフォーマンス上の利点があります。これは、潜在的なキャッシュ ミスや、リンク リストに関連する多数の小さなメモリ割り当てを回避し、事前に割り当てられた連続した配列ですべての操作を実行するためです。すべての要素の反復も安価です。問題は、オープン アドレッシングを使用するハッシュマップをより大きなサイズに再割り当てし、理想的な負荷率を維持するために再ハッシュする必要があることです。そうしないと、パフォーマンスが大幅に低下します。負荷率が 1.0 を超えることはありません。

ハッシュマップを作成するときに評価する主要なパフォーマンス指標には、次のものがあります。

  • 最大負荷率
  • 挿入時の平均衝突回数
  • 衝突の分布:不均一な分布 (クラスタリング) は、不十分なハッシュ関数を示している可能性があります。
  • さまざまな操作の相対時間:既存および存在しないエントリの配置、取得、削除

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

https://github.com/DavidLeeds/hashmap