{"id":3403,"date":"2011-09-16T18:51:00","date_gmt":"2011-09-16T18:51:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/the-net-dictionary\/"},"modified":"2016-07-28T10:50:34","modified_gmt":"2016-07-28T10:50:34","slug":"the-net-dictionary","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/blogs\/the-net-dictionary\/","title":{"rendered":"The .NET Dictionary"},"content":{"rendered":"

To many people, System.Collections.Generic.Dictionary<TKey,TValue><\/code> is just a useful collection. In this post, I’ll be looking inside that collection and see how it really works.<\/p>\n

Dictionary<\/code> is based on a hashtable; for the rest of this post, I’ll assume you know roughly how a hashtable works. The Wikipedia article<\/a>, as the source of all knowledge algorithmical, provides a good overview. It will also help if you’ve got the class open in Reflector so you can see what’s going on yourself.<\/p>\n

The basics<\/h4>\n

The core of the Dictionary<\/code> type is a standard hashtable, straight out of an algorithms book. However, it’s interesting design comes from how it deals with hash collisions, using a variant of chaining<\/em>.<\/p>\n

When you add an item to a hash table, the hash code of that item determines which slot in a backing array the item is stored. In the perfect case, every item would have a separate hash code, and so every item would have a separate slot in the array. To find an item, you simply hash it and go to that slot in the backing array.<\/p>\n

However, two or more items can hash to the same hash code, and you get a hash collision. When this happens, and you’re using chaining, the extra item is stored in a linked list hanging off the array slot. How does the .NET Dictionary handle this?<\/p>\n

Storing entries<\/h4>\n

To store its data, the Dictionary uses an array of Entry<\/code> structs: <\/p>\n

private struct Entry {\n    public TKey key;\n    public TValue value;\n    public int hashCode;\n    public int next;\n}<\/pre>\n
key<\/code> and value<\/code> should be self-explanatory. hashCode<\/code> provides a fast lookup to the original hash code for the functions that need it, and next<\/code> is used when dealing with hash collisions.<\/p>\n
So, the backing array is a Entry[]<\/code> called entries<\/code>. However, where the entries go in this array isn’t<\/em> determined by the hash code. There’s actually a separate array of ints called buckets<\/code> alongside entries<\/code>. How is this used?<\/p>\n
Hashing items<\/h4>\n
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<\/code>, it is actually the one in buckets<\/code>. The value in buckets<\/code> at the hashed index is then the index of the slot in entries<\/code> that the data is actually stored at, and that is simply assigned to the next free slot in the array.<\/p>\n
As an example, say you’ve got a Dictionary with a capacity of 5:<\/p>\n
 \"Dictionary1.png\"<\/p>\n
You add an item to it, that has a hash code of 3, modulo the size of the dictionary. The actual item goes in the first available slot in entries<\/code>, and the slot at index 3 in buckets<\/code> then stores the index at which the item is stored in entries<\/code>; in this case, 0:<\/p>\n
 \"Dictionary2.png\"<\/p>\n
You then add two more items to it, with hash codes 0 and 2, respectively:<\/p>\n
 \"Dictionary3.png\"<\/p>\n
Nice and simple. But, you then add a fourth item that also hashes to 3. Now, we’ve already added an item with a hash code of 3; we’ve got a hash collision, so the Dictionary will have to chain it. However, it doesn’t create a separate linked list, it stores the index of the next item in the chain in the next<\/code> value of the Entry<\/code> struct like so:<\/p>\n
 \"Dictionary4.png\"<\/p>\n
If we were to add another item, also with a hash code of 3, the chain would be extended:<\/p>\n
 \"Dictionary5.png\"<\/p>\n
This means, that to search for an item with a particular hash code, you go to the Entry<\/code> pointed to by the buckets<\/code> value at that hash code, and follow the next<\/code> pointers until you find the item you need, or the null pointer (signified by a next<\/code> of -1; see the FindEntry<\/code> method).<\/p>\n
Removing items<\/h4>\n
So that’s adding items. What about removing items?<\/p>\n
Any item in the dictionary can be removed at any time, which is different to adding items, where they simply get put on the end of the entries<\/code> array. If you’ve got lots of additions and removals, this can lead to a lot of wasted space as items in the middle of the array get removed, and new items get added to the end. Well, this is where a variable called freeList<\/code> comes into play.<\/p>\n
When an item is removed, the slot it occupied gets added to the freelist chain<\/em>. This is a chain of entries, indexed by a single freeList<\/code> variable, which marks array slots where additional items can go. This is chain is also linked by the next<\/code> pointer in the Entry<\/code> structure.<\/p>\n
So, this is what it would look like if you removed the blue item:<\/p>\n
 \"Dictionary6.png\"<\/p>\n
then the orange item:<\/p>\n
 \"Dictionary7.png\"<\/p>\n
Then, if another item is added, instead of adding to the end of the array (and causing a full rehash of the contents), it can simply use the slot pointed to by the freeList<\/code> variable:<\/p>\n
 \"Dictionary8.png\"<\/p>\n
Using this indirect mechanism means that the internal arrays don’t need to be resized, and everything re-hashed, until you actually have more items than you can store in the entries<\/code> array. It also doesn’t cause much performance degredation when the dictionary gets full, which the non-generic System.Collections.Hashtable<\/code> had problems with.<\/p>\n
Some more random observations…<\/h4>\n
    \n
  1. Clear<\/code> doesn’t reset the size of the arrays; if you clear a dictionary with 100,000 items in it, the backing arrays will still be sized to store 100,000 items, potentially wasting a lot of space.<\/li>\n
  2. \n
    The dictionary enumerator simply iterates down the entries<\/code> array. This is why, when you’re just adding items to a dictionary, they are returned in the order they were added. Only when you remove items and the freelist becomes involved are items returned in non-consecutive order.<\/p>\n
    However, this is very much an implementation detail, and can change in future versions of .NET; do not rely on this behaviour in your own code! Always treat the the enumeration order of any hashtable as random.<\/p>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    To many people, System.Collections.Generic.Dictionary<TKey,TValue> is just a useful collection. In this post, I’ll be looking inside that collection and see how it really works. Dictionary is based on a hashtable; for the rest of this post, I’ll assume you know roughly how a hashtable works. The Wikipedia article, as the source of all knowledge algorithmical,……<\/p>\n","protected":false},"author":186659,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[2],"tags":[],"coauthors":[],"class_list":["post-3403","post","type-post","status-publish","format-standard","hentry","category-blogs"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/3403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/186659"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=3403"}],"version-history":[{"count":1,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/3403\/revisions"}],"predecessor-version":[{"id":25366,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/3403\/revisions\/25366"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=3403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=3403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=3403"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=3403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}