Hashtable and Dictionary

As I have mentioned in the previous post – the .NET runtime is now open source. This means that we can dive into it’s code. What is important – most of the code is written in C++ (as expected obviously!).

As part of the runtime I have go through the mscorlib project. What got me interested were Dictionary and Hashtable implementations. There is quite sophisticated arithmetic there as we might have expected.

They share the code

The main difference between this two is obvious – the idea is the same, using hashes to store values in buckets. But it is more important that Dictionary code is just the copy of the initial Hashtable implementation. This means that if any bug fix is implemented in either of them, it needs to be made in the other one as well.

Hashtable has thread safety for multiple readers and single writer build into some of its methods and properties. As you probably know the hash table (aka hash map) is a data structure that maps keys to values and uses hash function for calculating the key (index) to put values into buckets.

In .NET implementation the hash function uses double hashing which looks like this:

h(key, n) = h1(key) + n*h2(key)

where n is the number of collisions for a bucket. h1 is our implementation of GetHash(key) (or the default if we did not override it). More complicated is the h2 one which uses h1 and calculates the value between 1 and hashsize-1.

The table where values are stored is initialized with 3 elements when we do not specify the size (we should not treat this as the constant value from version to version – this can differ). Even when we specify smaller number – there is a check to the “awfully small sizes” are avoided. Very interesting is the procedure for extending the size of the array.

Resize hash array

When the procedure reaches the maximum number of buckets in the array (load factor reaches the maximum load factor) – it needs to be resized. The number of buckets in the hashtable is “automatically increased by approximately a factor of two”. What does it mean? It means that that the size is increased to the smallest prime number which is larger than the current size of hashtable.

How is this organized in the code? First of all – the first 72 prime numbers are stored as the readonly array – so there is no need to calculate them. The biggest one is 7 199 369 (that’s quite big number). When the hashtable size is even bigger – the next prime number is going to be calculated.

We know that by doubling we are preserving the asymptotic complexity of the hashtable operations such as add. What is more important – by having a prime guarantees that double hashing does not lead to infinite loops or just one bucket with plenty of collisions.

Summary

By releasing .NET Framework as open source Microsoft allowed us, developers, to verify the code they wrote. We can even make changes and build our own version of the .NET Framework. I think it is very interesting to check how some of the objects were implemented by devs at Microsoft.

In this short post I dig a little bit into the Hashtable implementation in mscorlib.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s