Arrays vs hash tables: what a lookup costs, measured

A post on X claimed: "In performance optimization, the data structure I least want to use is a hash (only as a last resort), and the one I most want to use is an array. When a database is full of hashes, there's probably a lot of optimization opportunity hiding in there." This experiment tests that claim. It runs a GROUP BY key, SUM(amount) loop over 20 million rows four ways, from a string-keyed std::unordered_map down to a plain array indexed by id, and measures time and memory at different group counts. The widgets on this page model what each structure looks like in memory and how its read pattern interacts with a CPU cache, so you can change the configuration and watch the effect. The benchmark sources are linked in Setup.

The Question

How much slower is a hash table than an array for the same job, and why? When does the difference show up, and when is a hash table the right choice?

Setup

Hardware: Apple M4 Max. Each performance core has a 128 KB L1 data cache, and each cluster of performance cores shares a 16 MB L2 cache.
Compiler: Apple clang with -O2 -std=c++20 -mcpu=native. Single-threaded.
Workload: 20M rows of (id, amount) with ids drawn uniformly from [0, G). G (the number of distinct groups) is set to 100, 10K, 1M, or 10M.
Runs: each configuration ran twice. The runs agreed within 10%. The tables show the first run.
Sources: groupby.cpp, order.cpp, smalln.cpp, mem.cpp.

The four structures compared:

Name (short)	What it is
`unordered_map<string>` (string map)	`std::unordered_map<std::string, int64_t>`. Keys look like `user_1000000123`. This is what you get when ids come out of JSON or a row store as text.
`unordered_map<u32>` (u32 map)	The same node-based table with integer keys.
flat open-addressing (flat hash)	A hash table stored in flat arrays: linear probing and a power-of-two capacity, sized to twice the number of groups. This is the design behind SwissTable and Go 1.24 maps, simplified.
`array[id]` (array)	`std::vector<int64_t> sums(G); sums[id] += amount;`. It works only because the ids are dense, `0..G-1`.

Background: what one lookup touches

A CPU does not read single bytes from memory. It reads a whole cache line, which is 64 bytes on x86 and most ARM cores. Apple Silicon reports 128-byte lines, but the ratios below stay the same. A read that finds its line in L1 costs about a nanosecond. A read that goes to DRAM costs about 100 ns. So the useful cost measure for a data structure is how many distinct cache lines one lookup touches, and whether those lines are likely to be in cache already.

The widget below lays out each structure byte by byte in 64-byte lines. It uses libc++'s real node sizes (32 B nodes for u32 keys and 48 B for string keys, both confirmed with mem.cpp). Click any colored cell, or press play, to watch a lookup step through memory.

Structure

Key type

Entries: 16

valuekeypointerhash / control byteempty slot / paddingother program data

Each strip is one 64-byte cache line, split into sixteen 4-byte cells. Numbered rings show which lines a lookup reads, in order.

Things to try:

Array with 16 entries: 128 bytes, two lines, and every byte is a value. A lookup is base + id × 8: one line, with no hashing and no key comparison.
Flat hash, same 16 entries: a lookup reads a control byte, then the slot. That is two lines instead of one. Half the slots are empty by design, because a 50% load factor keeps probe sequences short.
Chained hash: a lookup reads the bucket array, then follows a pointer to a node allocated somewhere on the heap. The nodes sit wherever malloc put them, mixed in with other allocations. Each node also carries a next pointer and a cached hash.
Switch the key type to string and watch the node grow to 48 bytes, most of it key. The strings here are 15 characters, so they fit inside libc++'s 24-byte small-string buffer. A key longer than 22 characters adds one more pointer hop to a separate heap buffer.

Experiment 1: GROUP BY with four structures

Why this matters

Grouped aggregation is the inner loop of most analytic queries, and it is where a database most often reaches for a hash table. If arrays win anywhere, they win here.

Hypothesis

With a small number of groups everything fits in cache, so the structures differ only by instruction count: hashing and key comparison versus address arithmetic. Expect a 5–10× gap. Once the table outgrows cache, the gap should widen, because hashing scatters accesses and the node-based table adds a pointer hop to every lookup.

Method

groupby.cpp runs each structure over the same 20M-row input for each G. The string keys are built before timing starts, so the timed loop measures only hashing and lookup. A checksum over the finished table confirms that every method produced the same total. Memory was measured separately in mem.cpp with malloc_zone_statistics, one structure at a time. The first attempt measured memory inside the timed benchmark and picked up leftovers from the previous structure, which added about 25 MB to the array at 10M groups.

Results

Distinct groups (G)

Measured on an M4 Max, 20M rows. Both axes are log scale. The dashed lines on the memory chart mark the L1 (128 KB) and L2 (16 MB) cache sizes.

Time per row, in ns:

Groups	string map	u32 map	flat hash	array
100	12.80	2.29	2.69	0.35
10K	19.32	2.80	3.03	0.34
1M	83.57	20.84	6.44	0.90
10M	165.28	80.39	13.91	2.59

Memory for the finished table, in MB:

Groups	string map	u32 map	flat hash	array
1M	61.2	45.2	27.3	8.0
10M	585.4	425.4	436.2	80.0

