An interesting strategy for hashing with open addressing is known as cuckoo hashing. Two independent hash functions are computed for each key, and an lement is always stored in one of the two cells indicated by those hash functions. When a new element is inserted, if either of those two cells is available, it is placed there. Otherwise, it is placed into one of its choice of locations, evicting another entry. The evicted entry is then placed in its alternate choice of cells, potentially evicting yet another entry. This continues until an open cell is found, or an infinite loop is detected (in which case, two new hash functions are chosen and all entries are deleted and reinserted). It can be shown that as long as the load factor of the table remains below 0.5, then an insertion succeeds in expected constant time. Notice that a search can be performed in worst-case constant time,
because it can only be stored in one of two possible locations. Give a complete map implementation based on this strategy.