in the secondary hash tableand that this accounts for bi (bi )/ pairwise collisions which we will call ci thus the amount of spacebi used for the ith secondary hash table is ci bi the total space is then ci bi the total number of collisions is ( )/ (from the first sentence of this proof)the total number of items is of course nso we obtain total secondary space requirement of ( )/ thusthe probability that the total secondary space requirement is more than is at most (sinceotherwisethe expected value would be higher than )so we can keep choosing hash functions for the primary table until we generate the appropriate secondary space requirement once that is doneeach secondary hash table will itself require only an average of two trials to be collision free after the tables are builtany lookup can be done in two probes perfect hashing works if the items are all known in advance there are dynamic schemes that allow insertions and deletions (dynamic perfect hashing)but instead we will investigate two newer alternatives that appear to be competitive in practice with the classic hashing algorithms cuckoo hashing from our previous discussionwe know that in the balls and bins problemif items are randomly tossed into binsthe size of the largest bin is expected to be th(log nlog log nsince this bound has been known for long timeand the problem has been well studied by mathematiciansit was surprising whenin the mid sit was shown that ifat each tosstwo bins were randomly chosen and the item was tossed into the more empty bin (at the time)then the size of the largest bin would only be th(log log ) significantly lower number quicklya host of potential algorithms and data structures arose out of this new concept of the "power of two choices one of the ideas is cuckoo hashing in cuckoo hashingsuppose we have items we maintain two tableseach more than half emptyand we have two independent hash functions that can assign each item to position in each table cuckoo hashing maintains the invariant that an item is always stored in one of these two locations as an examplefigure shows potential cuckoo hash table for six itemswith two tables of size (these tables are too smallbut serve well as an examplebased on the table table figure potential cuckoo hash table hash functions are shown on the right for these six itemsthere are only three valid positions in table and three valid positions in table so it is not clear that this arrangement can easily be found