Closed Hash Tables with Buckets

Each slot holds several entries. Sized to a cache line, a bucket absorbs the first few collisions without a second memory fetch — and spills to an overflow area only when everything is full.

5 buckets × 3

Lookup: O(1) avg

Cache-line sized

Overflow fallback

Keys to insert (enough to force an overflow)

Speed: 850ms

Step 1 of 0Phase: start

Current Key

—

Home bucket

—

Bucket fill

0.00

Buckets — each one is a cache line

bucket 0

bucket 1

bucket 2

bucket 3

bucket 4

Overflow area — linear scan

empty

Current Step

Click Play to begin

Complexity

Search avg:O(1)

Bucket scan:O(B)

Overflow:O(n)

Space:O(m×B)

Key Concepts

Locality: a bucket is one cache line, one fetch
Fewer probes than single-cell open addressing
Trade-off: bigger buckets mean longer scans
Overflow is the slow path — resize before you need it

Knowledge Check

Question 1 of 3

Why does giving each slot a bucket of several entries help, when the total capacity is unchanged?

Indexing

Hashing your keys…

DSAverse

Closed Hash Tables with Buckets

Buckets — each one is a cache line

Current Step

Complexity

Key Concepts

Knowledge Check

Closed Hash Tables with Buckets

Buckets — each one is a cache line

Current Step

Complexity

Key Concepts

Knowledge Check