CODEWITHSUNDEEP
algorithmdata-structureshashhashtable
Navneet Srivastava
Navneet Srivastava

Reputation: 963

What is meant by uniform distribution of hash values in Hashing technique

In Hashing, what does this uniform distribution of hash values mean. Please explain in layman's terms using appropriate example.

Upvotes: 2

Views: 6188

Answers (1)

vish4071
vish4071

Reputation: 5277

It simply means that if you have some size of your hash-table (Say n), then if you are hashing k values k<n, then:

A sequence of outputs from the function must appear to be a random sequence, even if the input numbers are sequential

Also, fundamental thing for your hash function should be to minimize collisions obviously, but at the same time, for a skewed input, output from hash-function should be distributed.

EDIT:

As asked, here is what uniform distribution means. Say, if your size of hash-table is n and you push k (<n) elements to it, then, in every bucket of n/k in hash table, there should be an element. Also, if k=r*c, in every bucket of size n/c in hash table, there should be r elements.

Obviously, perfect uniform distribution is not possible...but output distribution should not be skewed.

Upvotes: 1

Related Questions