Hash Tables and Hashing Strategies: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 5, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A deterministic map from keys to slot indices that should spread realistic key sets evenly and be cheap to compute. Equal keys must always hash alike, or lookups silently fail.
Hash table
An array of slots addressed by hashed keys, giving expected O(1) insert, lookup and delete but no ordering. Worst case degrades to linear when every key collides.
Collision
Two distinct keys hashing to the same slot. Collisions are unavoidable once the key universe exceeds the table size, so every design needs a resolution policy.
Load factor
The ratio of stored entries to slots. Chained tables tolerate values above one, while open addressing degrades sharply as it nears one and is usually kept below about three quarters.
Separate chaining
Storing all keys of a slot in a secondary structure such as a linked list or small tree. Simple, tolerant of high load, and deletion is easy, but it costs a pointer hop per probe.
Open addressing
Keeping every entry inside the array and probing a sequence of alternative slots on collision. Memory is compact and cache friendly, but deletion and high load need care.
Linear probing
Trying the next slot repeatedly on collision. Excellent cache behaviour because probes are contiguous, but runs of occupied slots merge and lengthen as the table fills.
Quadratic probing
Offsetting by a quadratic step so probe sequences fan out. It avoids long contiguous runs but keys with the same first slot still share a path, and coverage needs a careful table size.
Double hashing
Using a second hash to choose the probe stride, so keys colliding once rarely follow the same route. The stride must be nonzero and coprime with the table size to cover all slots.
Primary clustering
The pathology of the next-slot probe scheme where adjacent occupied runs merge into longer runs, so each new insert into that region grows the run further and slows every probe.
Secondary clustering
The milder pathology where keys sharing an initial slot follow identical probe sequences, which affects fixed-offset schemes but not a table whose stride varies by key.
Tombstone marker
A deleted flag left in an open-addressed slot so probe sequences passing through it are not cut short. Tombstones accumulate and eventually force a rebuild of the table.
Rehashing
Allocating a larger table, usually double the size, and reinserting every entry under the new modulus. It costs linear time but keeps the amortized cost per insertion constant.
Simple uniform hashing
The analytic assumption that each key is equally likely to land in any slot independently of the others. It is what justifies the expected constant-time bounds quoted for hash tables.
Universal hash family
A set of functions from which a random choice makes any two distinct keys collide with probability at most one over the table size, giving guarantees without assuming input distribution.
Perfect hashing
A collision-free scheme for a fixed known key set, typically a two-level construction with squared secondary tables, giving worst-case O(1) lookup and linear expected space.
Cuckoo hashing
Each key has two candidate slots and an insert evicts the resident, which then relocates to its alternative. Lookups examine at most two slots for worst-case constant time.
Robin Hood hashing
An open-addressing rule that swaps an inserted key with a resident when the resident sits closer to its home slot, evening out probe distances and shrinking the worst probe run.
Division method
Mapping a key to its remainder modulo the table size. Cheap, but the size should avoid powers of two and small factors, since those discard the high bits of structured keys.
Multiplication method
Multiplying the key by an irrational-like constant fraction, keeping the fractional part, and scaling to the table size. It is insensitive to the choice of table size.
Polynomial string hash
Treating a string as digits of a number in some base and reducing modulo a large prime. Its rolling form updates in constant time as a window slides, powering substring search.
Hash map versus hash set
A set stores keys alone to test membership, while a map stores an associated value with each key. Both share the same slot machinery and the same collision policy.
Bloom filter
A compact bit array with several hash functions that answers membership with no false negatives but some false positives. It saves space by never storing the keys themselves.
Consistent hashing
Placing servers and keys on a hash ring so adding or removing a server moves only a small share of keys, unlike a plain modulus which remaps almost everything.
Hash flooding attack
An adversary submitting keys that all collide, forcing linear-time operations and stalling a server. Randomised seeds or keyed hashing per process is the standard defence.