Hash Maps

The array's O(1) lookup has a strict condition attached: you must know the numeric index. Real programs mostly do not. They want the account for a username, the price for a product code, the handler for an opcode name. The structure answering that need sits inside every language in this Academy, as Lua tables, JavaScript objects and Maps, Python dicts, PHP arrays, Ruby hashes, Go maps, Java HashMaps. All are the same machine under the hood: the hash table, and its design is one long, elegant answer to a single question: how do you turn an arbitrary key into an array index?

From key to bucket

Step one: a hash function digests any key, whatever its type or length, into a number, its hash code. A good hash function is deterministic, the same key always yields the same number, fast, and scattering: similar keys should produce wildly different numbers, spreading keys evenly across the numeric range. Step two: fold that number into the range of the backing array, classically by taking the remainder after dividing by the array's size. Key in, hash out, remainder taken, and you have a bucket index. Lookup, insertion, and deletion all start with this same two-step address computation, which costs O(1).

Think of a coat check with 8 numbered cubbies and a rule instead of a clerk: take your ticket number, divide by 8, and the remainder tells you the cubby. Ticket 12 goes to cubby 4, ticket 21 to cubby 5, ticket 30 to cubby 6. Nobody searches anything: the rule computes the location. And notice something useful, the rule works no matter how many tickets exist, because the remainder always lands between 0 and 7.

Collisions are not a bug

Infinitely many possible keys, finitely many buckets: by the pigeonhole principle, some distinct keys must share a bucket. That event is a collision, and it is a certainty to be managed, not a failure to be avoided. The classic management strategy, chaining, makes each bucket the head of a little linked list, the structure from last lesson doing exactly the job it is best at. Insert: hash to a bucket, splice into its chain. Look up: hash to a bucket, walk its chain comparing keys. The alternative family, open addressing, stores entries in the array itself and probes forward from an occupied slot; both appear in production runtimes, and chaining is the cleaner one to reason about first, which is why Open Data Structures and 6.006 both start there.

The playground shows the failure mode in miniature: keys 12, 21, and 30 differ by 9, so a 9-bucket table maps all of them to bucket 3, one long chain doing linear-search work while eight buckets sit empty. Real hash tables defend against such patterns by choosing table sizes and hash functions that break up key regularities, and modern runtimes go further, seeding their string hashes with a random value per process. That last defense is not academic: it exists because attackers once discovered they could send web servers thousands of keys crafted to collide, turning every O(1) lookup into O(n) and the whole table into O(n^2) behavior, a denial-of-service attack built purely on complexity analysis. Worst case versus average case, weaponized.

Load factor and the familiar resize

How full a table is allowed to get is its load factor: entries divided by buckets. Chains average load-factor entries each, so lookups stay O(1) on average as long as the load factor is capped by a constant. When insertions push past the cap, commonly around 0.75, the table resizes: allocate a bigger backing array, usually about double, and rehash every entry into its new bucket, since the remainder rule changed with the size. This is the dynamic array's growth story replayed: an occasional O(n) rebuild, amortized to O(1) per insertion by geometric growth. The two structures even fail the same way, a burst of inserts landing on a resize pays a visible pause.

The complete price list, honestly stated

• Lookup, insert, delete by key: O(1) on average, with a healthy hash function and capped load factor.
• Worst case for all three: O(n), when keys collide into one chain, whether by bad luck, bad table size, or adversarial construction.
• Iteration over all entries: O(n), but in no meaningful order, hash order is scrambled by design.
• Space: O(n), plus the overhead of buckets kept deliberately underfull.

That no meaningful order line is a real limitation, not a footnote. A hash map cannot answer range questions, all keys between A and F, or nearest-key questions, without scanning everything, because scattering keys uniformly is precisely what its hash function is for. Ordered-key workloads belong to the tree structures of the next lessons, which keep keys sorted and answer such queries in O(log n). Choosing between hash and tree maps is choosing which question shape your program asks most.

Hash maps in protected code

You have already relied on this structure everywhere in the Academy without naming it: every Lua table holding obfuscated state, every dispatch table mapping opcode numbers to handler functions in a virtualized program, every symbol table a compiler or deobfuscator builds while renaming identifiers. The dispatch loop lesson's table-based handler selection is a hash lookup in the hot path, chosen precisely because it is O(1) on average. And from the analyst's chair, key-value shapes in dumped memory, pairs of related values clustered in buckets, are among the most legible structures a reverse engineer can find, which is why serious protection moves sensitive mappings out of plain table shapes altogether.

A hash map turns any key into a bucket index: hash the key, take the remainder by the table size. Collisions are inevitable and chaining absorbs them with per-bucket linked lists. Capped load factor plus geometric resizing keeps operations O(1) on average, while the worst case remains O(n) and can be forced by adversarial keys. Fast by key, useless for ordered queries.

Frequently asked questions