Menu
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
844
It can be also defined as rehashing is the process of re-calculating the hash code of already stored entries and moving them to a bigger size hash map when the number of elements in the map reaches the maximum threshold value.
Rehashing is a collision resolution technique. Rehashing is a technique in which the table is resized, i.e., the size of table is doubled by creating a new table. It is preferable is the total size of table is a prime number. There are situations in which the rehashing is required.
Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed).
Rehashing is very expensive operation, the running time is O(N),since there are N element to rehashing and the table size roughly 2N. Rehashing can be implemented in several ways with quadratic probing such as: Rehashing,as soon as the table is half full; Rehashing only when an insertion fails.
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
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
