c - Cでダブルリンクリストノードをハッシュするには?

Question

私はデータ構造を実装しています。項目が範囲内にある二重連結リスト。O（1）にアイテムが存在するかどうかを調べたい。このために、キーがアイテムになり、値がノードになるノードをハッシュしたいと思います。

Java には、この種の機能をサポートする組み込み関数があります。

編集: 要するに、CでhashMapのようなものが欲しい.

Cで実装するにはどうすればよいですか？

Answer 1

キーと値を含む "buckets" という配列を作成し、オプションのポインターを使用してリンク リストを作成します。

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

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

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

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

Answer 2

リンクされたリストにアイテムを保存している場合、それらをハッシュに保存して封じ込めテストを行うことも...次善のようです。最初はハッシュ テーブルを使用し、サポートされていない操作 (O(1) 封じ込めテスト) が必要な場合は、リンク リストの使用を停止します。