hashing randomly chosen hash functionsitem can be at either position in table or position in table item can be at either position in table or position in table and so on immediatelythis implies that search in cuckoo hash table requires at most two table accessesand remove is trivialonce the item is located (lazy deletion is not needed now!but there is an important detailhow is the table builtfor instancein figure there are only three available locations in the first table for the six itemsand there are only three available locations in the second table for the six items so there are only six available locations for these six itemsand thus we must find an ideal matching of slots for our six items clearlyif there were seventh itemgwith locations for table and for table it could not be inserted into the table by any algorithm (the seven items would be competing for six table locationsone could argue that this means that the table would simply be too loaded ( would yield load factor)but at the same timeif the table had thousands of itemsand were lightly loadedbut we had abcdefg with these hash positionsit would still be impossible to insert all seven of those items so it is not at all obvious that this scheme can be made to work the answer in this situation would be to pick another hash functionand this can be fine as long as it is unlikely that this situation occurs the cuckoo hashing algorithm itself is simpleto insert new itemxfirst make sure it is not already there we can then use the first hash functionand if the (firsttable location is emptythe item can be placed so figure shows the result of inserting into an empty hash table suppose now we want to insert bwhich has hash locations in table and in table for the remainder of the algorithmwe will use ( to specify the two locationsso ' locations are given by ( table is already occupied in position at this point there are two optionsone is to look in table the problem is that position in table could also be occupied it happens that in this case it is notbut the algorithm that the standard cuckoo hash table uses does not bother to look insteadit preemptively places the new item in table in order to do soit must displace aso moves to table using its table hash locationwhich is position the result is shown in figure it is easy to insert cand this is shown in figure next we want to insert dwith hash locations ( but the table location (position is already taken note also that the table location is not already takenbut we don' look there insteadwe have replace cand then goes into table at position as suggested by its second hash function the resulting tables are shown in figure table table figure cuckoo hash table after insertion of