Arrays and Hash Maps: Engine Internals and Performance Reality

Theoretical complexity hides the real story. Dense JavaScript arrays usually deliver fast indexed access, but a single sparse write can push V8 into slower dictionary-style storage with very different constants. Map and plain objects both promise average-case O(1) lookups until collisions, resizing, or shape pollution dominate the hot path. This article walks through V8’s internal representations — elements kinds for arrays, hidden classes for objects, and Tyler Close’s ordered hash tables for Map/Set — so you can predict when these structures actually deliver their advertised performance and when they collapse to slow modes.

Abstract

Memory layout often dominates algorithmic complexity in real-world performance. Arrays exploit CPU cache lines through contiguous allocation — accessing adjacent elements is nearly free when they share a 64-byte cache line on x86 and most ARM cores. Hash tables trade memory for constant-time lookups, but their load factor and collision strategy decide whether Map.get is a couple of memory loads or a long chain walk.

V8 maintains multiple internal representations for both structures. Arrays transition through 21 “elements kinds” — from PACKED_SMI_ELEMENTS (fastest) to DICTIONARY_ELEMENTS (slowest) — and those transitions are essentially one-way. Objects use hidden classes that enable monomorphic inline caches; adding properties dynamically or deleting them forces costly shape transitions. Map and Set use Tyler Close’s deterministic hash table¹ to satisfy the ECMA-262 insertion-order iteration requirement — a hash table for lookup chained against a data table for iteration order.

The critical insight: writing arr[1000] = x on an empty array, deleting object properties, or creating polymorphic call sites permanently degrades performance. Understanding those transitions matters more than memorizing Big O notation.

V8 Array Internals: Elements Kinds

V8 currently distinguishes 21 elements kinds based on what an array can hold and whether it has gaps. The engine emits specialized machine code per kind, and transitions move only “downward” through a lattice from specific to more general. Once an array becomes HOLEY_* or PACKED_DOUBLE_* it stays there for its lifetime — Array.prototype.fill does not re-pack a holey array, even when called over the entire range, because V8 deliberately lets representations stabilize rather than flip-flopping².

The Elements Kind Hierarchy

The most common kinds, ordered from fastest to slowest:

Show 2 hidden lines3const arr = [1, 2, 3] // PACKED_SMI_ELEMENTS (optimal)4arr.push(4.5) // → PACKED_DOUBLE_ELEMENTS (still good)5arr.push("string") // → PACKED_ELEMENTS (boxed, slower)6arr[100] = "x" // → HOLEY_ELEMENTS (permanent hole)7// Cannot revert to PACKED_* even if you fill indices 4-99

Why Holes Are Expensive

Holes force every read to first check the elements store for V8’s internal the_hole sentinel and, if it matches, walk the prototype chain looking for a real binding. The V8 team is explicit that “operations on holey arrays require additional checks and expensive lookups on the prototype chain”³. Reading past array.length triggers the same out-of-bounds prototype walk and permanently demotes the load site — fixing one off-by-one in a hot loop has been measured at 6× faster in V8 micro-benchmarks³.

Show 2 hidden lines3const arr = [1, , 3] // HOLEY_SMI_ELEMENTS45// Accessing arr[1] requires:6// 1. Probe arr's elements store at index 1 → finds the_hole sentinel7// 2. Walk Array.prototype, Object.prototype looking for index 18// 3. Return undefined910// Contrast with packed array:11const packed = [1, 2, 3]12// Accessing packed[1]:13// 1. Direct memory read at (base + 1 * element_size)14// 2. Return value

Dictionary Mode: When Arrays Become Hash Maps

Sparse arrays — those with large gaps between indices — switch to dictionary-mode elements, sometimes called slow elements in the V8 source. The exact heuristic is not part of the public contract, but in practice V8 falls back when allocating a dense backing store would waste too much memory relative to occupied slots⁴.

Show 2 hidden lines3const arr = []4arr[0] = "first"5arr[1000000] = "sparse" // DICTIONARY_ELEMENTS67// Now arr[0] access requires:8// 1. Hash the key "0"9// 2. Probe the hash table10// 3. Return value if found1112// Memory comparison (approximate):13// Dense arr[0..999999]: ~8MB (1M × 8 bytes)14// Sparse with 2 elements: ~140 bytes (hash table overhead)

Dictionary mode makes sense for genuinely sparse data. The trade-off: random access degrades from O(1) direct indexing to O(1) average hash lookup with potential O(n) worst-case on collision chains.

V8 Object Internals: Hidden Classes and Shapes

