Software → Algorithms & Data Structures
Hash Table
A data structure that maps keys to values using a hash function and buckets.
Motivation
A hash table solves the problem of finding values quickly by key without scanning every item.
Where it fits
It belongs to algorithms and data structures and appears in maps, dictionaries, indexes, caches, and symbol tables.
Mental model
A hash function turns a key into a bucket location. The table then stores or finds the value near that location.
Important details
Important details include hashing, collisions, load factor, resizing, and the difference between average-case and worst-case behavior.
Common mistakes
- Assuming hash tables preserve order.
- Ignoring collision behavior and memory overhead.