What this tells us

The hypothesis was too low when everything fits in cache. At 100 groups the array is 6.5× faster than the best hash table, and 36× faster than string keys. The array loop costs about 1.5 cycles per row. The string version spends its time hashing 15 bytes and comparing them again on every row.
The node-based table falls behind as soon as it leaves cache. From 10K to 1M groups, unordered_map<u32> slows down 7.4× while the flat table slows down only 2.1×. The extra pointer hop per lookup is a second likely cache miss.
A good hash table narrows the gap but does not close it. At 10M groups the flat table is 5.8× faster than unordered_map<u32>, and still 5.4× slower than the array.
Density decides what fits in cache. At 1M groups the array is 8 MB and fits in L2. Every hash table is 27–61 MB and does not. The array uses 8 bytes per group. The flat table uses 27 bytes per group at the same count, because it stores keys, keeps half its slots empty, and needs control bytes. The node-based tables use 45–61 bytes per group.
The flat table's advantage is smallest when everything fits in cache. At 100 groups it is slightly slower than unordered_map<u32>, because its hash function costs more than libc++'s identity hash for integers. Layout only starts to matter once memory is the bottleneck.

Experiment 2: Read patterns and the cache

Why this matters

Experiment 1 shows that cost jumps once the table outgrows cache. This experiment isolates why: it is the access pattern, not just the size. A hash function is designed to scatter keys, and scattered keys make scattered reads.

Hypothesis

For the same array at 10M groups, processing rows in id order should be several times faster than processing them in random order. In id order, consecutive rows hit the same or neighbouring cache lines, and the hardware prefetcher can see the pattern.

Method

The toy simulator below runs the GROUP BY loop against a small, fully associative LRU cache. Each square is one 64-byte line of the table. Blue squares are in cache. Green flashes are hits and red flashes are misses. Its timing is a model: 1 ns per hit and 80 ns per miss, with no prefetcher, so it shows why the pattern matters rather than predicting real numbers. The real measurement comes from order.cpp: the same sums[id] += amount loop over 20M rows and 10M groups, run once with random ids and once with the ids sorted.

Structure

Groups

Row order

Cache

Speed

line not in cacheline in cachehitmiss

A toy model with a fully associative LRU cache and no prefetcher. It runs 4,000 rows. Modeled time assumes 1 ns per hit and 80 ns per miss.

Things to try:

512 groups with an 8 KB cache. The array is 4 KB and fits, so after the first pass nearly every access hits. The flat hash table for the same 512 groups needs 16 KB of slots plus control bytes, so it thrashes. The chained table does worse.
2048 groups, random order. Now nothing fits. Switch the order to sorted by id and the array's misses drop to about one per line, because eight consecutive ids share a line. The hash tables gain much less from sorting, because sorting by id does not sort by hash.
The 2 KB cache shows the same effect at smaller sizes.

Results

Measured (order.cpp, array[id], 20M rows, 10M groups):

Row order	ms	ns/row
random	51.0	2.55
sorted by id	14.4	0.72

What this tells us

Confirmed: the same array is 3.5× faster when reads follow memory order. The data structure is identical. Only the read pattern changed.
A hash table cannot use this trick directly. Its slot order is the hash order, and the hash is designed to have no relation to key order. That is why databases partition data before hashing it. A radix-partitioned hash join first splits both inputs into chunks whose hash tables fit in cache, then joins chunk by chunk (Balkesen et al. 2013).
An array wins twice over. Its small footprint means more of it stays in cache, and its layout follows key order, so ordered input becomes sequential reads.

Experiment 3: The cost of getting dense ids

Why this matters

array[id] only works when the keys are dense integers. Real keys are strings, UUIDs, or sparse 64-bit ids. Turning them into 0..G-1 needs a dictionary, and a dictionary is a hash table. Does that hash table cancel the benefit?

Hypothesis

Building the dictionary costs about as much as one hash-table aggregation, because it is the same work: hash each key, probe, compare. It pays off only when the encoded column is read more than once.

Method

groupby.cpp also times building a dictionary (unordered_map<string, u32>) and encoding all 20M rows into a u32 column.

Hash at the boundary, index everywhere after it. Columnar databases do this with dictionary-encoded columns.

Results

Groups	encode	string map	array	break-even
100	11.03	12.80	0.35	0.89
10K	17.34	19.32	0.34	0.91
1M	80.55	83.57	0.90	0.97
10M	161.12	165.28	2.59	0.99

All times are ns/row. Break-even is the number of queries after which encoding has paid for itself: encode / (string map − array).

What this tells us

Confirmed: encoding costs almost exactly one string-hash aggregation. It is the same loop, storing an id instead of adding to a sum.
It pays off from the second read of the column onward. Every later query, filter, join, or sort on the encoded column runs at array speed. The 4-byte ids are also 4× smaller than the 15-byte strings they replace.
This is the bet a columnar database makes: write once, read many times. Dictionary encoding (Abadi et al. 2006) and ClickHouse's LowCardinality type pay the hashing cost at insert time so that queries never pay it. For a one-off pass over data you will never read again, just hash it.

