Hashtable- Rehashing

Question

I have been told that Hashtable in .NET uses rehashing in order to reduce/avoid collision.

Ie. “Rehasing works as follows: assume we have a set of hash different functions, H1 ... Hn, and when inserting or retrieving an item from the hash table, initially the H1 hash function is used. If this leads to a collision, H2 is tried instead and onwards up to Hn to avoid collision in Hashtable.”

Assumption: We have a hashtable with n (where n < Infinity) element where asymptotic time complexity is o(1); we (CLR) have achieved this while applying some hashing function ( Hn-1 hash function where n>1).

Question: Can someone explain me how CLR map Key to the hash code when we seek (retrieve) any element (if different hashing functions are used)? How CLR track (if it) the hashing function of any live object (hash table)?

Thanks in advance

Answer 1

Random selection of a hash function is know as Universal Hashing approach. AFAIK the hash function selected once per some initialization process so this is not a real case when in scope of a single hash table were used multiple hash functions.

EDIT: More details

Just back at home, opened "Introduction to algorithms" T. Cormen book and found following in the section 11.3.3 Universal Hashing:

The main idea behind universal hashing is to select the hash function at random from a carefully designed class of functions at the beginning of execution

You can read more by previewing the book at the Google Books site here