Why is my hash map slow?

A slow hash map is nearly always slow for one of four reasons: the hash function is poor, so keys pile into a few buckets; the load factor has been allowed to climb, so every lookup walks a chain; the keys themselves are expensive to hash or compare; or the table is so large that every access is a cache miss. The promised O(1) was never a promise about nanoseconds, and each of these breaks a different assumption behind it.

I want to start with the assumption, because the question "why is my hash map slow" usually comes from someone who was told hash maps are constant time and now feels lied to. They were not lied to, exactly. They were given an average-case bound that holds under three conditions: the hash spreads keys evenly, the table is resized before it fills, and the constant hidden inside O(1) is small relative to whatever else the program does. Violate any one and the map is still "constant time" in the textbook sense while being the slowest thing in your profile.

Is the hash function spreading keys evenly?

Check this first, because it is the failure people least expect and it produces the worst slowdowns. A hash map achieves constant time by making each bucket hold about one key. If many keys share a bucket, a lookup degrades to scanning that bucket, and with a bad enough function the whole map becomes a linked list with extra steps: O(n) per operation, which is the complexity you were trying to escape.

Bad hashing hides in plain sight. A custom hash that combines fields with addition sends (a, b) and (b, a) to the same bucket. A hash of a string that only looks at the first few characters collapses every key with a common prefix, and URLs, file paths, and identifiers all have common prefixes. Integer keys that are all multiples of some power of two, used with a table whose size is also a power of two and a hash that is the identity, land in a fraction of the buckets. The test is cheap: count keys per bucket, or in a language that exposes it, look at the collision statistics. If the maximum chain length is far above the average, the function is the problem, and no amount of resizing will help. The load factor and collisions deep-dive works through what a good distribution looks like numerically.

Has the load factor been allowed to climb?

The load factor is the number of stored keys divided by the number of buckets. Standard libraries resize when it crosses a threshold, typically around 0.75 for chaining and lower for open addressing, and that resize is what keeps chains short. Two situations defeat it. The first is a map constructed with a fixed capacity and resizing disabled or capped, a choice people make to avoid the pause of rehashing and then forget about. The second is open addressing with many deletions: tombstones left by removed keys still count as occupied for probing purposes, so a map that has churned through millions of insertions and deletions can have a low nominal size and a very long average probe sequence.

Reasoning about the cost makes the threshold concrete. With chaining and load factor alpha, an unsuccessful lookup examines about alpha keys on average, so alpha of 0.75 means under one comparison beyond the bucket access. With linear probing, the expected probes for an unsuccessful search grow roughly like one over (1 minus alpha) squared: at alpha 0.5 that is about 4 probes, at 0.9 about 100. A map that drifted from 0.5 to 0.9 without resizing got twenty-five times slower for lookups of missing keys, and it did so silently.

Are the keys expensive to hash or compare?

O(1) counts operations on keys, not the cost of each operation. Hashing a 2 KB string is a 2 KB scan, every time, unless the hash is cached. Comparing two long strings that share a prefix walks the prefix before finding the difference. A key that is a nested object with a hash defined over all its fields costs a traversal per lookup. In a hot loop, the map may be doing everything right and the keys are simply heavy.

The fix is to hash something smaller. Intern strings so that keys become pointers or integers; precompute and store a key's hash alongside it; or hash a stable identifier rather than the full object. Languages differ on what they do for you: some cache string hashes after the first computation, some do not, and knowing which you are in is worth a profiler run. The hash maps module covers the trade-off between hash quality and hash cost, which pulls in opposite directions.

Is the table too big for the cache?

This one is invisible to complexity analysis and dominant in practice. A hash lookup on a large table is a pointer chase to a random location in memory. When the table fits in L2 cache, that chase costs a few nanoseconds; when it spans hundreds of megabytes, it costs a main-memory access, on the order of 100 nanoseconds, and with chaining there is a second chase to the node. A map with ten million entries can therefore be dozens of times slower per operation than one with ten thousand, at the same O(1), for no algorithmic reason at all.

Two remedies. If the access pattern has locality, sort the keys and iterate in order, or batch lookups by bucket, so that consecutive accesses hit nearby memory. If it does not, consider whether a hash map is the right structure: a sorted array with binary search does log n comparisons but touches memory in a predictable pattern, and for read-mostly data it frequently wins in wall-clock time. The arrays versus lists essay makes the same argument for a different structure, and the reason is identical: the memory hierarchy, not the operation count.

How do you tell which problem you have?

Each cause leaves a different fingerprint, and a few minutes of measurement separates them:

Symptom	Likely cause	Quick check
Some lookups fast, some very slow	Uneven hash, long chains	Histogram of bucket sizes
Slows steadily as the map grows or churns	Load factor or tombstones	Print size, capacity, and the resize policy
Slow even when tiny	Expensive hash or equality	Profile the hash and compare functions
Fast in tests, slow at production scale	Cache misses	Compare per-op time at 10k versus 10M entries

Work down the table in order, because the first two causes are bugs with clean fixes and the last two are trade-offs you may have to design around. And measure before touching anything. I have watched a team replace a hash map with a hand-rolled trie to fix a slowdown that turned out to be a string hash recomputed on every call; the trie was slower.

Frequently asked questions

Is a hash map always O(1)?

On average, with a good hash function and a bounded load factor, yes. The worst case is O(n) when many keys collide, and some libraries fall back to balanced trees inside a bucket to cap that at O(log n). Neither bound says anything about cache behaviour, which is what usually dominates at scale.

Should I use a hash map or a sorted array?

Hash map for unpredictable lookups with frequent inserts. Sorted array for read-mostly data, small keys, or when memory locality matters more than the log n comparisons. At a few hundred elements, the sorted array is often faster in practice even though its complexity is worse.

What load factor should I use?

Keep the library default unless you have measured a reason to change it. Chaining tolerates 0.75 to 1.0 comfortably; open addressing wants 0.5 to 0.7. Lowering it trades memory for speed, and the gain flattens quickly below 0.5.

For the mechanics behind the average-case bound, and the numbers that make "bounded load factor" concrete, continue with load factor and collisions.