Experiment 4: Small maps and linear scans

Why this matters

Redis stores small hashes as a flat listpack and scans it linearly, switching to a real hash table only past hash-max-listpack-entries (Redis docs). A common claim is that a linear scan of a small array beats a hash lookup. If that holds, "prefer arrays" would extend to searching arrays too.

Hypothesis

A linear scan beats unordered_map up to roughly 32–64 entries, where the scan's cost overtakes the hash's fixed overhead.

Method

smalln.cpp does 20M random point lookups for n = 4 to 1024. It compares scanning a vector<pair<key, value>> with unordered_map::find, for both u32 and string keys.

Key type

Measured, ns per lookup. Both axes are log scale. Hover over the markers for exact values.

Results

n	u32 scan	u32 hash	string scan	string hash
4	5.42	5.08	9.88	9.90
8	6.54	7.49	13.74	15.15
16	7.88	1.89	19.22	11.56
64	14.42	2.83	57.85	13.20
256	40.76	0.91	156.18	13.92
1024	137.50	0.90	857.41	11.24

What this tells us

Refuted. The scan only ties or narrowly wins up to 8 entries. By 64 entries it is 5× slower for u32 keys and 4× slower for strings. With random queries the loop's exit branch is unpredictable, and a scan does n/2 comparisons on average.
Redis uses listpacks to save memory, not to make lookups faster. A 20-field hash as a listpack is one small allocation. As a hash table it is a table plus 20 nodes, each with pointers.
The "array" in the original claim means direct indexing, not searching. array[id] is fast because the key is the address. An array you have to search is a different data structure, and it loses to a hash table once n is more than a handful.

Where real systems already replace hashes with arrays

DuckDB uses a perfect hash aggregate when column statistics show a small integer range. It allocates 2^bits slots and indexes each group by value − min, with no hash function (aggregation blog, operator source). Since late 2024 it makes the same switch for joins, using the min/max it computes while building the join table (PR #14971).
ClickHouse aggregates UInt8/UInt16 keys with FixedHashMap, which is a lookup array with "no conflict chain … no key comparison" (source, hash tables in ClickHouse).
V8 stores JavaScript object properties in slot arrays described by hidden classes, and falls back to hash-based "dictionary mode" only when an object's shape keeps changing (Fast properties in V8).
CPython 3.6+ stores dict entries in a dense array with a small sparse index on top (Hettinger's 2012 proposal). The hash part is only a way to find a position in the array.
Game engines and compilers replace pointers and hash-map lookups with indices into arrays: generational handles (floooh), ECS component storage (Catherine West, RustConf 2018), and the Zig compiler's data-oriented rewrite (Andrew Kelley).

When to use which

Use an array when the keys are dense integers, or can be made dense:

Dictionary-encode strings at ingest, then use the integer ids everywhere after that.
Hand out handles or indices instead of pointers or string ids.
For a small or known key range, index by value − min.
For sets of integers, use a bitset, or a Roaring bitmap when the set is sparse.
For read-mostly lookups, sort once and binary-search. A sorted array, in Eytzinger layout if lookups dominate, beats std::set.
Sort or partition the input by key before the hot loop, so the reads become sequential.

Use a hash table when the keys are sparse or unbounded and you will read the data only once, or when inserts and lookups are interleaved with no point where you could encode. When you need one, choose a flat open-addressing table such as absl::flat_hash_map, Rust's HashMap, or Go 1.24+ maps. At 10M groups the flat table was 5.8× faster than the node-based std::unordered_map.

How to find opportunities: look for string- or UUID-keyed maps inside hot loops, maps whose keys are already sequential ids, and maps with fewer than about 64K distinct keys, since those keys fit in a u16 index.

Final Summary

Factor	Finding
Instruction cost, when everything fits in cache	Array is 6.5× faster than the best hash table, and 36× faster than string keys
Cache footprint	8 B per group for the array vs 27–61 B for hash tables. At 1M groups only the array fits in L2
Pointer chasing	Node-based `unordered_map` is 5.8× slower than a flat hash table at 10M groups
Read order	The same array is 3.5× faster with rows sorted by id
Cost of dense ids	Encoding costs about one hash aggregation. It pays off from the second query
Linear scan on small n	Wins only up to about 8 entries, then loses badly. "Array" means indexing, not searching

The claim holds, with one condition. A hash table converts a key into a location, and that conversion costs instructions, memory, and locality. Where the key can already be the location, as with dense ids, handles, or dictionary codes, that cost disappears. Where it cannot, a flat hash table is the best option, and the node-based std::unordered_map is the most expensive one tested here.

The Question

Setup

Background: what one lookup touches

Experiment 1: GROUP BY with four structures

Why this matters

Hypothesis

Method

Results

What this tells us

Experiment 2: Read patterns and the cache

Why this matters

Hypothesis

Method

Results

What this tells us

Experiment 3: The cost of getting dense ids

Why this matters

Hypothesis

Method

Results

What this tells us

Experiment 4: Small maps and linear scans

Why this matters

Hypothesis

Method

Results

What this tells us

Where real systems already replace hashes with arrays

When to use which

Final Summary

Further reading