Hash tables: finding a name at once
Add names to a table of buckets, where a hash function works out each name's bucket from its letters. See two names land in the same bucket (a collision), find a name by looking in one bucket only, and change the number of buckets to spread the names out.
Core concept
A hash table turns each key into a bucket number with a hash function; adding and finding a key look in that one bucket, so they stay fast however many keys there are, as long as collisions are few
Topic: Data structures
Finding a name in an unsorted list means checking the names one by one. A hash table does better. It keeps a row of buckets, numbered 0, 1, 2 and so on, and a hash function that turns a name into a bucket number. Here the hash adds up the places of the name's letters in the alphabet (A = 1, B = 2, … Z = 26) and takes the remainder after dividing by the number of buckets: ASHA is 1 + 19 + 8 + 1 = 29, and 29 MOD 5 = 4, so ASHA goes in bucket 4. To find ASHA later, the program works out the same number and looks in bucket 4 only. When two names land in the same bucket, that is a collision: both are kept in the bucket, one after the other, and a lookup checks just those few. More buckets usually mean fewer collisions.
What you will learn
- Work out a name's bucket with the hash function.
- Explain why a lookup only checks one bucket.
- Explain what a collision is and how the table handles it.
- See how the number of buckets changes the collisions.
Before you start
- Know what MOD (the remainder after dividing) means.
Materials
- A notebook to work out the hashes
Equipment
- None
Procedure
- Add five or more names with 5 buckets and watch where each goes.
- Find a collision, where two names share a bucket.
- Find a name and count the comparisons.
- Change the number of buckets and compare the collisions.