Search code examples
complexity-theory

Is a lookup in a hash table O(1)?


If a hash table holds N distinct items, and is not overloaded, then the hashes for the N items must have have approximately lg(N) bits, otherwise too many items will get the same hash value.

But a hash table lookup is usually said to take O(1) time on average.

It's not possible to generate lg(N) bits in O(1) time, so the standard results for the complexity of hash tables are wrong.

What's wrong with my reasoning?


Solution

  • What is wrong with your reasoning is the use of conflicting definitions of "time".

    When one says that lookup in a hash table takes O(1) time, one usually means that it takes O(1) comparisons, that is, the number of comparisons required to find an item is bounded above by a constant. Under this idea of "time", the actual time (as in the thing you would measure in seconds) used to compute the hash causes no variation.

    Measuring time in comparisons is an approximation that, while it may not reflect reality in the same way that measuring it in seconds would, still provides useful information about the behaviour of the hash table.

    This sort of thing is true for most asymptotic complexity descriptions of algorithms: people often use "time" with a very abstract meaning that isn't the informal meaning of "time", but more often than not is some variation of "number of operations" (with the kind of operation often left unstated, expected to be obvious, or clear from context).