hash table
A data structure that stores key-value pairs in an array and uses a hash of each key to jump almost directly to its slot.
In more detail
Lookup, insert and delete are O(1) on average, because the hash tells you where to look instead of searching. Two keys can land in the same slot, a collision, which is handled by chaining or open addressing. A hash table has no useful order, so it cannot answer range questions such as "all keys between 10 and 20".
Related terms
- hash function — A function that turns data of any size into a fixed-size value, called its hash, used to find items quickly in a table or to detect any change in the data.
- collision — Two different keys producing the same hash, or the same slot in a hash table.
- chaining — A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.
- open addressing — A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
- load factor — The number of items stored in a hash table divided by the number of slots, a measure of how full it is.
- dictionary — A Python collection that stores values under keys, written in curly brackets, such as {"tea": 250}.
- hashable — Describes a Python object that has a hash value that never changes during its lifetime and can be compared for equality, so it can be a dict key or set member.
- set (Python) — An unordered collection of distinct values, written {1, 2, 3} or made with set(), where each value appears only once.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Python Dicts And Sets Under The Hood — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Dunder Methods, And Making Objects Pythonic — Hands-on Python: Complete Video Course & Book