asp.net :is time complexity of searching an value by key in dictionary constant time or log2(n)?

Question

i need a datastructure in dotnet where i can search an item in constant time.it means that datastructure should implement indexing internally.is dictionary usefull for this purpose or some other one?

Answer 1

Yes, use Dictionary<> (or Hashtable if you are on an older version of .NET). Be sure the objects you are stuffing in the dictionary have a good hash value (look into overriding GetHashCode() and Equals() for your objects you are using as keys in the Dictionary). If your data objects have poor hash codes performance will start to degrade. And yes, to answer your question, looks ups in a hashtable/dictionary should be relatively constant time (books generally say it is O(1), but that's arguable). The lookup performance will be determined by many factors:

1. Hash function (determines distribution)
2. How does the table handle collisions? Probing? Buckets? (most implementations use buckets).
3. Is the table resizable? How does it resize? Small increments? Power of 2? Prime numbers?
4. etc...