hash bucket
One position in a hash table's underlying array, where the keys whose hash maps to that position are stored.
In more detail
A key's slot is usually its hash taken modulo the number of slots. With chaining, a bucket holds a small list of pairs; with open addressing, each slot holds at most one entry. A good hash function spreads keys so that buckets fill evenly.
Related terms
- 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.
- modulo — The operation that gives the remainder after division, written % in many programming languages, so 17 % 5 is 2.
- chaining — A way of resolving hash collisions in which each slot holds a small list of all the key-value pairs that hashed there.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers