Reading CLRS analysis of hashing with chaining 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).
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 -&gt; x_12 -&gt; ... -&gt; x_11000000 -&gt; NULL  // 1000000 elements
2   : NULL                                       // 0 element
3   : x31 -&gt; 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.