Hashing (Hash Set)
Easy+70 XPStore values in buckets by value % size for O(1) average lookup.
No visualization loaded.
Watch
—
Press Run to begin.
Hashing is how you find something WITHOUT searching. Instead of scanning boxes, you use the value itself to compute exactly which shelf (bucket) it belongs on. To check if 42 is stored, you don't look everywhere — you compute its bucket and glance at just that one. It's like a coat-check: your ticket number tells you the exact hook, so you never hunt.
▸What does 'value % size' mean and why use it?
% is the remainder after division. With 10 buckets, the value 42 goes to bucket 42 % 10 = 2; the value 57 goes to 57 % 10 = 7. The remainder is always between 0 and size-1, so it's always a valid bucket number. That little formula is the 'hash function' — it turns any value into a shelf address instantly.
▸Why is this 'O(1)' — and what does O(1) even mean?
O(1) means 'constant time': the work doesn't grow as the data grows. To find a value you compute one bucket and look there — that's the same tiny amount of work whether you've stored 10 values or 10 million. Compare that to linear search's O(n) (look at everything). O(1) lookup is the fastest tier there is, and it's why hash sets/maps are everywhere.
▸What if two different values land in the same bucket?
That's called a collision, and it's normal — 42 and 52 both hash to bucket 2 with 10 buckets. The bucket just holds a little list, and you scan that short list. As long as buckets stay mostly small, lookups stay fast on average. That 'on average' is why we say O(1) AVERAGE, not guaranteed — a bad pile-up can slow one lookup down.
▸When would I NOT use hashing?
When you need order. A hash set throws values into buckets by their hash, so they're not sorted and you can't ask 'what's the smallest?' or 'give me everything between 10 and 20.' For instant 'is this exact value here?' hashing wins; for ordered questions, a sorted array + binary search wins.
How the work grows
O(1) average is instant — doesn't grow at all. You compute one bucket and look only there, so lookup time barely changes no matter how much data you store — that flat line is the best you can get. The cost is memory: the buckets must hold every value.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.