Hash Tables
Hash tables jump straight to data using a hash function.
About this topic
A hash table stores key and value pairs and allows very fast lookup. A hash function turns a key, such as a word, into a number, which is used as an index in an array where the value is stored. Because the position is calculated, finding an item takes about constant time, O(1), on average, no matter how many items there are.
Sometimes two keys produce the same index, called a collision. Solutions include chaining, where each slot holds a small list of entries, and open addressing, where the next free slot is used. A good hash function spreads keys evenly, and if the table becomes too full it is resized. For example, with hash equal to key length mod 5, the words cat and dog would collide, which shows why better functions are needed.
Hash tables power dictionaries in Python, caches, database indexes and password checking, where only hashes are stored. A common misconception is that hash tables keep items in order; they do not. Another is that hashing is the same as encryption, but hashing is a one-way process and cannot be reversed. Poor hash functions cause slow worst-case behaviour.
Key ideas
- Average O(1) lookup
- Collisions need handling
- Used in dictionaries
Quick check
Use cases: where Hash Tables helps
- Homework: review the key idea behind Hash Tables before you start a problem set.
- Exam revision: use the quick check to test whether you can recall Hash Tables without notes.
- Visual learning: play with the interactive lab to see how Hash Tables changes when you adjust its inputs.
- Teaching a friend: explain Hash Tables in your own words, then compare your version with the key ideas.
Computing ideas run phones, search engines, games and the wider internet.
Frequently asked questions
What is Hash Tables?
Hash tables jump straight to data using a hash function.
What will I learn in Hash Tables?
Average O(1) lookup. Collisions need handling. Used in dictionaries.
Is Hash Tables part of Computer Science?
Yes. It is one of 80 Computer Science topics on LearnViz HighSchoolEdu, with 3 key ideas, a live animation and a quick check.
Does the Hash Tables lab work on a phone or tablet?
Yes. The animation resizes to fit your screen and supports touch, so you can drag, tap and slide with your finger.
How should I study Hash Tables?
Read the summary and key ideas first, play with the interactive lab to see the idea in motion, then answer the quick check. If you get a question wrong, go back to the key idea it tests.
Do I need an account, and is my progress saved?
No account is needed. Marking a topic as learned is saved in your own browser, so it stays on that device and is not sent to a server.