Objects in V8 use hidden classes (also called “shapes” or, internally, “maps” — not to be confused with the JavaScript Map data structure). A hidden class describes an object’s memory layout: which named properties exist and at what offset, the object’s prototype, and a transition tree linking related shapes.

Shape Transitions and Inline Caching

When V8 first sees a property access like obj.x, it doesn’t know where x is stored. After the first access, it caches the property’s offset for that shape. Subsequent accesses to objects with the same shape use this “inline cache” for direct memory access.

Show 2 hidden lines3// All objects with same property order share a hidden class4function createPoint(x, y) {5  const p = {}6  p.x = x // Transition: {} → {x}7  p.y = y // Transition: {x} → {x, y}8  return p9}1011const p1 = createPoint(1, 2)12const p2 = createPoint(3, 4)13// p1 and p2 share the same hidden class1415function getX(point) {16  return point.x // After first call: inline cached17}1819getX(p1) // Misses cache, caches offset for shape {x,y}20getX(p2) // Hits cache! Direct memory read at cached offset

Polymorphism Kills Performance

When a function receives objects with different shapes, V8’s inline cache becomes “polymorphic” (2-4 shapes) or “megamorphic” (many shapes). Megamorphic sites abandon caching entirely.

Show 2 hidden lines3function getX(obj) {4  return obj.x5}67// Creating objects with different shapes8const a = { x: 1 } // Shape: {x}9const b = { y: 2, x: 3 } // Shape: {y, x} — different!10const c = { x: 4, y: 5 } // Shape: {x, y} — also different!11const d = { z: 6, x: 7 } // Shape: {z, x}12const e = { x: 8, z: 9 } // Shape: {x, z}1314// Calling with many shapes forces megamorphic15;[a, b, c, d, e].forEach(getX)16// getX is now megamorphic — falls back to dictionary lookup

Delete Destroys Optimization

The delete operator is particularly expensive. It typically forces the object into slow / dictionary properties⁴, an in-object representation that drops the descriptor array and disables inline caches for that object.

Show 2 hidden lines3const obj = { a: 1, b: 2, c: 3 }4// obj uses fast properties (hidden class)56delete obj.b7// obj transitions to dictionary mode8// All subsequent property accesses use hash lookups910// Preferred alternative:11const obj2 = { a: 1, b: 2, c: 3 }12obj2.b = undefined // Maintains shape, just clears value13// obj2 keeps fast properties

Hash Map Internals: V8’s Deterministic Hash Tables

JavaScript’s Map and Set must iterate in insertion order — Map.prototype.forEach is specified to visit each [[MapData]] record “in original key insertion order”⁵. A textbook open-addressed hash table reorders keys on every rehash, so V8 implements Map/Set with an OrderedHashTable modelled on Tyler Close’s deterministic hash table¹⁶.

Dual Data Structure Design

V8’s OrderedHashTable keeps two cooperating regions in a single backing store:

1. Hash table — numBuckets head-of-chain indices, sized to a power of two.
2. Data table — entry records appended strictly in insertion order; each record carries a key, value(s), and a chain field linking to the next entry in the same bucket.

Lookup: hash the key → mask to a bucket → follow the bucket’s head index into the data table → walk the chain via per-entry next indices. Iteration: walk the data table from index 0 to NumberOfElements + NumberOfDeletedElements, skipping tombstones. This is O(n) overall and O(1) per element.

Hash Code Computation

V8 computes hash codes differently by key type:

The per-object value is just a random number, independent of the object’s contents — V8 cannot recompute it later, so it must store it⁸. Random per-object hashes prevent attackers from predicting which object keys will collide; string-keyed maps remain exposed via the string-table CVEs covered in the next section.

Memory Optimization: Hash Code Hiding

When a JavaScript object is used as a Map/WeakMap key, V8 needs to remember a per-object hash code. Storing it as a private symbol used to trigger a hidden-class transition on the key, polluting unrelated property accesses. V8 6.3 moved the hash code into the object’s own properties backing store⁸:

• Empty properties store — write the hash code directly into that slot on the JSObject.
• Array-backed properties store — that array is capped at 1022 entries, so its length only needs 10 of the 31 Smi bits. V8 packs the 21 spare bits with the hash code.
• Dictionary-backed properties store — add one extra slot at the head of the dictionary for the hash code; the relative cost is low because dictionaries are already large.

This change yielded a ~500% improvement on the SixSpeed Map/Set benchmark and a ~5% improvement on ARES-6 Basic⁸. It is an optimisation about how object keys are hashed, not about Map’s own size; a Map itself can hold many more than 1022 entries.

