O(1) hash look ups?

Question

I ran across an assertion that HashSet<T>.Contains() is an O(1) operation. This surprised me since every discussion of hashing I've encountered mentions the possibility of collisions, potentially leading to O(n) run time.

Being curious, I looked into documentation for HashSet<T>.Contains and also HashTable.Contains. The documentation for both methods make that same claim.

When I look in reflector, HashSet<T>.Contains() is implemented with a for loop, going through a list of slots containing values which have the same hash.

Now admittedly, those same discussions of hashing have also mentioned that a good hashing algorithm avoids collisions and under those circumstances the lookup will indeed be O(1). But my understanding of Big O notation is that it's the worst-case runtime time, not best.

So is the O(1) claim incorrect? Or am I missing something?

Answer 1

In general, it's O(1).

Answer 2

No, Big O does not define "worst case", it defines a limit. Hash-based lookups (with good hashing algorithms that provide efficient value distribution and a low collision rate) progress toward a constant value as the number of items increases (they will never reach or that constant value, but that's the point of it being a limit).

Answer 3

I believe it means O(1) on average.

Answer 4

But my understanding of Big O notation is that it's the worst-case runtime time, not best.

Unfortunately, there is no "standard" for Big-O when describing algorithms. Often, it's used to describe the general or average case - not the worst case.

From Wikipedia:

...this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case...

In this case, it's describing a standard case, given proper hashing. If you have proper hashing in place, the limiting behavior will be constant for size N, hence O(1).

Answer 5

My understanding of Big Oh is that the "worst case" generally is in reference to the number of elements involved. So if a function were to perform O(n) with 10 elements, but O(n squared) with 100 or more (not sure such an algorithm actually exists), then the algorithm is considered O(n squared).

Answer 6

O(1) does not necessarily mean "worst case". For hashes, one usually says that the "expected" lookup time is O(1), since the probability of hash collisions is small.

Answer 7

For a properly implemented hash table, look ups have amortized constant time complexity.

In practice, a single look up can be O(n) in case of collisions, as you say. However, if you perform a large number of look ups the average time complexity per operation is constant.

Quoting wikipedia:

Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

Answer 8

No, Big-O notation is not necessarily restricted to the worst-case. Typically you will see Big-O published for best-case, average-case, and worst-case. It is just that most people tend to focus on the worst-case. Except in the case of a hash table the worst-case rarely happens so using the average-case tends to be more useful.

Yes, a good hash function reduces the probability of a collision. A bad hash function may cause the clustering effect (where different values hash to the exact same value or close to the same value). It is easy to demonstrate that HashSet can indeed become O(n) by implementing the GetHashCode function in such a manner that it returns the same value all of the time.

In a nutshull, yes HashSet and Dictionary can be described as having O(1) runtime complexity because the emphasis is on the average-case scenario.

By the way, Big-O can be used to analyze amortized complexity as well. Amortized complexity is how a sequence of separate (and sometimes even different) operations behave when grouped together as if they were one big operation. For example, a splay tree is said to have amortized O(log(n)) search, insert, and delete complexity even though the worst-case for each could O(n) and the best-case is O(1).

Answer 9

Hash tables not only have average-case performance O(1), but if the hash function is random, for any given percentage P < 100%, the performance that can be obtained P% of the time from a properly-designed hash tale is O(1). Although the extreme parasitic cases become more and more severe as N increases, that is balanced by the fact that even moderately-parasitic cases become less and less likely.