同じハッシュと同じキーがどのように処理されるのですか？

Question

この質問は、プログラミング言語に固有のものではありません。私はより一般的なロジックに興味があります。

一般的に、アソシエイティブマップはキーを取得し、値にマップします。私が知る限り、実装ではキーが一意である必要があります。それ以外の場合は値が上書きされます。よかった。

上記のことは、いくつかのハッシュ実装によって行われるものとします。 2つのDIFFERENTキーが同じハッシュ値を取得するとどうなりますか？私は、そのキーがハッシュの結果であるインデックスを持つ基本的な配列の形でこれを考えています。複数のユニークキーが同じ値にマップされる可能性はありますか？もしそうなら、そのような実装はどのようにこれを処理しますか？ どのように扱いますか同じハッシュと異なる取り扱い同じキー？ 同じキーの結果は上書きされ、同じハッシュ値を保持するためのHAS。
私は衝突によるハッシングを理解しているので、私は連鎖とプロービングを知っています。実装は、特定のインデックスにハッシュされた現在の値を反復処理し、キーが同じかどうかを判断しますか？
私はこれらのリンクに出くわした答えを探していたが：
1. What happens when a duplicate key is put into a HashMap?
2. HashMap with multiple values under the same key
しかし彼らは私の質問に答えていません。同じハッシュと同じキーを区別するにはどうすればよいですか？

Answer 1

キーを比較します。 、のみハッシュ関数は何の平等機能与えられないとすることができた場合

bool equal(Key key1, Key key2); 
int hash(Key key); 

：あなたは、ハッシュマップのオブジェクト指向の実装を見れば、あなたは彼らが通常の2つの方法は、キータイプに実装する必要があることを見つけるだろうハッシュマップは、言語のデフォルトの等価性に基づいて制限されます。これは、キーが異なる平等関数と比較される必要がある場合があるため、必ずしも望ましいとは限りません。たとえば、キーが文字列の場合、アプリケーションは大文字と小文字を区別しない比較を行う必要があり、ハッシュ関数の前に小文字に変換され、大文字小文字を無視する等価関数に変換されます。

ハッシュマップは、対応する各値の横にキーを格納します。ハッシュマップへの参照は、一致するハッシュを見つけた後にキーを比較し、そのキーが実際に一致することを検証する必要があります。

たとえば、各バケットにリストを格納する非常に単純なハッシュマップの場合、リストは（キー、値）のペアのリストになり、ルックアップは一致を見つけるまで各リストエントリのキーを比較します。擬似コード内：

Array<List<Pair<Key, Value>>> buckets; 
Value lookup(Key k_sought) { 
    int h = hash(k_sought); 
    List<Pair<Key, Value>> bucket = buckets[h]; 
    for (kv in bucket) { 
     Key k_found = kv.0; 
     Value v_found = kv.1; 
     if (equal(k_sought, k_found)) { 
      return v_found; 
     } 
    } 
    throw Not_found; 
} 

Answer 2

インデックスからキーが何であるかを知ることはできません。したがって、キーについての情報を見つけるために値を反復処理することはできません。 0回の衝突を保証するか、またはインデックスを与えるためにハッシュされた情報を格納する必要があります。

構造体に値が格納されている場合、同じキーまたは同じハッシュを持つかどうかを判断する方法はありません。知っている価値と一緒に鍵を保管する必要があります。