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?

回答1:

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).

回答2:

The analysis is based on the assumption that the hash function is fixed and not related to the actual number of elements stored in the table. Rather than saying that the hash function returns a lg N-bit value if there are N elements in the hash table, the analysis is based on a hash function that returns, say, a k-bit value, where k is independent of N. Typical value of k (such as 32 or 64) provide for a hash table far larger than anything you need in practice.

So in once sense, yes, a table holding N elements requires a hash function that returns O(lg n) bits; but in practice, a constant that is far larger than the anticipated maximum value of lg n is used.

回答3:

Hashtable search is O(1). I think you are mixing insertion(which is O(n)) and search.