Cuckoo for Hashing
Cuckoo hashing is a form of hashing that employs two hash tables T1 and T2, each with its own hash function f1(x) and f2(x). Insertion of a value x proceeds as follows: you first try to store x in T1 using f1(x). If that location is empty, then simply store x there and you\'re done. Otherwise there is a collision which must be handled. Let y be the value currently in that location. You replace y with x in T1, and then try to store y in T2 using f2(y). Again, if this location is empty, you store y there and you\'re done. Otherwise, replace the value there (call it z) with y, and now try to store z back in T1 using f1(z), and so on. This continues, bouncing back and forth between the two tables until either you find an empty location, or until a certain number of swaps have occurred, at which point you rehash both tables (again, something to discuss with your faculty advisor). For the purposes of this problem, this latter occurrence will never happen, i.e., the process should always continue until an empty location is found, which will be guaranteed to happen for each inserted value.
Given the size of the two tables and a series of insertions, your job is to determine what is stored in each of the tables. (For those interested, cuckoo hashing gets its name from the behavior of the cuckoo bird, which is known to y to other bird\'s nests and lay its own eggs in it alongside the eggs already there. When the larger cuckoo chick hatches, it pushes the other chicks out of the nest, thus getting all the food for itself. Gruesome but efficient.)
5 7 4 8 18 29 4 6 7 4 8 18 29 4 1000 999 2 1000 2000 0 0 0
Case 1: Table 1 3:8 4:4 Table 2 1:29 4:18 Case 2: Table 1 0:18 2:8 4:4 5:29 Case 3: Table 1 0:2000 Table 2 1:1000