8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Closely related: (When) is hash table lookup O(1)?, For what kind of data are hash table operations O(1)? $\endgroup$ – Gilles Jun 15 '14 at 16:56
  • 4
    $\begingroup$ The answer is they are not. This type of analysis of hashing does not take into account the dimension (or number of bits) of the elements, but only their multitude. $\endgroup$ – Nikos M. Jun 15 '14 at 18:51
  • $\begingroup$ But if a hash map look-up that would be $\Theta (1)$ not considering reading and writing the bits as described, is $ \in \Theta (lg$ $n)$, then under the same criteria, a binary search or any other process we normally consider $\in \Theta lg$ $n$ would actually be $ \in \Theta( lg^2 $ $n )$ wouldn't it? $\endgroup$ – user16480 Jun 15 '14 at 19:44
  • 5
    $\begingroup$ @tAllan cf uniform vs logarithmic cost model. $\endgroup$ – Raphael Jun 15 '14 at 20:12
  • $\begingroup$ @tAllan A regular binary search would be $\Theta(\log^2 n)$ but if you keep items sorted according to their keys' bit sequences and do binary search comparing "one bit at a time" (tricky details omitted), you might be able to attain $\Theta(\log n)$. $\endgroup$ – Solomonoff's Secret Jul 20 '16 at 14:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand your definition of $k,c,r$. It's not true that resizing increases the amortized runtime. As long as you do the resizing appropriately the cost of copying can be amortized away and doesn't increase the amortized runtime. I don't think the speed of the hash is ever an issue (even cryptographic hashes are very fast; and in any case, they run in constant time, if the length of the input is upper-bounded by a constant). The $O(1)$ runtime claims are always contingent on using a good hash function (so collisions will be few). $\endgroup$ – D.W. May 1 '16 at 19:44
  • 1
    $\begingroup$ So of the issues you mentioned, I think only the length of the input is really a serious issue. Also, this doesn't really answer the question that was asked. The question talks about the length of the outputs and that length of the outputs should be best considered to be $\Omega(\lg n)$ bits rather than $O(1)$ bits. That's correct, but what it overlooks is the computational model used to compute the $O(1)$ running time. This answer doesn't seem to get into any of that, so I'm not sure this is getting at the issue raised in the question. $\endgroup$ – D.W. May 1 '16 at 19:45
  • $\begingroup$ I wanted to be complete with all the elements of the running time. We agree that only the key length is really a concern when hashing. I fixed the log(n) issue the OP raised. I misread that, because it's such a non-issue when hashing IMO. $\endgroup$ – Johan May 1 '16 at 20:47
  • $\begingroup$ I hope the answer is more in tune with the OP's question now. $\endgroup$ – Johan May 1 '16 at 21:05
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.