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).