1
$\begingroup$

Suppose I have a hash table which stores the some strings. Let the index/key of this hash table be the length of the string. what is the time complexity of checking if the string of length K exists in your hashtable? is it O(1) or O(k) ?

$\endgroup$
2
  • $\begingroup$ What do you think? How long does it take to read the string? Is it necessary? $\endgroup$ Apr 21 '20 at 8:13
  • $\begingroup$ I don't have to read the string. All i need to know is that if a string of length k exists in my table. isn't this O(1) because I have my index as lengths and hence i'll just go to that index and see if a string is present. how can it be O(k)? $\endgroup$
    – Styen
    Apr 21 '20 at 10:43
1
$\begingroup$

Here's how a hash table usually works:

  • Given an input $x$, you compute its hash $h$.
  • You look at cell $h$, and compare your input to the key $k$ stored there.
  • If the key compares, great. Otherwise, what you do depends on the exact implementation.

As you can see, you have to compute the hash of your input, as well as compare it to a key stored at the table.

Typically we want the hash to depend on the entire input, has computing the hash takes at least linear time in the size of $x$. Similarly, comparing $x$ and $k$ takes non-constant time.

$\endgroup$
1
  • $\begingroup$ Oh yes! I I forgot to account the time-complexity of generating the hash. This makes sense. Thanks ! $\endgroup$
    – Styen
    Apr 21 '20 at 10:52
3
$\begingroup$

If the hash function takes the whole string into account, then the hash calculation takes $\Omega(k)$ time where $k$ is the length of the string. So the hash table lookup takes $\Omega(k)$ time.

The hash table lookup takes $\Theta(k)$ time if the hash calculation is done in linear time in the length of its input, which is typical for hash functions, and the lookup of the value takes $O(k)$ time. That part is usually not the case. With a typical hash table, looking up the bucket for the hash value in the table takes constant time $O(1)$ with respect to the length of the string $k$ and the size of the hash table $n$. But that's not the end of the lookup.

If the bucket is empty, the value is absent and the lookup ends there, having consumed $\Theta(k)$ time. If the bucket contains a value, you need to be compare it with the string that you're looking up, and that takes $O(k)$ time. If the value in the bucket is equal to the value that you're looking up, the lookup ends there, having consumed $\Theta(k)$ time. But what if the value is different? What happens next depends on the variant of the hash table data structure.

  • In a variant where collisions are handled by growing the hash table until there are no more collisions, the lookup ends here and the cost of the lookup is indeed $\Theta(k)$. This variant has efficient lookup, but pays for it by making addition potentially very expensive (depending on the growing strategy when a collision happens).
  • In a variant where collisions are handled by putting the value in the next bucket (for some traversal strategy), the search can potentially cover the whole table, with one string comparison for each bucket. The worst-case cost of each string comparison is $\Theta(k)$ (with a typical string comparison algorithm, the worst case is reached if the strings have the same length and differ towards the end). In the worst case, the total cost of the search is therefore $O(k \cdot n)$.
  • In a variant where collisions are handled by storing values that land in the same bucket in a secondary lookup structure (such as a list, a hash table with a different hash function, or a search tree), the cost depends on what the secondary data structure is. It's unlikely to be $O(1)$ with respect to the number of values in the bucket, so the worst-case cost of the lookup is not $O(k)$.

Hash tables only have constant-time operations in the average case with some “reasonable” (or not) hypotheses over the data, not in the worst case. See also (When) is hash table lookup O(1)?

$\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.