Imagine a wall of cubby holes. Every toy has a name, and a magic rule tells you which cubby should hold it. That is the idea behind a hash table.
A hash table stores a value with a key. The key might be a name like Luna. The value might be Luna’s phone number.
The hash function chooses a cubby
A hash function turns a key into a location. The same key should always lead to the same location. So when we ask for Luna later, the computer knows where to look.
We do not need to check every name from the beginning. A good hash table often finds an item in about one quick jump.
Sometimes two keys bump
Two different keys can choose the same cubby. This is called a collision. It is normal, and hash tables have plans for it.
- One plan keeps a small list inside each cubby.
- Another plan checks the next open cubby.
- The table may grow when too many cubbies become crowded.
A collision does not mean the table is broken. It only means the computer must do a little extra checking.
Where hash tables help
They are useful for dictionaries, user accounts, word counts, caches, and settings. Use one when you know a key and want its value quickly.
Hash tables are not naturally sorted. If you need every item in order, another structure may fit better.
phone_book = {
"Luna": "555-0101",
"Milo": "555-0102",
}
print(phone_book["Luna"]) # 555-0101
phone_book["Nova"] = "555-0103"
print(phone_book["Nova"])Your tiny challenge
Draw five cubbies. Make a rule that uses the first letter of each toy’s name. Put ball, bear, car, and doll away. Ball and bear collide, so give their cubby a tiny list.