8

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

sll
  • 61,540
  • 22
  • 104
  • 156
s_nair
  • 812
  • 4
  • 12
  • 1
    Sidebar: Are you needing to use `Hashtable` because of working with .NET 1.1 (directly or via a library)? If not, you should instead consider `System.Collections.Generic.Dictionary`. – Anthony Pegram Sep 28 '11 at 18:24
  • @Anthony Pegram : I believe in terms of hashtable data structure optimization there is should not be (?!) any differences, I mean low-level implementation of both Hashtable and Dictionary classes. AFAIK main difference is that Dictionary provides generic type arguments what makes more efficient work with value type objects by effectively excluding boxing/unboxing operations – sll Sep 28 '11 at 18:44
  • I looked at the code of `Dictionary`, so I know it doesn't use multiple hash functions, just the single hash function `object.GetHashCode()`, placed in a slot according to the modulus of the table size (which is a prime number). – Qwertie Sep 28 '11 at 19:48
  • @Anthony Pegram: We have a code base which uses Hashtable. Therefore, the point was to know how hashing work undercover for hash table. Anyways thanks for your comment. – s_nair Sep 29 '11 at 08:20
  • @sll: Thank you flashing idea on Universal Hashing. Nonetheless, I have to comment your point here. AFAIK Hashtable uses rehashing/double hashing in case of collision. But when it comes to Dictionary, it uses chaining to avoid collision. The only similarity which I can think of now is Dictionary is a generic implementation of Hashtable. – s_nair Sep 29 '11 at 08:22
  • @s_nair : do you have a reference to MSDN, I recall that read something liek that but can't recall exact details, looks like you right – sll Sep 29 '11 at 09:04

1 Answers1

5

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

enter image description here

sll
  • 61,540
  • 22
  • 104
  • 156