2

I know what the difference is in terms of where a map or where a dictionary is used, but what I wondered is why a Dictionary<TKey, TValue> in .NET supposedly uses, from what I've read here, a linked list under the covers and I know that a std::map<K,T> (C++) is implemented as a red-black tree.

Why aren't they the same under the covers, is there some difference in performance, (which I know that a C++ data structure is optimized for) or why would the .NET dictionary actually be a linked list under the covers and the C++ std::map then a red-black tree, which to my knowledge are completely different data structures, used for entirely different purposes mostly.

Perhaps these two things serve a different purpose and maybe I just don't know.

Can anybody clarify?

Community
  • 1
  • 1
Tony The Lion
  • 61,704
  • 67
  • 242
  • 415
  • 2
    The question you linked to only states that linked lists *are used* in `Dictionary`, not that it *is* a linked list. There's an important difference. :) – jalf Apr 21 '11 at 08:47
  • @jalf: hmm interesting point... – Tony The Lion Apr 21 '11 at 08:47
  • To elaborate on jalf's point, a linked list is one (in my experience often poor) way to handle collisions as hash values for different keys coincidentally fold to the same hash bucket. In this model, a hash table is effectively an array of linked lists, but the way elements are added, removed, the table resized etc. incorporates the hashing for faster index, and aims to keep each list as short as possible. – Tony Delroy Apr 21 '11 at 10:05

1 Answers1

3

Dictionary<> is a hash table, akin to std::unordered_map<>.

SortedDictionary<> is a red-black tree, akin to std::map<>.

ildjarn
  • 62,044
  • 9
  • 127
  • 211