良いハッシュ関数とは何でしょうか? 大学のデータ構造のコースでハッシュ関数とその応用をたくさん見てきましたが、良いハッシュ関数を作るのはかなり難しいということがほとんどでした。衝突を避けるための経験則として、教授は次のように言っていました。
function Hash(key)
return key mod PrimeNumber
end
(mod は C や類似言語の % 演算子です)
素数をハッシュ テーブルのサイズにします。これは衝突を回避するのにやや良い関数であり、高速であることはわかりますが、どうすればもっと良いものを作ることができるでしょうか。数値キーに対して文字列キーのハッシュ関数の方が優れているものはありますか。
ベストアンサー1
ユニバーサル ハッシュには「良いハッシュ関数」というものはありません (編集者注: 「ユニバーサル ハッシュ」というものがあることは知っていますが、私が言いたいのはそういうことではありません)。状況に応じて、ハッシュの品質はさまざまな基準で決まります。2 人がすでに SHA について言及しています。これは暗号ハッシュであり、おそらくあなたが言っているハッシュ テーブルにはまったく適していません。
ハッシュテーブルにはさまざまな要件があります。しかし、異なるデータ型はハッシュできる情報も異なるため、普遍的に優れたハッシュ関数を見つけるのは困難です。経験則として、以下を考慮するとよいでしょう。全て型が保持する情報は平等に扱われます。これは必ずしも簡単ではなく、可能でもありません。統計上の理由 (したがって衝突) から、問題空間、つまりすべての可能なオブジェクトに適切に分散させることも重要です。つまり、100 から 1050 までの数字をハッシュする場合、最上位桁がハッシュで大きな役割を果たさせるのは良くありません。オブジェクトの約 90% では、この桁は 0 になるからです。最後の 3 桁でハッシュを決定することの方がはるかに重要です。
同様に、文字列をハッシュする場合、すべての文字を考慮することが重要です。ただし、すべての文字列の最初の 3 文字が同じであることが事前にわかっている場合は除きます。その場合、これらを考慮するのは無駄です。
これは実際に私がクヌースの言うことを読むことを勧めるケースの一つですコンピュータプログラミングの芸術、第3巻。ジュリアン・ウォーカーのハッシュの芸術。