MainExamplesHistoryRecommended Reading
Hash tables (also called hash maps or dictionaries) are data structures that store key-value pairs. They're like a super-organized filing cabinet where you can instantly find any file by its label, without searching through everything.
How It Works:
- You have a key (like a name) and a value (like a phone number)
- A hash function converts the key into an index (like a filing cabinet drawer number)
- The value is stored at that index
- When you look up a key, the hash function tells you exactly where to find it — O(1) average time!
Why They're Fast:
- Direct access: No need to search through all items
- Average O(1): Constant time lookups, inserts, and deletes
- Efficient: Much faster than arrays or lists for lookups
Common Uses:
- Caching: Store computed results to avoid recalculation
- Databases: Index data for fast retrieval
- Dictionaries: Word definitions, translations
- Counting: Track frequencies of items
FAQ
What's the difference between a hash table and an array?
Arrays use numeric indices (0, 1, 2...). Hash tables use any type of key (strings, objects) and convert them to indices using a hash function.
Can hash tables have collisions?
Yes! When two keys hash to the same index, it's a collision. Good hash tables handle this with techniques like chaining or open addressing.
Are hash tables always O(1)?
Average case is O(1), but worst case can be O(n) if there are many collisions. In practice, they're usually very fast.