Loading...
The art of scattering data: How to design and choose the perfect hash function.
Section 0 of 0
The art of scattering data: How to design and choose the perfect hash function.
Experiment with different mapping strategies.
h(k) = k mod mSame key must always yield the same index.
Every bucket should have the same probability of being used.
Ideally O(1) time to compute index.
Similar keys should hash to very different indices.
In the Division Method, if you pick $m$ as a power of 2, the hash only depends on the lower bits of the key. This is bad!
The Golden Rule: Always pick a Prime Number for your table size that isn't too close to a power of 2.