Why is accessing an element of a dictionary by key O(1) even though the hash function may not be O(1)?

c# dictionary hashtable big-o
monogate picture monogate · May 20, 2016 · Viewed 18.4k times · Source

I see how you can access your collection by key. However, the hash function itself has a lot of operations behind the scenes, doesn't it?

Assuming you have a nice hash function which is very efficient, it still may take many operations.

Can this be explained?

Answer

Paarth picture Paarth · May 20, 2016

O(1) doesn't mean instant. O(1) means constant without regard to the size of the data. The hash function takes a certain amount of time, but that amount of time doesn't scale with the size of the collection.

Related questions

.NET HashTable Vs Dictionary - Can the Dictionary be as fast?

I am trying to figure out when and why to use a Dictionary or a HashTable. I have done a bit of a search on here and have found people talking about the generic advantages of the Dictionary which I …

Read More
Tuples( or arrays ) as Dictionary keys in C#

I am trying to make a Dictionary lookup table in C#. I need to resolve a 3-tuple of values to one string. I tried using arrays as keys, but that did not work, and I don't know what else to …

Read More
Hashtable with MultiDimensional Key in C#

I'm basically looking for a way to access a hashtable value using a two-dimensional typed key in c#. Eventually I would be able to do something like this HashTable[1][false] = 5; int a = HashTable[1][false]; //a = 5 This is what I've been …

Read More