for separate chainingassuming load factor of this is one version of the classic balls and bins problemgiven balls placed randomly (uniformlyin binswhat is the expected number of balls in the most occupied binthe answer is well known to be th(log nlog log )meaning that on averagewe expect some queries to take nearly logarithmic time similar types of bounds are observed (or provablefor the length of the longest expected probe sequence in probing hash table we would like to obtain ( worst-case cost in some applicationssuch as hardware implementations of lookup tables for routers and memory cachesit is especially important that the search have definite ( constantamount of completion time let us assume that is known in advanceso no rehashing is needed if we are allowed to rearrange items as they are insertedthen ( worst-case cost is achievable for searches in the remainder of this section we describe the earliest solution to this problemnamely perfect hashingand then two more recent approaches that appear to offer promising alternatives to the classic hashing schemes that have been prevalent for many years perfect hashing supposefor purposes of simplificationthat all items are known in advance if separate chaining implementation could guarantee that each list had at most constant number of itemswe would be done we know that as we make more liststhe lists will on average be shorterso theoretically if we have enough liststhen with reasonably high probability we might expect to have no collisions at allbut there are two fundamental problems with this approachfirstthe number of lists might be unreasonably largesecondeven with lots of listswe might still get unlucky the second problem is relatively easy to address in principle suppose we choose the number of lists to be ( tablesize is )which is sufficiently large to guarantee that with probability at least there will be no collisions then if collision is detectedwe simply clear out the table and try again using different hash function that is independent of the first if we still get collisionwe try third hash functionand so on the expected number of trials will be at most (since the success probability is )and this is all folded into the insertion cost section discusses the crucial issue of how to produce additional hash functions so we are left with determining how large mthe number of listsneeds to be unfortunatelym needs to be quite largespecifically ( howeverif we can show that the table is collision free with probability at least and this result can be used to make workable modification to our basic approach theorem if balls are placed into binsthe probability that no bin has more than one ball is less than proof if pair (ijof balls are placed in the same binwe call that collision let cij be the expected number of collisions produced by any two balls (ijclearly the probability that any two specified balls collide is /mand thus cij is /msince the number of collisions that involve the pair (ijis either or thus the expected number of