Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining.

Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and hash them. Next, we perform the search operation for one of those keys.

My question is: is it true that this operation can take $O(k)$ time? Because, if we are very unlucky, it may happen that we hashed all keys to the same cell in the hash table, and then the key that we decide to search for is exactly the key that was hashed last?


Your Answer


Browse other questions tagged or ask your own question.