I'm currently reading an analysis hashing with chaining, and it goes over two examples:

In the first, the search is unsuccessful; no element in the table has key k. In the second, the search successfully finds an element with key k.

(This is all under the assumption of simple uniform hashing). I understood the analysis for the first case, but the second confuses me. The book goes:

The situation for a successful search is slightly different, since each list is not equally likely to be searched. Instead, the probability that a list is searched is proportional to the number of elements it contains.

The above sentences are what confuses me. Why is each list not equally likely to be searched if both operate under assumption of simple uniform hashing? And why in the world would the number of elements a list contains have any effect at all on the probability that the list is searched? I would think it's the opposite...the number of elements searched in a list depends on the probability that a key is hashed to a particular index (where the list is).


1 Answer 1


I assume that you are talking about the hash-table that uses an adjacency list for the elements that have the same hash key (hash table using chaining). Let's look at a very simple example.

We have a hash table such as the following:

key : like list of elements
1   : x_11 -> x_12 -> ... -> x_11000000 -> NULL  // 1000000 elements
2   : NULL                                       // 0 element
3   : x31 -> NULL                                // 1 element

If you look at keys 1 and 3, which one is more likely to be visited? The answer is 1, because it has more elements than all other lists. Therefore, we are more likely to find the mysterious element in 1's linked list.


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.