5
$\begingroup$

To look up a key in a hash map you have to

  1. calculate its hash
  2. find the entry in the resulting hash bucket

Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.

When using an index (like a binary tree) for each bucket, finding an entry within a bucket that contains $k$ entries can be done in $O(\log k)$. With $n$ being the total number of entries in the hash map and $m$ being the number of buckets, $k$ averages to $n/m$. Due to $m=2^l$ we thus get $O(\log k) = O(\log n/m) = O(\log n - \log m) = O(\log n - l)$.

Combining these two runtimes one gets a total look-up time of $O(l + \log n - l) = O(\log n)$, which conforms to the intuition that a lookup in a collection with $n$ entries is not possible below $O(\log n)$ operations.

In short, it is generally assumed that $l$ and $k$ are both constant with regard to $n$. But if you fix $l$ then $k$ grows with $n$.

Am I missing something here?

Improve this question
$\endgroup$
6

3 Answers 3

Reset to default
8
$\begingroup$

Because we generally use the RAM model of computation with uniform cost model when computing the running time of operations on a hash table, and the RAM model with uniform cost states that the time to do a single operation on an entire machine word is $O(1)$. Also, we generally assume that the hash value fits within a single machine word.

Thus, the running time of computing a hash value is not $O(l)$, but rather $O(1)$ [assuming both the value being hashed and the hash value fit within one word, or a constant number of words].

Moreover, when you choose the hash function and size of the hashtable appropriately, the expected value of $k$ is $O(1)$. In particular, the number of buckets is not fixed, but increases as the number of items in the hashtable grows. The number of buckets it is usually chosen to be some function of $n$; say $m = 4n$, or something like that. In any case, we usually choose $m$ so that $n/m = O(1)$. Therefore, the (expected) running time to find an item within the bucket is $O(1)$.

Therefore, the total (expected) running time is $O(1)+O(1) = O(1)$.

So why do we use the RAM model with uniform cost model? Because it's often a better match to reality than other alternatives.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I admit that the RAM model matches reality quite good here, but from theoretical perspective, if you consider that if m is proportional to n then l~log n, assuming n -> infinite, it is actually inappropriate, right? I am so focused on the purely theoretical aspect, because I somehow always felt there is a natural limit of log n for look-ups and wondered why hash functions are able to cross it. $\endgroup$
    – jederik
    Jul 29, 2016 at 15:43
  • 1
    $\begingroup$ @jederik, nope. It's only appropriate from a theoretical perspective. It's actually pretty reasonable from a practical perspective; $O(1)$ remains a better approximation than $O(\lg n)$. Fact is, we only use a hashtable if everything will fit in memory. Once $n$ gets so big that $\lg n$ exceeds the word size (which implies $n$ won't fit in addressible memory -- take a moment to see if you understand why this implication follows), then we start using different data structures and algorithms that work differently. $\endgroup$
    – D.W. ♦
    Jul 29, 2016 at 15:51
  • $\begingroup$ So, would it be correct to say that we achieve a constant lookup time by fixing l and putting a (large) upper bound to $n$ thus bounding $k$ from above? $\endgroup$
    – jederik
    Jul 29, 2016 at 16:27
  • 2
    $\begingroup$ @jederik, I suppose that's one way to look at it. I wouldn't suggest thinking about it like that, because if you take that too seriously, then it makes you think that everything has $O(1)$ running time (since $n$ is bounded). Instead, for the theoretical perspective, look at cs.stackexchange.com/a/1661/755 (which says $n$ and $l$ aren't bounded). For a practical perspective, the real justification that empirically the RAM model with uniform cost model is a better predictor of practical running time than other models. Take my comment as only intuition, not the actual justification. $\endgroup$
    – D.W. ♦
    Jul 29, 2016 at 16:33
1
$\begingroup$

The runtime analysis as given for example in the Wikipedia only counts the number of comparisons, which is indeed O(1), if you resize your table. You have to add the time to compute the hash function if you want to be precise.

Note that this isn't too bad though. Computing the hash function for some object with $n$ bits takes $O(n)$ operations (for reasonable hash functions). Comparing two objects with $n$ bits also takes that long. So computing the hash function costs about as much as a comparison, up to constant factors.

Improve this answer
$\endgroup$
0
$\begingroup$

If a value has size l, I can easily calculate a hashcode in constant time, by ignoring all the data beyond some limit. I know of one implementation for strings that uses only up to 80 characters in the hash.

Or take an array: A reasonably simple hash for an array takes the number of elements, and the hash code of one array element chosen in a deterministic way from the element count, and hashes these two numbers.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ jederik asks for hash values of size $l$, not hashing objects of size $l$ and notes that either you bound $l$ and let your buckets grow, or you let $l$ grow and should take it into account for the runtime. Your answer doesn't seem to address that. $\endgroup$
    – adrianN
    Jul 28, 2016 at 13:13
  • $\begingroup$ Oh well, show me a hashtable with more than 2^64 buckets, and I'll address it... $\endgroup$
    – gnasher729
    Jul 30, 2016 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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