algorithm - ハッシング技術におけるハッシュ値の一様分布とは

Question

Hashingでは、ハッシュ値のこの均一な分布は何を意味しますか。適切な例を使用して、素人の言葉で説明してください。

ありがとうございました

Answer 1

これは単純に、ハッシュテーブルのサイズがある程度 (Say n) で、k値をハッシュしている場合、次のことを意味しますk<n。

入力数値が連続していても、関数からの出力のシーケンスはランダムなシーケンスのように見えなければなりません

また、ハッシュ関数の基本的なことは、明らかに衝突を最小限に抑えることですが、同時に、歪んだ入力の場合、ハッシュ関数からの出力を分散する必要があります。

編集：

尋ねられたように、これが一様分布の意味です。たとえば、ハッシュ テーブルのサイズがで、そこに要素をnプッシュする場合、ハッシュ テーブルk (<n)のすべてのバケットにn/k要素が存在するはずです。また、ハッシュテーブルk=r*cのサイズのすべてのバケットに要素n/cがあるはずです。r

明らかに、完全に均一な配布は不可能です...しかし、出力の配布は偏ってはなりません。