Separate Chaining Deletion
Goals
Students will understand elements of the deletion algorithm for separate chaining 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 9 cards.
Each student should use their cards and follow the insertion algorithm.
Algorithm
The first step in separate chaining deletion is finding the chain that contains the card we are looking to delete. For example, If a card hashes to 6 it will be in the numbered card 6 chain.
Now that we know which chain contains our card we remove it. If there are cards following it shift all of them up.
Example
For this example we are using a Hash table containing the Tiger, Snake, Barracuda, Quelea, Boar, Sheep, Baboon, Civet, and Hummingbird cards.
Deleting the Quelea
First, we find the chain that contains the Quelea card. When hashed the Quelea key is 4, therefore we are looking under the gold numbered card 4.
We remove the Quelea card from the chain and shift the Boar and Sheep cards up.
Deleting the Hummingbird
First, we find the chain that contains the Hummingbird card. When hashed the Hummingbird key is 7, therefore we are looking under the gold numbered card 7.
We remove the Hummingbird card from the chain, since there are no other cards after we do nothing else.
Deleting the Baboon
First, we find the chain that contains the Baboon card. When hashed the Baboon key is 5, therefore we are looking under the gold numbered card 5.
We remove the Baboon card from the chain and shift the Civet card up.
Deleting the Civet
First, we find the chain that contains the Civet. When hashed the Civet key is 5, therefore we are looking under the gold numbered card 5.
We remove the Civet card from the chain, since there are no other cards after we do nothing else.
