Cでの<string、string>の実装

Question

なんらかの理由で、これを実装する必要があり、libsを使用できません。 マップを高速にするには、まずキーを整数にマップし、その整数を内部キーとして使用します。次にマップを実装します。これは私にマッピング関数を与えます。しかし、文字列キーを使用して内部整数キーを計算すると、別の文字列から同じ整数を取得することがあります。どうすれば問題を解決できますか？

Answer 1

これは避けることはできません。整数よりも多くの文字列が存在するため、ハッシュの衝突が差し迫っています。ハッシュマップを読み上げる - それは明示的に衝突を考慮に入れたデータ構造であり、それらを回避します。

Answer 2

これは衝突として知られていますが、最も簡単なのは、ハッシュマップ内の各バケットを同じハッシュのアイテムのリストにすることです。次に、にを入力するだけで、あなたが探しているアイテムを見つけるまでリストを繰り返し処理するだけで済みます。

Answer 3

マップデータ構造と「衝突」は分離できません。あなたの実装を開始した方法は罰金だ、ここにあなたが衝突を処理する方法は次のとおりです。

マップ

1. に新しいエントリを追加するhashcode
keyのハッシュコードから計算 index（多かれ少なかれを計算 index = hashcode value％ size of keyset）
3. keyset[index]がヌルでない場合
   1. keyset [index]！= key（つまり、文字列を、使用のstrcmp）indexモジュラスsize of keysetをインクリメントするために、その後、後藤3
4. はkey
用マップ
1. 計算hashcodeから値を取得する

entryset[index]にvalueを置きます
5. を計算するindex ashcode（多かれ少なかれindex = hashcode value% size of keyset）
6. keyset[index]がnullでない場合
   1. キーセット[インデックス]！=キー（つまり場合。文字列に対して、使用のstrcmp）をindexモジュラスsize of keysetをインクリメントジャンプ3
7. リターンentryset[index]

マップからエントリを削除しているヌルリターンヌル

keyset[index]場合

1. keyの場合hashcodeを計算する場合
0ハッシュコードから
2. 計算index（多かれ少なかれindex = hashcode value% size of keyset）
3. keyset[index]がnullでない場合
   1. かのキーセット[インデックス]！=キー（すなわち。文字列のため、strcmpのを使用）indexモジュラスsize of keysetをインクリメントし、その後、後藤3
4. は、あなたが見ることができるように、あなたが機能int findIndexFromKey(Map *map, char *key);に3ステップ1を入れて、最も可能

をnullにkeyset[index]とentryset[index]を設定もちろん

** EDIT **

行われる作業のため、また、あなたのメートルかどうかを確認する必要があります新しいエントリを追加する前に（またはその間に）pが満杯になっていない場合は、無期限にループします。