I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I wanted to insert something into the table, would I calculate the bucket to place it in using the hash function and then place it in that bucket? How would I go about retrieving that data later on?

  • 1
    $\begingroup$ Have you taken a look at the Wikipedia page on hash tables? $\endgroup$ Apr 6 '18 at 21:23
  • $\begingroup$ Is your question about hashing or about hash tables? $\endgroup$
    – Draconis
    Apr 6 '18 at 22:37

One example of universal hashing's application is perfect hashing. If you know all the keys beforehand, we can obtain $O(1)$ time for search, insert, delete (dynamic perfect hashing exists but is difficult to implement). More concretely we hash all of our values with an initial hash function into our table and keep track of where collisions occurred. For wherever $d>1$ collisions occurred, you build another hash table of size $d^2$. You obtain a hash function for this ($d^2$ size) table by applying universal hashing until you get no collisions.

Universal hashing guarantees that the probability of getting collisions with any two distinct keys is $\leq \frac{1}m$ where $m$ is our table size. Following your universal hash functions $h_{a,b}$ defined above (which is proved to be universal using number theory), we can try various $a,b$ in each $d^2$ size table until we get no collisions.

So to answer your question you just try a bunch of times (usually not too many as shown by probabilistic analysis and universal hashing) until you get a hash function that works for your problem setting and then save that hash function to use later for retrieval, insertion...

To be clear, the cost of utilizing this data structure is $O(1)$ because we only need to compute the first hash function and then the second hash function (we obtained via universal hashing).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.