Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C# Hashtable Internal datastructure

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.

like image 980
Patrick Avatar asked Sep 12 '13 20:09

Patrick


People also ask

What C is used for?

C programming language is a machine-independent programming language that is mainly used to create many types of applications and operating systems such as Windows, and other complicated programs such as the Oracle database, Git, Python interpreter, and games and is considered a programming foundation in the process of ...

What is the full name of C?

In the real sense it has no meaning or full form. It was developed by Dennis Ritchie and Ken Thompson at AT&T bell Lab. First, they used to call it as B language then later they made some improvement into it and renamed it as C and its superscript as C++ which was invented by Dr.

Is C language easy?

C is a general-purpose language that most programmers learn before moving on to more complex languages. From Unix and Windows to Tic Tac Toe and Photoshop, several of the most commonly used applications today have been built on C. It is easy to learn because: A simple syntax with only 32 keywords.

What is C language basics?

What is C? C is a general-purpose programming language created by Dennis Ritchie at the Bell Laboratories in 1972. It is a very popular language, despite being old. C is strongly associated with UNIX, as it was developed to write the UNIX operating system.


2 Answers

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.

like image 162
tihonua Avatar answered Oct 12 '22 13:10

tihonua


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.

like image 22
Theodoros Chatzigiannakis Avatar answered Oct 12 '22 14:10

Theodoros Chatzigiannakis