# Universal Hashing

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input.

I understand we may do this e.g. in order to prevent manipulation by somebody choosing malicious input deliberately (a possibility of a deterministic hash function is know).

My Question is the following: Is it not true, that we still need to guarantee that a key will be mapped to the same address every time we hash it ? For instance if we want to retrieve information, but the hash function is chosen at random, how do we guarantee we can get back at our data ?

-

Once the hash function has been chosen for a given key, the key ought to remain in that slot. The whole point of a class of universal hash functions is that the runtime for data retrieval is expected to be significantly less than the worst case in a basic hash using chaining. Specifically, it can be shown that the expected length of the linked list corresponding to an arbitrary key is equal to $1+\frac{n}{m},$ where $n$ is the number of keys and $m$ is the number of slots (cf. Cormen et. all.) Perhaps I don't fully understand your question though.

-
so essentially somewhere we have to store for each key that has been inserted previously which hash function is to be used for it in case we need to work with it later ? i.e. it s chosen randomly at the first go, but deterministic thereafter for retrieval ? – Beltrame Jan 27 '12 at 23:54
A well-designed perfect hashing scheme will allow for "rehashing" - in the event that the search procedure notices too many collisions, it will recompute the values - but in principal that is correct. – user17794 Jan 28 '12 at 1:26

Yes, the hash table handler must guarantee that it goes to the same address when it tries to find data -- the same address that that hash table handler used when it stored that data in the hash table. So it must use the same hash function both times.

If hypothetically the hash table handler were to roll the dice and pick a fresh new random hash function for every new data item that came in ... well, as you pointed out, that would cause problems.

Each hash table is associated with one and only one hash function(*). Every key used to store data in that hash table was hashed using that one hash function. Typically the hash table handler uses one chosen hash function for millions of keys.

Many hash table handlers periodically switch from one hash function to some other new hash function. Many hash table handlers -- whether they use universal hashing or not -- switch every time the number of data items stored in the hash table doubles. In addition, as Tim Duff pointed out, hash table handlers that use that use universal hashing also switch when they observe too many collisions. When a hash table handler that use that uses universal hashing decides it is time to switch (for either reason), the hash table handler rolls the dice and picks a new random hash function.

Every time the hash function changes, the hash table handler moves each and every data item out of the old address (the address indicated by the old hash function) and into the new address (the address indicated by the new hash function). Once all that shuffling around is complete, every data item stored in the hash table is in an address entirely determined by its key and the current latest hash function. So then the hash table handler can forget the old hash function, and do all new lookups using the new hash function.

(*) One exception: some "incremental rehashing" systems remember both the old and the new hash functions, so they can run queries during the re-hashing process. Also, there are quite a few hash table handlers use a second hash function as part of the collision resolution scheme ( double hashing, cuckoo hashing, skewed associative cache, etc. ). But I've never heard of any hash table associated with more than 2 hash functions at any one time.

-