The Basics of Universal Hashing How to Ensure Accessibility

Question

to my current understanding. Universal Hashing is a method in which a hash function is randomly selected at runtime to ensure reasonable performance for any input.

I understand that we can do this to prevent the manipulation of someone intentionally choosing malicious input (the ability to know a deterministic hash function).

My question is this: isn't it true that we still need to guarantee that the key will be mapped to the same address every time we use it? For example, if we want to get information, but the hash function is randomly selected, how can we guarantee that we can return to our data?

Answer 1

A universal hash function is a family of different hash functions that have the property that with a high probability two randomly selected elements from the universe will not collide regardless of which hash function is selected. Typically, this is achieved because the implementation selects a random hash function from the family of hash functions for use within the implementation. Once this hash function is selected, the hash table works as usual - you use this hash function to calculate the hash code for the object, and then place the object in the appropriate place. The hash table must remember the choice of the hash function that it made and must constantly use it throughout the program, because otherwise (as you noticed) it will forget where it matched each element.

Hope this helps!