Collision Resolution and HashDoS

V8 does not use one collision strategy for every internal hash table. The two most relevant for application-level performance are:

For an OrderedHashTable, every collision walks the chain via the per-entry chain slot. With pathological inputs an attacker can force every key into one bucket, degrading lookup and insertion to O(n) per operation and O(n²) for a batch insert. The string table is similarly vulnerable: its quadratic probe sequence becomes a linear walk if every key lands on the same first-probe slot⁷.

Recent HashDoS CVEs in Node.js

• CVE-2025-27209 — V8’s switch to the rapidhash string hash in Node.js v24.0.0 left the algorithm constants hard-coded instead of seeded. An attacker who could feed strings into the server (JSON keys, query parameters, header names) could pre-compute colliding inputs without knowing any runtime secret. Affects only the 24.x release line; fixed in Node.js v24.4.1 by reverting to a seeded hash and later wiring up rapidhash’s seed-generation routine⁹⁷.
• CVE-2026-21717 — V8 stores the hash of an “array-index string” (a decimal-integer string whose value fits in 24 bits) directly as (length << 24) | value. Because that hash was deterministic and unseeded, a remote attacker could use a 2 MB JSON payload to wedge JSON.parse for ~30 seconds on a fast laptop. Mitigated in the March 2026 Node.js security release with a new seeded, efficiently invertible permutation hash for integer-index strings⁷.

Show 2 hidden lines3// If an attacker can choose keys that collide on the same bucket4// (string table) or the same Map bucket (OrderedHashTable):5const map = new Map()6for (const k of attackerControlledKeys) map.set(k, 1) // O(n) per insert7// Total: O(n²); with ~2 MB payload this stalls the event loop for tens of seconds.89// Mitigations: keep Node.js patched, JSON-schema-validate untrusted input,10// cap request size and key cardinality, and avoid using attacker-controlled11// strings as Map keys without normalization.

Load Factor and Resizing

V8’s OrderedHashTable uses a load-factor constant of 2 entries per bucket: capacity = numBuckets × 2, both always powers of two⁶. An empty Map starts with 2 buckets and capacity 4. When inserting would exceed capacity (counting present + tombstoned entries), V8 rehashes:

1. Allocate a new table, doubling numBuckets and rounding to a power of two.
2. Re-mask each live key into its new bucket.
3. Copy live entries to the new data table in their current insertion order.
4. Discard tombstones.

The same routine compacts the table (without growing it) when the deleted-element count dominates. Rehashing is O(n) per event but amortises to O(1) per insertion; in latency-sensitive code paths the spike still matters and is worth pre-sizing around when the working-set size is known.

Map vs Object vs Array: When to Use Each

Benchmark Reality

Microbenchmarks often show Map outperforming Object for dynamic keyed workloads, especially when inserts and deletes dominate. The exact ratios vary heavily with engine version, key distribution, object shape stability, and whether the benchmark accidentally rewards monomorphic property access. Treat benchmark tables as workload-specific evidence, not universal multipliers.

Objects still win when the shape is stable and properties are accessed through monomorphic call sites. For dynamic keyed collections, Map is usually the safer default.

Cache Locality: Why Memory Layout Matters

Modern CPUs fetch memory in cache lines — 64 bytes on x86_64 and most ARMv8 cores, 128 bytes on Apple Silicon performance cores. Accessing one element loads adjacent bytes for free, so contiguous traversal of a Float64Array reads roughly one cache line per eight elements while a sparse hash-table walk often pays one cache miss per lookup.

Array Contiguous Advantage

Show 2 hidden lines3// Cache-friendly: sequential access4const arr = new Array(1000000).fill(0)5for (let i = 0; i < arr.length; i++) {6  arr[i] += 1 // Adjacent memory, cache hits7}89// Cache-hostile: random access10const indices = [...Array(1000000).keys()].sort(() => Math.random() - 0.5)11for (let i = 0; i < indices.length; i++) {12  arr[indices[i]] += 1 // Random jumps, cache misses13}1415// On commodity hardware sequential access is typically several times16// faster than random access on the same data, driven almost entirely17// by L1/L2 hit rate. The exact multiplier depends on working-set size,18// CPU prefetcher, and DRAM latency — measure before quoting numbers.

Typed Arrays: Maximum Cache Efficiency

For numeric data, TypedArrays are the only structure the spec guarantees is backed by an ArrayBuffer with a fixed element width and contiguous bytes:

