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)