与えられたハッシュ関数はなぜ貧弱なハッシュ関数ですか？

Question

ハッシュテーブルがインデックス0〜HASHSIZE-1の配列であるとします。この関数は正しい範囲の値を返し、実行時エラーを生成しません。渡されたStringに少なくとも2文字が含まれているとします。なぜそれは貧弱なハッシュ関数ですか？

public static int hash(String key) { 
    return (key.charAt(0) 
      + key.charAt(1) 
      + key.charAt(key.length()-1) % HASHSIZE; 
} 

Answer 1

ハッシュ関数の品質は、期待されるキーの集まりの中で作成する衝突の数によって異なります。良い関数は、異なるキーが同じハッシュコードを生成しにくい状況を作ります。

この手法の品質は、使用されているキーの予想される長さによって異なります。長さ3のキーでは、これは完全に許容される方法ですが、ハッシュは文字の順序に基づいて変化しないため、理想的ではありません。

長さが10のキーの場合、この方法は、同じ文字の末尾に同じ文字のペアから始まるすべてのキーの衝突を生成します。 2つの最初の文字と最後の文字の組み合わせが頻繁に繰り返されると、衝突が発生し、このハッシュ関数の有用性が低下します。