誰でもハッシュの品質を理解していますか？

Question

ハッシュの「品質」は、ランダムなハッシュに必要な予想される数に対して、すべての要素に一度アクセスするのに必要な比較の合計数として定義されます。値は100％を超えることができます。

比較の合計数は、各バケット内のエントリ数の平方和に等しくなります。 「< N」「< K」>バケットに>キーのランダムなハッシュについては、期待値は次のとおりです。まさにハッシュの品質が

n + n (n - 1)/2 * k 

何？

Answer 1

これは、ハッシュが「均等に分散されている」ための尺度です。理想的には、ハッシュ関数はすべてを独自のバケットに配置しますが、そのバケットを複数持つことはできません（ハッシュの衝突があっても、別々の値が同じバケットに残ります）。

多くの要素を含むバケットを使用すると、バケツのパフォーマンス（理想的にはバケットを上げてそこの単一の要素を調べる）が低下します。そのような場合は、すべてを線形的に処理する必要があります。

100％の品質は、ランダムなデータで埋め込まれたハッシュに期待されるものです。その場合、すべてのバケツが同じに満ちている必要があります。 100％を超えると、データが不均等にハッシュされ、ルックアップに時間がかかります。