Search code examples
c#dictionaryhashtablebig-o

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

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?

Solution

  • the HashFunc itself has a lot of operations behind the scenes

    That is certainly true. However, the number of these operations depends on the size of the key, not on the size of the hash table into which the key is inserted: the number of operations to compute hash function is the same for a key in a table with ten or with ten thousand entries.

    That is why the call of hash function is often considered O(1). This works fine for fixed-size keys (integral values and fixed-length strings). It also provides a decent approximation for variable-sized keys with a practical upper limit.

    Generally, though, access time of a hash table is O(k), where k is the upper limit on the size of the hash key.