Skip to main content
Be Bitwise

Hashmaps in the Real World

Hashmaps & Hash Tables · Data & Hashing track

8 min read

In this module

Hashmaps Everywhere

Hash tables quietly run most of modern software. Once you step past the textbook version and into how real implementations actually behave, you become a much more dangerous programmer.

Language Implementations

Python's dict

Python's dict uses open addressing with a heavily-tuned probing scheme. The internal array keeps hash values right next to keys and values, so comparison is cheap — check the hash, fall through to a key comparison only when hashes already match. Since Python 3.7, dicts also preserve insertion order, courtesy of a separate compact array of indices riding alongside the storage.

Here's the shape of that layout for d = {"cat": 1, "dog": 2, "fish": 3} in an 8-slot table. The hash picks a slot in the small index array; the slot holds a position in the dense entries array, which is filled strictly in insertion order. Iterating the dict just walks the entries top to bottom. The slot numbers are illustrative, since they depend on the real hashes.

The index array is cheap to keep sparse because each slot is a single byte while the table has 128 slots or fewer, and the entries stay packed together. (Since 3.11, a dict whose keys are all strings drops the stored hash from each entry, because a str already caches its own.)

Java's HashMap

Java's HashMap uses separate chaining with linked lists. Once a chain stretches past eight elements, and the table already has at least 64 buckets (smaller tables just resize instead), the JVM quietly upgrades it to a balanced red-black tree, so even an attacker-stuffed bucket answers lookups in O(log n) rather than O(n). That bound leans on the keys implementing Comparable (as String does); keys that share a hash code and can't be compared still fall back to scanning. It's a half-decent defence against hash-flooding by accident of design.

Rust and C++ (SwissTable / abseil)

Google's SwissTable design (lurking inside Rust's standard library and C++ abseil) is open addressing on top of SIMD: a single SSE/NEON instruction probes a whole batch of buckets at once. The result is genuinely fast on modern CPUs. Sixteen buckets, one instruction.

The trick is a separate array of one-byte control bytes, one per slot. Each holds either a marker for empty or deleted, or the low 7 bits of the key's hash (called H2). The rest of the hash (H1) picks which group of 16 slots to start in. A lookup broadcasts H2 into a 16-byte register, compares it against the whole group in one go, and gets back a bitmask of candidate slots. Only those candidates get a full key comparison.

Key Concept

Production hash tables look very different from textbook ones. They lean on CPU-specific tricks like SIMD probing, swap data structures mid-flight when chains grow dangerous, and tune every constant against real hardware until the numbers stop moving.

Common Usage Patterns

Counting occurrences

text
function count_words(text) {
counts = new HashMap()
for word in split(text) {
if counts.contains(word) {
counts[word] = counts[word] + 1
} else {
counts[word] = 1
}
}
return counts
}

Deduplication

text
function remove_duplicates(list) {
seen = new HashSet()
result = []
for item in list {
if not seen.contains(item) {
seen.add(item)
append(result, item)
}
}
return result
}

Caching (Memoisation)

text
cache = new HashMap()
function fibonacci(n) {
if cache.contains(n) {
return cache[n]
}
if n <= 1 { return n }
result = fibonacci(n-1) + fibonacci(n-2)
cache[n] = result
return result
}

Without memoisation, the naive recursive fibonacci is O(2^n) — exponential, painful, and roughly proportional to how upset your laptop gets. With a hashmap cache, it collapses to O(n): each value is computed once and from then on read straight out of memory.

Grouping

text
function group_by_first_letter(words) {
groups = new HashMap()
for word in words {
letter = word[0]
if not groups.contains(letter) {
groups[letter] = []
}
append(groups[letter], word)
}
return groups
}

Here are three of those idioms with C++'s std::unordered_map and std::unordered_set. Run it, then delete the marked line in fib and compare the call counts. The word counts come out in whatever order the buckets happen to hold them, which can differ between standard libraries.

Try itCount, deduplicate and memoise; then remove the cache line and rerun.
C++ (GCC 9.2.0)

Hash Tables in Systems

DNS resolution caches. Your OS keeps recently-resolved domains in a hash table — domain name in, IP address out — so it doesn't hit the network every time you visit the same site twice in a row.

Database indexes. B-trees are the default, but databases like PostgreSQL and MySQL also ship hash indexes for cases where you only ever do equality lookups and never range queries.

Compiler symbol tables. Every variable name, function signature, and type the compiler sees lands in a hash table. Each subsequent reference to that name triggers a lookup to recover the type and the memory location.

Switches. MAC address tables are hash-backed so the device can decide which port a frame goes out of in well under a microsecond. IP routers are different: their forwarding decision is a longest-prefix match, which lives in tries or TCAM rather than a plain hash table.

Performance Pitfalls

Mutable keys are a footgun. Mutate an object after using it as a key and its hash changes — but the table still has it filed under the old bucket. The entry is now orphaned. It exists; nothing can find it.

Cheap hash functions invite collisions. Hash a string by its first character and every word starting with "a" lands in the same bucket. The structure gets the worst of every world.

Hash-flooding DoS preys on predictable hashing. An attacker fires thousands of requests with keys that all collide, dragging each lookup back to O(n). SipHash and friends — keyed, randomised — break the attacker's ability to predict where things land.

Unexpected rehashing causes latency spikes. Bumping a one-million-entry table to two million means reinserting all one million entries on the same insertion that triggered it. On a real-time server, that one operation is a visible pause in the latency graph.

When Not to Use a HashMap

Hash tables aren't always the right call:

  • Ordered iteration. Need to walk the keys in sorted order? Reach for a balanced BST (TreeMap) or just a sorted array.
  • Range queries. Pulling every key between A and B demands a structure that knows about ordering. A hash table doesn't.
  • Small collections. Below about 10–20 elements, a plain array with linear search is often the fastest thing on the planet — better cache locality, no bucket-array overhead, fewer indirections.
  • Tight on memory. Hash tables pay for the bucket array, the load-factor headroom, and per-entry bookkeeping. Arrays don't.

Knowing where the hash table loses is what separates a programmer with a toolbox from one who only ever swings the same hammer.

The Bigger Picture

Hash maps are probably the most consequential data structure in practical software engineering. Every non-trivial program has at least one, often dozens. Compiler symbol tables. Switch forwarding tables. Web caches. Database indexes. Mastering hash maps means looking past the three-method API (put, get, delete) and into the machinery that decides whether they hum or hitch under load. Once that landscape is familiar, you can pick the right structure, configure it without blindly copy-pasting defaults, and chase down latency regressions when they show up at 2am.