How Hash Maps Work

Hash Table Explained covers the textbook mechanism — a hash function, an array of buckets, collision resolution. Real language runtimes implement that mechanism in genuinely different, verifiable ways, and the differences aren't cosmetic: JavaScript's plain {} mostly isn't a hash table at all, Python's dict doesn't use chaining, and Java's HashMap quietly rewrites part of itself into a completely different data structure once a bucket gets crowded enough. This post goes under the hood of three concrete implementations rather than the general theory.

JavaScript: the object you use every day usually isn't a hash table

A plain object literal — { x: 1, y: 2 } — looks like the obvious JavaScript hash map. In V8 (Chrome and Node.js), it usually isn't one. V8 gives most objects a hidden class (also called a "shape") — a compiled description of exactly which properties an object has and their fixed memory offsets. Reading obj.x becomes "read the value at a known offset," not "hash the string "x" and look it up" — objects sharing the same set of properties in the same order share the same hidden class, which is also what makes V8's inline caching optimization possible. A real hash table lookup only kicks in when an object falls into what V8 calls dictionary mode — too many properties, properties added and deleted repeatedly, or property names that don't look like fixed identifiers. Dictionary mode is the fallback, not the default.

Map and Set (added in ES2015) are different — they're genuine hash tables from the ground up, specifically because arbitrary, dynamic keys are exactly what they're for. V8's implementation (based on Jason Orendorff's deterministic hash table design) uses separate chaining: each bucket holds a singly linked chain of entries, and the table resizes — doubling — once the entry count would exceed 2× the bucket count, a notably looser threshold than the 0.75 load factor covered for Java below. Insertion order is preserved by a separate dataTable array holding every entry in the order it was added; iterating a Map just walks that array directly rather than traversing buckets at all.

The practical takeaway: reaching for Map instead of {} when keys are genuinely dynamic isn't just a style preference — it's picking the data structure actually built for that job, instead of accidentally forcing a property-optimized object into its slower dictionary-mode fallback.

Python: dict doesn't chain at all — it probes

CPython's dict uses open addressing, not chaining — every entry lives directly in the table's own slot array, and a collision means checking other slots in that same array instead of walking a side chain. Which slot to check next comes from a specific perturbed pseudo-random probing formula, not a simple "try the next slot" linear scan:

perturb = hash
slot = hash & mask          # mask = table_size - 1

# on collision, repeat:
perturb >>= 5
slot = (slot * 5 + perturb + 1) & mask

Two keys that collide on their first slot don't just retry in lockstep — folding in perturb (derived from the hash's higher-order bits, which the initial hash & mask step ignored) sends them down different subsequent paths. Running this exact formula on two real hash values that collide at slot 5 in an 8-slot table:

Same starting collision, genuinely different paths afterward — that's the whole point of perturbing with the high bits instead of a fixed step size, since a fixed step (plain linear probing) would send every key that ever collides on slot 5 down the identical subsequent sequence, clustering hard around busy slots.

The payoff for probing instead of chaining is a compact dict design (standard since Python 3.6, with iteration-order preservation guaranteed by the language spec since 3.7): a small, sparse array of slot indices for hashing, pointing into a separate dense array holding the actual key/value entries in insertion order. That split is what gives CPython all three properties at once — O(1) average lookup, insertion-order iteration, and roughly 25% less memory than a naive single open-addressed table — rather than trading one for another.

Resizing triggers at a load factor of 2/3 full (not Java's 0.75, covered next) and typically doubles the table — a tighter threshold than either JS Map or Java HashMap, which makes sense for open addressing: a table that's allowed to get too full has nowhere left to probe into.

Java: HashMap quietly turns into a tree under load

Java's HashMap uses separate chaining with the default 0.75 load factor covered in Hash Table Explained — the one genuinely new piece of behavior, added in Java 8, is what happens when a single bucket's chain gets unusually long. Once a bucket's chain reaches 8 entries (TREEIFY_THRESHOLD) and the table itself has at least 64 buckets (MIN_TREEIFY_CAPACITY — below that, Java just resizes the whole table instead), that one bucket's linked list is converted into a red-black tree. Lookups, inserts, and removes within that specific bucket drop from O(n) to O(log n) — everywhere else in the table is completely unaffected. If the bucket later shrinks back down to 6 entries (UNTREEIFY_THRESHOLD), it converts back to a plain linked list; the gap between 6 and 8 exists specifically so a bucket hovering right at the threshold doesn't thrash back and forth between the two representations on every insert/remove.

Why 8 specifically: with a reasonable hash function and the default load factor, chain lengths follow a Poisson distribution where the probability of any bucket naturally reaching 8 entries is documented in the JDK's own source comments at roughly 0.00000006 — six in a hundred million. A bucket that actually gets there essentially never happens by chance; it's either a badly-distributed hashCode() implementation or a deliberately hostile key set, and the tree exists as a safety net for exactly that case rather than something normal operation ever exercises.

Same idea, three different trade-offs

None of these is objectively "faster" in general — chaining tolerates a table getting crowded gracefully (worst case, longer chains), while open addressing needs headroom to probe into but keeps every entry in cache-friendly contiguous memory when load factor stays low. Each language picked the trade-off that fit its own priorities: JS Map optimizing for simplicity and guaranteed order, Python dict for memory compactness given how pervasively it's used internally, Java HashMap for resilience against worst-case chains it can't fully prevent.

Try it yourself

Hash Table Visualizer runs the general separate-chaining mechanism described in Hash Table Explained step by step — the same core idea all three implementations above build on, before language-specific tuning takes over. See Array vs Linked List for exactly what a chained bucket's internal linked list costs once it gets long, which is the precise problem Java's treeification exists to cap.

FAQ

So is a JavaScript object a hash table or not?

It depends entirely on how it's used. Objects created and used with a fixed, consistent set of properties stay on V8's fast hidden-class path and never become a real hash table. Objects used more dynamically — properties added and removed unpredictably, used as an ad hoc string-keyed lookup table — get demoted into dictionary mode, which is a genuine hash table. Map skips this ambiguity entirely by always being a hash table, which is exactly why it exists as a separate type.

Why did Python only guarantee dict order in 3.7, but JS Map had it since 2015?

Different starting points, not different capability. Map was designed from scratch in the ES2015 spec with ordered iteration as a stated requirement from day one. Python's dict already existed for decades as an unordered structure by specification (even though a given CPython version's implementation might have happened to iterate consistently) — the compact dict redesign in 3.6 was what made ordering both free (no extra memory over the old design) and reliable enough to formally guarantee it in the language spec the following version.

Does treeification mean Java's HashMap is never O(n) worst case anymore?

No — it narrows the worst case, it doesn't eliminate it. Below MIN_TREEIFY_CAPACITY (64 buckets), a long chain still resizes the whole table rather than treeifying, and a small table can still have every key collide into one long chain in a genuinely pathological case. Treeification specifically caps the damage once the table is large enough for a single overloaded bucket to be the actual bottleneck, rather than the whole table being undersized.

Which of these is fastest?

There's no single answer that survives contact with a real workload — it depends on key distribution, table size, how full the table typically runs, and what the host language optimizes elsewhere (V8's inline caching alone can make a well-shaped plain object faster than any hash table for the specific case it's built for). Reasoning about the trade-off directly, the way this post does, beats trusting a general ranking that doesn't know your actual access pattern.