C# Hashtable Internal datastructure

Question

All -

Asking a specific question which I came across recently and surprisingly didn't find any convincing answer.

What is the internal backing data structure which C# Hashtable (and Dictionary - which internally uses Hashtable) leverages

So in essence - what kind of buckets are key value pairs stored in - ArrayList, LinkedList (which I know is not the answer here), tree structure etc.

Not looking for collision strategies etc - simply once a hashcode is computed - what data structure does Hashtable internally use to store this value?

Any explanation or article pointers will really help.

Answer 1

There is a nice explanation of dictionary internal datastructure: https://www.simple-talk.com/blogs/2011/09/16/the-net-dictionary/ , the same is thrue for HashTable

In a nutshell hashtable consists of two arrays: buckets and entries

When adding an item, the hash code is generated modulo the current array size, and that determines the slot the item is stored in.

However, that slot is not the one in entries, it is actually the one in buckets.

The value in buckets at the hashed index is then the index of the slot in entries that the data is actually stored at, and that is simply assigned to the next free slot in the array.

Answer 2

System.Collections.Hashtable defines a custom struct (bucket) for storing the key, value and collision information and keeps a simple array of instances of that struct.

System.Collections.Generic.Dictionary uses about the same strategy, although with generic types instead of object. The generic Dictionary does not make use of the non-generic Hashtable, even though they work similarly.