# How to actually implement universal hashing?

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?

• Have you taken a look at the Wikipedia page on hash tables? Apr 6 '18 at 21:23
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.
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).