26

C# dictionaries are a simple way to find if something exists etc etc. I have a question though on how they work. Let's say instead of a dictionary I use an ArrayList. Instead of using ContainsKey (or an equivalent method in another language) I loop through the ArrayList to check if something exists there (or performing binary search if data is sorted or something similar). What's the difference in efficiency? Is the ContainsKey method using some more efficient way rather than looping through the keys and check if what I am searching exists?

If let's say I had created a specific hash function which corresponds to the type of data that I am having and is specifically designed for that set of data then yes, that hash function is indeed faster than looping through data. But dictionaries are general. ContainsKey method is not specific to the data that it gets, it's a general searching method.

Basically what I am asking is. Dictionaries are helpful to programmers. They include methods that help with many things and they combine strings with integers,(keys and values) and many more. But concerning efficiency, what do they offer? What's the difference in having a dictionary vs an ArrayList of structs(string,int)

Improve this question
1

1 Answer 1

Reset to default
35

You've got to dig a bit to see how the Dictionary is implemented in C# - Its not as obvious as HashMap (a hash table) or TreeMap (a sorted tree) (or ConcurrentSkipListMap - a skip list).

If you dig down into the "Remarks" section:

The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.

And there we have it. It's a hash table. Note that I've linked the Wikipedia article there - its a fairly good read. You may wish to read the section on collision resolution. It is possible to get a pathological data set where the lookup devolves to O(N) (for example everything you insert falls to the same hash value or index in the hash table for some reason and you're left with linear probing).

While the Dictionary is a general purpose solution you shouldn't be passing around concrete types (such as the Dictionary) - you should be passing around the interfaces. In this case, that interface is IDictionary (docs). To this, you are perfectly capable of writing your own dictionary implementation that does things optimally for the data you have.

As to the efficiency of various lookup/contains?

  • Walking an unsorted list: O(N)
  • Binary search of a sorted array: O(log N)
  • Sorted tree: O(log N)
  • Hash table: O(1)

For most people, the hash table is what they want.

You may find that the SortedDictionary is what you want instead:

The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval.

Though, again, if the data structure isn't one that works with your data ideally, you are given the tools (the interfaces) to be able to write one that works best for your data.

The dictionary itself is an abstract data type. You give me a Dictionary and I know what i can do with it and all the tools there there for me to use by the nature of it being a Dictionary. If you gave me an ArrayList, I would find myself writing my own code for searching, inserting, or deleting items from the list. This wastes my time and also means that there's more likelihood for a bug as I copy the code again and again from spot to spot.

Improve this answer
7
  • 9
    O(1) isn't necessarily "fast". Looping through a list could still be quicker than a hashtable for the collection sizes the application is dealing with.
    – whatsisname
    Dec 6, 2014 at 20:15
  • 5
    @whatsisname at no point do I claim that O(1) is fast. It certainly has the potential to be the fastest. Iterating over a the keys of a hashtable is slower than that of an ArrayList (unless you're using something like the LinkedHashMap that Java provides). It is important to know your data and how it behaves and chose the appropriate collection for it - and if that doesn't exist, write it. Assuming, of course, that such an endeavor is actually worth the time (profile first!).
    – user40980
    Dec 6, 2014 at 20:19
  • 2
    Your quote says "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.", so the OP could confuse the two concepts. In otherwords, I wanted to make it clear that big O does not tell the whole story concerning "speed".
    – whatsisname
    Dec 6, 2014 at 20:23
  • 3
    @whatsisname that's direct from Microsoft. Using a key to lookup a value, unless you have a pathological hashtable (which solves hash collisions with some other mechanism) will be faster than looking it up in a tree or sorted list (or unsorted list). Java, for example, uses linear probing (step 1) for its collision resolution - which can be slower in cases where the table is too full or too many hashes collide. For the general case though, it is good enough.
    – user40980
    Dec 6, 2014 at 20:29
  • 4
    As a relevant example, I recently optimized some code in c++ that was originally using a hash table for data sets of around 20 entries and was taking around 400ms to complete. Switching to a binary tree brought that down to 200ms, because the tree is simpler to access. But I was able to cut it still further by using an array of name value pairs and a heuristic look up function that guessed where to start looking based on past access patterns. So it's all a matter of how much data there is and what kinds of pattern there is in the accesses (e.g. locality).
    – Jules
    Dec 7, 2014 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.