How are hash tables O(1) taking into account hashing speed?

Question

Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity.

However, this assumes the lengths of the elements are constant. Computing the hash of an element requires going through the element, taking $\Theta(l)$ time where $l$ is the length.

But to discriminate between $n$ elements, we need the elements to have length at least $\lg n$ bits; otherwise by pigeonhole principle they won't be distinct. The hash function going through $\lg n$ bits of element is going to take $\Theta(\lg n)$ time.

So can we instead say that the speed of a hash table, taking into account a reasonable hash function which uses all parts of the input, is actually $\Theta(\lg n)$? Why, then, are hash tables in practice efficient for storing variable-length elements, such as strings and large integers?

Answer 1

The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification.

This is only true if:
- The amount of data to hash per item is trivial compared to the number of Keys and the speed of hashing a Key is fast - $k$.
- The number of Collisions is small - $c$.
- We do not take into account time needed to Resize the hash table - $r$.

Large strings to hash
If the first assumption is false the running time will go up to $\Theta(k)$.
This is definitely true for large strings, but for large strings a simple comparision would also have a running time of $\Theta(k)$. So a hash is not asymptotically slower, although hashing will always be slower than a simple comparision, because comparison has a early opt out ergo $O(1)$, $\Omega(k)$ and hashing always has to hash the full string $O(k)$, $\Omega(k)$.

Note that integers grow very slowly. 8 bytes can store values up to $10^{18}$; 8 bytes is a trivial amount to hash.
If you want to store bigints then just think of them as strings.

Slow hash algorithm
If the amount spend hashing is non-trivial compared to the storage of the data then obviously the $\Theta(1)$ assumption becomes untenable.
Unless a cryptographic hash is used this should not be an issue.

What matters is that $n$ $>>$ $k$. As long as that holds $\Theta(1)$ is a fair statement.

Many collisions
If the hashing function is poor, or the hash table is small, or the size of the hash table is awkward collisions will be frequent and the running time will go to $O(log(n))$.
The hashing function should be chosen so that collisions are rare whilst still being as fast as possible, when in doubt opt for fewer collisions at the expense of slower hashing.
A rule of thumb is that the hashing table should always be less than 75% full.
And the size of the hashing table should not have any correlation with the hashing function.
Often the size of the hashing table is (relatively) prime.

Resizing the hash table
Because a nearly full hash table will give too many collisions and a big (empty) hash table is a waste of space, many implementations allow the hash table to grow (and shrink !) as needed.
The growing of a table can involve a full copy of all items (and possibly a reshuffle), because the storage needs to be continuous for performance reasons.
Only in pathological cases will the resizing of the hash table be an issue so the (costly but rare) resizes are amortized across many calls.

Running time
So the real running time of a hash table is $\Theta(kcr)$.
Each of $k$, $c$, $r$ on average is assumed to be a (small) constant in the amortized running time and thus we say that $\Theta(1)$ is a fair statement.

To get back to your questions
Please excuse me for paraphrasing, I've tried to extract different sets of meanings, feel free to comment if I've missed some

You seem to be concerned about the length of the output of the hash function. Let's call this $m$ ($n$ is generally taken to be the number of items to be hashed). $m$ will be $log(n)$ because m needs to uniquely identify an entry in the hash table.
This means that m grows very slowly. At 64 bits the number of hash table entries will take up a sizeable portion of worldwide available RAM. At 128 bits it will far exceed the available disk storage on planet earth.
Producing a 128 bit hash is not much harder than a 32 bit hash, so no, the time to create a hash is not $O(m)$ (or $O(log(n))$ if you will).

The hash function going through $log(n)$ bits of element is going to take $Θ(log(n))$ time.

But the hash function does not go through $log(n)$ bits of elements.
Per one item (!!) it only goes though $O(k)$ data.
Also the length of the input (k) has no relation with the number of elements. This matters, because some non hashing algorithms have to examine many elements in the collection to find a (non)matching element.
The hash table only does 1 or 2 comparisons per item under consideration on average before reaching a conclusion.

Why are hash tables efficient for storing variable-length elements?

Because irrespective of the length of the input ($k$) the length of the output ($m$) is always the same, collisions are rare and lookup time is constant.
However when the key length $k$ grows large compared the to number of items in the hash table ($n$) the story changes...

