[SOLVED] .NET Dictionary, impressively fast but how does it work?

Issue

Ok, I will confess I’ve not dug out reflector to look at what’s going on here, but I’m hoping someone can tell me.

How do Microsoft make adding and fetching so fast, I can make adding fast by just sticking items in an array, and I can make fetching fast by sorting the array and using a binary search. If however, I was to do a quicksort every time an item was added to make fetching data fast, adding would slow down massively, and if I had to sort the data every time I tried to fetch something, adding items would slow massively.

Does anyone know the internal workings of a dictionary? It is a fair bit more memory hungry than an array, so there’s clearly something other than clever algorithms going on behind the scenes.

I’m trying to understand the magic and learn from it!

Solution

The dictionary<T,T> in .Net is a data structure called a hash table:

On Hash Table and .Net Dictionary:

http://en.wikipedia.org/wiki/Hash_table

http://msdn.microsoft.com/en-us/library/4yh14awz.aspx

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

On Binary Search:

http://en.wikipedia.org/wiki/Binary_search

You’re right, it uses more memory than an array to retrieve data. That’s the trade off you pay for faster access. (This is true in most cases, when you start taking into account the setup time to build a hash table vs an array, at times a sorted array could be faster for setup time and access. In general this is a valid assumption though.)

Answered By – kemiller2002

Answer Checked By – Clifford M. (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *