Hash maps

What it is and why it exists

A hash map stores key-value entries and supports lookup by exact key. Instead of scanning every entry, it computes a hash from the key and uses that number to choose a small part of its storage. Equality checks within that part confirm whether an entry is the requested one.

The structure exists because many programs ask the same shape of question repeatedly: which customer owns this ID, whether a token has been seen, or how many times a word occurs. A linear scan takes O(n) comparisons per query. A well-behaved hash map makes insertion, lookup, and deletion expected O(1) operations, so the work does not normally grow with the total number of entries.

The word “expected” carries the real contract. Multiple keys can choose the same storage location, and an implementation must still distinguish them. Storage also has finite capacity, so the table periodically grows and redistributes its entries.

A map is appropriate when the operation is exact-key lookup and useful ordering is absent. A sorted array or balanced tree is usually a better fit for predecessor queries, ranges, and ordered traversal. A direct array index is simpler when keys are already dense non-negative integers in a small known range.

Most languages expose a dictionary-like interface while hiding its representation. Python dict, Java HashMap, and many other collections use hash-table techniques, but their detailed layouts differ. ECMAScript requires Map to provide average sublinear access, yet does not require an engine to implement it as a hash table; this topic uses JavaScript Map only for its specified key behavior and builds a teaching table when internal mechanics matter.

The contract behind the interface

Every key passes through two decisions. The hash function chooses where to search, while equality decides whether a candidate is the same logical key. Neither decision can safely replace the other.

A hashable key has hash and equality behavior stable enough for the collection’s rules. The core consistency rule is one-way: if two keys are equal, they must produce the same hash. Unequal keys are allowed to produce the same hash, because the table has a collision strategy.

Hash maps are not merely caches. They implement indexes, symbol tables, adjacency maps, frequency counters, joins, deduplication sets, and registries. In each case, the hardest design choice is often the key’s meaning rather than the collection call itself.

How it works

At its simplest, a hash map owns an array of buckets. A hash function converts a key into an integer, and a reduction such as hash % capacity selects an array index. The selected bucket stores zero or more entries that may share that index.

Lookup and insertion

A lookup follows a narrow path:

1. Compute the key’s hash using the table’s configured hash function.
2. Reduce the hash to a bucket index for the current capacity.
3. Examine candidate entries along the table’s collision path.
4. Compare candidate keys with the requested key using the configured equality rule.
5. Return the matching value, or report that the key is absent.

Insertion begins with the same search. If an equal key already exists, the map updates that entry’s value without increasing its size. Otherwise, it adds a distinct entry and may trigger growth.

Deletion must preserve whatever search path lookup relies on. Removing a node from a chain is straightforward. An open-addressed table usually needs a tombstone or a cluster repair, because clearing a slot outright can make later collided entries unreachable.

Collisions are normal

A hash collision occurs when different keys lead to the same hash or bucket index. Since the key space is usually much larger than the bucket array, collisions are mathematically unavoidable. Correctness therefore comes from equality checks and collision handling, not from hoping that hashes are unique.

Separate chaining stores a collection of entries at each bucket. Lookup walks only the selected chain. The implementation is simple, and deletion does not disturb other buckets, but each chain adds allocation and pointer-traversal costs.

Open addressing keeps entries in the bucket array itself. On a collision, it probes other positions according to a rule such as linear, quadratic, or double hashing. This layout can improve locality, but probe behavior, deletion markers, and a nearly full table require care.

Load and growth

The load factor is the number of stored entries divided by the number of buckets. For chaining it predicts average chain pressure; for open addressing it predicts how hard it is to find an empty slot. Implementations choose different thresholds because layout, cache behavior, and memory goals differ.

When the threshold is crossed, a table normally allocates a larger bucket array and reinserts or relocates existing entries. Copying entries at their old indices is incorrect because the capacity participates in index selection. The same full hash can map to a different bucket after capacity changes.

A resize is O(n) for the operation that performs it. Geometric growth spreads those occasional copies across many cheap insertions, giving insertion amortized O(1) cost under normal assumptions. It does not make every individual insertion constant time.

Equality defines key identity

Different runtimes expose different equality policies. Java collections can receive an equality comparer ; Python keys use compatible __eq__ and __hash__; JavaScript Map uses SameValueZero . Under SameValueZero, NaN equals NaN, positive and negative zero are equal, and distinct objects compare by identity.

For a business key such as { warehouse, sku }, object identity is often not the intended meaning. You can use a canonical immutable string, an interned key object, or a language facility with value equality. The representation must be unambiguous: naïvely joining fields with a delimiter fails when a field can contain that delimiter.

Cost model

These bounds count table work, not the cost of hashing the key itself. Hashing a long string is proportional to the characters examined unless its hash is already cached. Calling a table operation “constant time” must not hide an unbounded key-size cost.

Examples

The examples separate observable language semantics from teaching internals. All three files were run with the local Node 24 runtime, and each output below is the captured result.

Observing key equality

JavaScript Map makes object identity and SameValueZero visible without exposing buckets. Two objects with the same fields remain distinct keys, while repeated NaN and signed zero keys address existing entries.

The second NaN assignment updates the first, and +0 finds the value stored with -0. The fresh object literal does not find firstOrder, because equal fields do not change object identity. Nothing in this result proves that the engine uses buckets; it demonstrates only the specified key relation.

