hashing collisions in the entire table is (ij) < cij since there are ( )/ pairsthis sum is ( )/( mn( )/( since the expected number of collisions is below the probability that there is even one collision must also be below of courseusing lists is impractical howeverthe preceding analysis suggests the following alternativeuse only binsbut resolve the collisions in each bin by using hash tables instead of linked lists the idea is that because the bins are expected to have only few items eachthe hash table that is used for each bin can be quadratic in the bin size figure shows the basic structure herethe primary hash table has ten bins bins and are all empty bins and have one itemso they are resolved by secondary hash table with one position bins and have two itemsso they will be resolved into secondary hash table with four ( positions and bin has three itemsso it is resolved into secondary hash table with nine ( positions as with the original ideaeach secondary hash table will be constructed using different hash function until it is collision free the primary hash table can also be constructed several times if the number of collisions that are produced is higher than required this scheme is known as perfect hashing all that remains to be shown is that the total size of the secondary hash tables is indeed expected to be linear theorem if items are placed into primary hash table containing binsthen the total size of the secondary hash tables has expected value at most proof using the same logic as in the proof of theorem the expected number of pairwise collisions is at most ( )/ nor ( )/ let bi be the number of items that hash to position in the primary hash tableobserve that space is used for this cell figure perfect hashing table using secondary hash tables