Desirable Property of Hash Functions

We will see from the analysis that an ideal hash function is essentially random... it takes a set of keys and sprays them out uniformly along the length of the table.

So, the hash function should look random but be deterministically computable. In crytography, this is called a one-way function (easy to compute h(k) from k, but no real pattern linking k back to h(k)).

Like anti-sorting!


next up previous
Next: ANALYSIS Up: COLLISION RESOLUTION Previous: Linear Probing