Have Geek Brain

Asp.net: time complexity of finding value by key in dictionary constant time or log2 (n)?

I need a data structure in dotnet where I can search for an element at a constant time.it means the datastructure should implement indexing internally. Is this dictionary useful for this purpose or some other?

+1


a source to share


1 answer


Yes, use Dictionary <> (or Hashtable if you're using an older version of .NET). Make sure the objects you fill in the dictionary have a good hash value (look at overriding GetHashCode () and Equals () for your objects that you use as keys in the dictionary). If your data objects have a bad hash code, performance will start to degrade. And yes, to answer your question, it looks like the ups in the hash table / dictionary should be a relatively constant time (books tend to say it's O (1), but that's debatable). Search performance will be influenced by many factors:



  • Hash function (defines distribution)
  • How does the table face conflicts? Sounding? Buckets? (most implementations use buckets).
  • Can the table be resized? How do I resize? Small increments? Power 2? Main numbers?
  • etc...
+2


a source






More articles:


All Articles