What type of collision resolution is chosen for HashTable/Dictionary implementation in .net?

Question

As we know there are 2 classical strategies to collision resolution: Separate chaining and Open addressing.

I'm wondering which one was chosen for HashTable/Dictionary in .net.

Or there were used some other strategy?

Answer 1

It's all described in this paper on the MSDN : An Extensive Examination of Data Structures Using C# 2.0

...collision resolution technique called rehasing, which is the technique used by the .NET Framework's Hashtable class. In the final section, we'll look at the Dictionary class, which uses a collision resolution technique knows as chaining. ....

... Rehasing works as follows: there is 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 if needed. The previous section showed only one hash function, which is the initial hash function (H1). The other hash functions are very similar to this function, only differentiating by a multiplicative factor. In general, the hash function Hk is defined as:

 Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %  (hashsize – 1)))] % hashsize

The Dictionary class differs from the Hashtable class in more ways than one. In addition to being strongly-typed, the Dictionary also employs a different collision resolution strategy than the Hashtable class, using a technique referred to as chaining. Recall that with probing, in the event of a collision another slot in the list of buckets is tried. (With rehashing, the hash is recomputed, and that new slot is tried.) With chaining, however, a secondary data structure is utilized to hold any collisions. Specifically, each slot in the Dictionary has an array of elements that map to that bucket. In the event of a collision, the colliding element is prepended to the bucket's list.

Remember only the first sentence is my own :-)

Answer 2

That's actually a really interesting question; I've just done a blog post on how Dictionary is implemented behind-the-scenes. I may cover Hashtable in a later one.