Best performance on a String Dictionary in C#

c# performance dictionary hashtable idictionary
smartcaveman picture smartcaveman · Jul 4, 2011 · Viewed 9.4k times · Source

I am designing a C# class that contains a string hierarchy, where each string has 0 or 1 parents.

My inclination is to implement this with a Dictionary<string,string> where the key is the child and value is the parent. The dictionary may have a large amount of values, but I can't say the exact size. This seems like it should perform faster than creating composite wrapper with references to the parent, but I could be wrong.

Is there an alternative approach I can take that will ensure better performance speed?

Answer

Ed S. picture Ed S. · Jul 4, 2011

Retrieving values from a Dictionary<K,V> is extremely fast (close to O(1), i.e., almost constant time lookup regardless of the size of the collection) because the underlying implementation uses a hash table. Of course, if the key type uses a terrible hashing algorithm than the performance can degrade, but you can rest assured that this is likely not the case for the framework's string type.

However, as I asked in my comment, you need to answer a few questions:

  1. Define what performance metric is most important, i.e., Time (CPU) or space (memory).
  2. What are your requirements? How will this be used? What's your worst case scenario? Is this going to hold a ton of data with relatively infrequent lookups, do many lookups need to be performed in a short amount of time, or do both hold true?

The Dictionary<K,V> class also uses an array internally which will grow as you add items. Is this okay for you? Again, you need to be more specific in terms of your requirements before anyone can give you a complete answer.

Related questions

What is more efficient: Dictionary TryGetValue or ContainsKey+Item?

From MSDN's entry on Dictionary.TryGetValue Method: This method combines the functionality of the ContainsKey method and the Item property. If the key is not found, then the value parameter gets the appropriate default value for the value type TValue; …

Read More
Why is it faster to check if dictionary contains the key, rather than catch the exception in case it doesn't?

Imagine the code: public class obj { // elided } public static Dictionary<string, obj> dict = new Dictionary<string, obj>(); Method 1 public static obj FromDict1(string name) { if (dict.ContainsKey(name)) { return dict[name]; } return null; } Method 2 public static …

Read More
Is there a limit to entries in a Dictionary<>?

I have about 3000 different files I need to organize, and retrieve at different times during the game. I created my own struct of variables. I was thinking about creating a "Dictionary " at the beginning of my application, and simply loading …

Read More