Show 2 hidden lines3const floats = new Float64Array(1000000)4// Guaranteed: 1000000 × 8 bytes = 8MB contiguous56// Regular array equivalent:7const regular = new Array(1000000).fill(0.0)8// V8 may optimize to contiguous doubles, or may not9// Adding a string element forces reallocation1011// TypedArrays: fixed size, fixed type, maximum cache efficiency12// Regular arrays: flexible, but optimization is fragile

Practical Recommendations

For Arrays

1. Pre-allocate when size is known: new Array(n).fill(defaultValue) creates a packed array
2. Avoid holes: Never skip indices or use delete arr[i]
3. Keep types homogeneous: Mixing integers and floats transitions to PACKED_DOUBLE; adding strings transitions to PACKED_ELEMENTS
4. Use TypedArrays for numeric data: Guarantees contiguous memory and type stability

For Objects

1. Initialize all properties in constructors: Establishes stable shape early
2. Add properties in consistent order: Objects with properties added in same order share hidden classes
3. Never use delete: Set to undefined or null instead
4. Avoid dynamic property names in hot paths: Use Map instead

For Maps

1. Default choice for dynamic keyed collections: Designed for frequent add/remove
2. Use when keys aren’t strings: Objects coerce keys; Maps preserve type
3. Use when insertion order matters: Guaranteed iteration order
4. Consider memory overhead for small collections: Object may be more efficient for <10 fixed keys

Conclusion

Big O notation describes algorithmic bounds, not real-world performance. V8’s internal representations — elements kinds for arrays, hidden classes for objects, ordered hash tables for Map/Set — determine actual execution speed, and most of the bad news is one-way: a single sparse write, an out-of-bounds read, a delete, or a megamorphic call site can demote a hot path for the lifetime of that data structure.

Three practical heuristics carry most of the weight:

1. Keep arrays dense, homogeneous, and inside length. If they’re fundamentally numeric, prefer a TypedArray.
2. Initialize object properties in the same order in every constructor; never delete. Set to undefined if you need to clear.
3. Reach for Map (or Set) the moment your collection is dynamic, has non-string keys, or needs guaranteed iteration order — and pre-size it when you know the working-set size, to avoid mid-request rehash spikes.

For untrusted input, also keep your Node.js patched against the most recent string-table CVEs and validate / size-cap any payload that becomes hash-table keys.

Appendix

Prerequisites

• Big O notation and amortized analysis
• Basic understanding of hash tables and collision resolution
• JavaScript object and array fundamentals

Terminology

• Elements kind: V8’s internal classification of array contents determining storage and access strategy
• Hidden class / Shape: V8’s internal description of an object’s property layout enabling inline caching
• Inline cache (IC): Cached property offset enabling direct memory access without property lookup
• Monomorphic: Call site that always sees one shape; optimal for inline caching
• Polymorphic: Call site seeing 2-4 shapes; uses polymorphic inline cache
• Megamorphic: Call site seeing many shapes; abandons inline caching
• Dictionary mode: Fallback to hash table storage when fast properties aren’t possible
• Load factor: Ratio of entries to buckets in a hash table; affects collision probability
• HashDoS: Denial-of-service attack exploiting hash collisions to degrade O(1) to O(n)

Summary

• V8 arrays have 21 elements kinds; transitions from packed to holey/dictionary are permanent
• V8 objects use hidden classes; maintaining consistent shapes enables inline caching
• delete forces dictionary mode on objects—set to undefined instead
• Maps use deterministic hash tables: hash table for lookup, data table for insertion-order iteration
• Cache locality often matters more than algorithmic complexity—contiguous beats sparse
• HashDoS attacks can degrade hash table operations from O(1) to O(n)

References

• ECMA-262, latest editor’s draft — ECMAScript Language Specification, including Map/Set insertion-order requirements and TypedArray semantics.
• Elements kinds in V8 — V8 blog on array internal representations and the lattice of transitions.
• Fast properties in V8 — V8 blog on hidden classes, in-object / fast / slow properties, and hole semantics.
• Optimizing hash tables: hiding the hash code — V8 blog on storing object hash codes inside the properties backing store.
• V8 source — src/objects/ordered-hash-table.h — primary source for Map/Set internals (load factor, chain layout).
• V8 Deep Dives: Understanding Map Internals — annotated walk-through of OrderedHashTable.
• Node.js — July 2025 security releases (CVE-2025-27209) — official advisory for the rapidhash HashDoS.
• Node.js — Developing a HashDoS-resistant integer hash for V8 (March 2026) — design write-up for the CVE-2026-21717 mitigation.
• A tour of V8: object representation — older but still useful deep dive into V8 object internals.