Cuckoo Hashing
Goals
Students will understand elements of the insertion algorithm for cuckoo hashing in hash tables.
Video
Materials
One deck of Menagerie cards.
Setup
Give each student a set of 0-7 number cards. Set these cards in a row, ordered from 0 on the left to 7 on the right.
Shuffle the animal cards from the deck and deal each student 12 cards.
Each student will shuffle their 12 cards, and place them in a face-down pile to their left.
Algorithm
Repeat these steps for each card in the face-down pile.
Flip over a card from your face-down pile, to become the face-up card.
Gold Insertion
To determine where the face-up card should be placed, look at the first number with a gold background. This number is the result of passing the animal name through the Murmur3 hash function, and calculating this number modulo 8.
Now find the matching number card in the row. If the space below this number card is empty, then place the face-up card in this space below. You are now finished with inserting this card.
However, if there is already a card in the space below, replace the found card with the face-up card. The found card becomes the new face-up card. Proceed to the White Insertion section.
White Insertion
To determine where the face-up card should be placed, look at the second number with a white background. This number is the result of passing the animal name through the FNV hash function, and calculating this number modulo 8.
Now find the matching number card in the row. If the space above this number card is empty, then place the face-up card in this space above. You are now finished with inserting this card
However, if there is already a card in the space above, replace the found card with the face-up card. The found card becomes the new face-up card. Proceed to the Gold Insertion section.
Looping
If you ever find yourself repeating the same replacement steps, then you should stop. The hash table is too small to hold the desired elements and will need to be resized.
Example
The first card flipped face-up is the Capybara. This card hashes to 0, so it is placed below the 0 number card.
The next card flipped face-up is the Tarsier. This card hashes to 3, so it is placed below the 3 number card.
The next card flipped face-up is the Baboon. This card hashes to 5, so it is placed below the 5 number card.
The next card flipped face-up is the Okapi. This card hashes to 3, but the Tarsier card is currently below this location.
The Okapi card replaces the Tarsier card. We now need to place the Tarsier card according to the White Insertion rules.
The Tarsier now hashes to 6. We find that the space above is empty, so we place the Tarsier in this location.
The next card flipped face-up is the Hummingbird. This card hashes to 7, so it is placed below the 7 number card.
The next card flipped face-up is the Lyrebird. This card hashes to 1, so it is placed below the 1 number card.
The next card flipped face-up is the Shrimp. This card hashes to 7, but the Hummingbird card is currently below this location.
The Shrimp card replaces the Hummingbird card. We now need to place the Hummingbird card according to the White Insertion rules.
The Hummingbird now hashes to 0. We find that the space above is empty, so we place the Hummingbird in this location.
The next card flipped face-up is the Lemur. This card hashes to 2, so it is placed below the 2 number card.
The next card flipped face-up is the Bison. This card hashes to 6, so it is placed below the 6 number card.
Squid
The next card flipped face-up is the Squid. This card hashes to 0, but the Capybara card is currently below this location.
The Squid card replaces the Capybara card. We now need to place the Capybara card according to the White Insertion rules.
The Capybara now hashes to 1. We find that the space above is empty, so we place the Capybara in this location.
The next card flipped face-up is the Siamang. This card hashes to 2, but the Lemur card is currently below this location.
The Siamang card replaces the Lemur card. We now need to place the Lemur card according to the White Insertion rules.
The Lemur now hashes to 1, but the Capybara card is currently above this location.
The Lemur card replaces the Capybara card. We now need to place the Capybara card according to the Gold Insertion rules.
The Capybara now hashes to 0, but the Squid card is currently below this location.
The Capybara card replaces the Squid card. We now need to place the Squid card according to the White Insertion rules.
The Squid now hashes to 6, but the Tarsier card is currently above this location.
The Squid card replaces the Tarsier card. We now need to place the Tarsier card according to the Gold Insertion rules.
The Tarsier now hashes to 3, but the Okapi card is currently above this location.
The Tarsier card replaces the Okapi card. We now need to place the Okapi card according to the White Insertion rules.
The Okapi now hashes to 4. We find that the space above is empty, so we place the Okapi in this location.
The next card flipped face-up is the Pangolin. This card hashes to 4, so it is placed below the 4 number card.