Why are hash tables efficient for storing large strings?

Hash tables are not very efficient for very large strings.

If $not$ $n >> k$ (i.e. the size of the input is rather large compared to the number of items in the hash table) then we can no longer say that the hash has a constant running time, but must switch to a running time of $\Theta(k)$ especially because there is no early out. You have to hash the full key. If you're only storing a limited number of items then you may be much better off using a sorted storage, because when comparing $k1$ $\ne$ $k2$ you can opt out as soon as a difference is seen.

However if you know your data, you can choose not to hash the full key, but only the (known or assumed) volatile part of it, restoring the $\Theta(1)$ property whilst keeping the collisions in check.

Hidden constants
As everyone ought to know $\Theta(1)$ simply means that the time per element processed is a constant. This constant is quite a bit larger for hashing than for simple comparison.
For small tables a binary search will be faster than a hash lookup, because e.g. 10 binary comparisons might very well be faster than a single hash.
For small datasets alternatives to hash tables should be considered.
It's on large datasets that hash tables truly shine.

Answer 2

Let's start with a simpler question. Consider what is perhaps the simplest data structure in existence, an array. For concreteness, let us imagine an array of integers. How much time does the operation $A[i] = A[j]$ take? The answer depends on the computation model. Two models are relevant here: the RAM model (which is more common) and the bit model (which is simpler to explain).

In the bit model, a basic operation involving $N$ bits costs $N$. So if the integers are $w$ bits wide, the operation $A[i] = A[j]$ is going to cost about $2w$.

In the RAM model, the basic unit of data is not a bit but a word (sometimes known as a machine word). A word is an integer of width $\log n$, where $n$ is the size of the inputs (in bits). A basic operation involving $N$ words costs $N$. In most cases, if you have an integer array then the integers you need have width $O(\log n)$, and so the operation $A[i] = A[j]$ costs $O(1)$.

As I said above, we usually analyze algorithms using the RAM model. The only common exception is integer arithmetic, especially integer multiplication, which is often analyzed with respect to the number of bit operations.

Why do we use the RAM model? Since it has more predictive power (vis a vis reality). The assumption that the input size is at most exponential in the size of a machine word is usually justified, especially for modern 64-bit processors, and operations on machine words do take constant time in actual CPUs.

---

Hash tables are more complicated data structures, and they really involve three types: the key type, the hash type, and the value type. From the point of view of the value type, a hash table is just a glorified array, so let's ignore that aspect. The hash type can always be assumed to consist of a small number of machine words. The key type satisfies a special property: it is hashable, which means that it has a hash operation which (at minimum) is some deterministic function (a function always returning the same value).

We can now address your question: how long does it take to hash a key? The answer depends on the computation model. This times we have three common models: the two earlier ones, and the oracle model.

In the oracle model, we assume that the hash function is given to us by an "oracle" that can compute the hash of an arbitrary key in constant time.

In the RAM model and the bit model, the hash function is an actual function, and the time complexity of the hash table depends on the time complexity of the hash function. Hash functions used for hash table (rather than for cryptographic purposes) are usually very fast, and take linear time in the input. That means that if the key type has length $N$ bits (in the bit model) or $N$ words (in the RAM model), the hash function takes time $O(N)$. When $N$ is a constant, the hash function takes constant time.

When we analyze the running time of hash table algorithms, we usually implicitly use the oracle model. This is often expressed in a different language: we simply say that we count the number of invocations of the hash function. This makes sense, since usually applications of the hash function is the dominant term in the running time of hash table algorithms, and so to analyze the actual time complexity, all you have to do is to multiply the number of hash invocations by the running time of the hash function.

When analyzing the running time of an algorithm using a hash table as a data structure, we are often interested in the actual running time, usually in the RAM model. One option here is to do what was suggested in the preceding paragraph, namely to multiply the running time of hash table operations (given in terms of number of hash function invocations) by the running time of the hash function.

However, this is not good enough if the keys have varying lengths. For example, imagine we have keys of size $1,2,4,\ldots,2^m$, and we calculate the hash of each of them once. The actual time complexity is $O(2^m)$, but the computation above only gives $O(m2^m)$. If this is the case in some application, we can take it into account on an ad hoc basis, using a refined analysis of the complexity of the underlying hash table.