priceByKey.get() also cannot distinguish a missing key from a present key whose value is undefined. Use priceByKey.has(key) when that distinction affects behavior. A sentinel value is another option when the surrounding API can reserve one safely.

Handling collisions and resizing

This small map accepts string keys, uses separate chaining, and grows when its load factor exceeds 0.75. It is a teaching implementation rather than a replacement for the runtime collection: it omits deletion, validation, iteration APIs, and production hash hardening.

class StringHashMap {
  constructor(capacity = 4) {
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }
  hash(key) {
    let hash = 2166136261;
    for (const character of key) {
      hash = Math.imul(hash ^ character.codePointAt(0), 16777619) >>> 0;
    }
    return hash;
  }
  set(key, value) {
    const bucket = this.buckets[this.hash(key) % this.buckets.length];
    const entry = bucket.find(([storedKey]) => storedKey === key);
    if (entry) {
      entry[1] = value;
      return;
    }
    bucket.push([key, value]);
    this.size += 1;
    if (this.size / this.buckets.length > 0.75) this.resize();
  }
  get(key) {
    const bucket = this.buckets[this.hash(key) % this.buckets.length];
    return bucket.find(([storedKey]) => storedKey === key)?.[1];
  }
  resize() {
    const entries = this.buckets.flat();
    this.buckets = Array.from({ length: this.buckets.length * 2 }, () => []);
    this.size = 0;
    for (const [key, value] of entries) this.set(key, value);
  }
}
const balances = new StringHashMap();
[["apples", 5], ["pears", 3], ["plums", 8], ["melon", 2]]
  .forEach(([key, value]) => balances.set(key, value));
console.log(`capacity: ${balances.buckets.length}`);
console.log(`values: ${balances.get("apples")}, ${balances.get("plums")}`);
console.log(`bucket sizes: ${balances.buckets.map((bucket) => bucket.length).join(",")}`);

capacity: 8
values: 5, 8
bucket sizes: 1,0,1,0,2,0,0,0

The fourth distinct insertion takes the load from 3/4 to 4/4, crosses the threshold, and doubles capacity to eight. Every old entry passes through set() again, so it receives an index based on the new capacity. Resetting size before reinsertion keeps the count correct.

The final bucket sizes contain a 2: "apples" and "melon" collide at bucket four even after growth. Both lookups remain correct because the bucket retains full keys and get() checks equality. Storing only their hashes would lose that distinction.

The hash loop uses Unicode code points and 32-bit multiplication to make the example deterministic. It is not a claim that FNV-style hashing is suitable for hostile input, nor does it reproduce a JavaScript engine’s internal hash. Production collections may randomize hashes or use other defenses.

Building a composite business key

When callers reconstruct key objects, JavaScript object identity cannot express value equality. A canonical string can, provided its encoding preserves field boundaries. Length prefixes avoid the ambiguity of simply joining fields with ":".

function canonicalSkuKey({ warehouse, sku }) {
  return `${warehouse.length}:${warehouse}${sku.length}:${sku}`;
}

const stock = new Map();
const parisWidget = { warehouse: "PAR", sku: "W-7" };
stock.set(canonicalSkuKey(parisWidget), 12);

const lookup = { sku: "W-7", warehouse: "PAR" };
console.log(`key: ${canonicalSkuKey(lookup)}`);
console.log(`stock: ${stock.get(canonicalSkuKey(lookup))}`);

lookup.sku = "W-8";
console.log(`after mutation: ${stock.get(canonicalSkuKey(lookup))}`);
console.log(`original: ${stock.get(canonicalSkuKey(parisWidget))}`);

key: 3:PAR3:W-7
stock: 12
after mutation: undefined
original: 12

Property order does not matter because the function reads named fields in a fixed order. Mutating lookup changes the derived key for later lookups, but it cannot move or corrupt the already stored string key. The original record still derives the original key.

Canonicalization must also define types, normalization, case rules, and missing values. If warehouse identifiers are case-insensitive, normalize them before encoding and apply the same rule on every insertion and lookup path. For arbitrary structured data, prefer a specified serialization or a value-key facility over inventing an incomplete encoding.

Pitfalls

Treating the hash as identity

Fix: retain the full key or an equivalently collision-free canonical representation and compare candidates with the defined equality rule. Test two deliberately colliding keys and confirm that both values remain reachable.

Breaking the hash-equality contract

Fix: derive equality and hashing from the same immutable fields and normalization steps. Prefer immutable key types; otherwise remove an entry before changing key fields and insert it again afterward.

Promising worst-case constant time

Fix: say expected O(1) under controlled load and adequate hash distribution. Bound untrusted key sizes, use runtime-provided hardened collections, and benchmark representative and adversarial distributions when latency matters.

Resizing without rehashing

Fix: reinsert or correctly relocate every live entry according to the new table geometry. Test lookups for all entries immediately before and after each growth boundary, including colliding keys.

Confusing absence with a stored value

Fix: use the collection’s membership operation, such as Map.has(), or return a tagged result that separates presence from value. Include each falsey value and one absent key in tests.

Using a plain object as an untrusted dictionary

Fix: use Map when keys are arbitrary, or create a null-prototype object when string-property interoperability is required. Validate keys at trust boundaries and use own-property checks rather than inherited membership.

Further reading

• ECMAScript Language Specification: Map Objects
• Java SE 25 API: HashMap
• Python 3.14 documentation: mapping types
• The Go Programming Language Specification: map types
• MDN Web Docs: Map