How the dictionary quickly searches

Question

I look at the source of Item[TKey] Dictionary<TKey,TValue> , trying to understand the storage / search mechanism in the dictionary, and why it is faster than just checking each entry one at a time.

Here I am confused about the user of primes in the buckets field and the interaction with Entry<TKey,TValue>.next .

Can someone explain the logic to me or point out a link where I can understand this.

Thanks.

Answer 1

See Hash Tables and perhaps this article on using prime numbers in a table hash .

Answer 2

Have a look at this Wikipedia article: Hashtable

A dictionary is a strongly typed implementation of a hash table. It has several "buckets" where it places items with its keys.

When you add an item to the hash table, it uses the key hash code to decide which bucket it will be placed in (which is usually a very quick operation, just call GetHashCode and apply modulo to it). When it has a bucket (this is some kind of list), it checks if the bucket contains an item with the same key and adds it if it is not. This is also pretty fast, because each bucket contains only a small subset of all hash table elements.

When you want to get an element based on its key, it defines a bucket based on the hash code of the key and looks for the element with this key in the bucket.

Of course, this is a very simplified description ... for more details see the Wikipedia article.

Answer 3

Look at the hash codes, they allow the bucket dictionary:

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

Colin E.