What exactly is a hashmap?
A hashmap stores pairs of keys and values. A key identifies an entry, and its value is the information stored there. For example, "apple" → 3 can record that the word apple appears three times in a document: apple is the key, and 3 is its value.
Why is that useful? Once the counts are stored, we can ask for any word’s count without scanning the document again: the hashmap returns the count saved under that key, or reports that the word has no entry.
Python calls it a dictionary, and C++ provides unordered_map; other languages say Map or HashMap. The syntax differs, but each stores and retrieves information by key.
A map is the set of operations on keys and values. A hash table is one way to implement those operations; other implementations use trees, which keep the keys sorted. This lesson builds the hash-table implementation.
Operations on keys and values
| Operation | Example | Result |
|---|---|---|
| Look up a key | Read apple | 3 |
| Test membership | Does plum exist? | No |
| Insert a new key | Store plum → 2 | Three entries |
| Update an existing key | Store apple → 4 | Two entries; apple now has value 4 |
| Remove a key | Remove apple | One entry; only pear → 1 remains |
Each key has one entry. Storing "apple" → 4 replaces the earlier count of 3. Different keys can have equal values: "apple" → 3 and "pear" → 3 are separate entries. A membership test looks only at keys, never at values.
What about a count of zero? Removing apple makes its key absent. Setting its value to zero instead leaves the entry "apple" → 0, and a membership test still finds it. An algorithm may need to tell those two situations apart.
Arrays and maps
Do we need a hashmap when we already have arrays? An array gives constant-time access when we know an element’s position: it goes straight to nums[i], while a hashmap first hashes the key and then locates its entry. An array also keeps its slots next to one another in memory, which makes scanning fast, and a hash table needs extra space for its keys and for unused slots.
So the choice depends on the range of possible keys. To count integers from 0 to 100, an array of 101 counts works well. With a few distinct numbers up to , though, an array with a slot for every possible key would waste almost all of its space. A map stores entries only for the keys we actually use, and its keys can be words as well as numbers.
| Structure | Keys | Cost to find a key | Iteration order |
|---|---|---|---|
| Array: Python list, C++ vector | Positions 0 to n − 1 | O(1) | By position |
| Hash map: Python dict, C++ unordered_map | Any hashable value | O(1) expected, O(n) worst | Python: insertion order; C++: unspecified |
| Tree map: C++ map | Any comparable value | O(log n) | Sorted by key |
When is a set enough?
Sometimes we need no value at all. A set stores only distinct keys, so it can answer whether a word appeared. A map also stores information about each word, so it can answer how many times that word appeared.
You get an array of integers nums. Return true if some value appears at least twice, and false if every value is distinct.
Constraints
- , where is the length of
nums
Sample 1 · Input
nums = [1,2,3,1]
Output
true
Sample 2 · Input
nums = [1,2,3,4]
Output
false
Sample 3 · Input
nums = [1,1,1,3,3,4,3,2,4,2]
Output
true
In the first sample, 1 appears at positions 0 and 3. Only the presence of each value matters here, so a set is enough. We scan the array and ask whether the current value is already in the set. If it is, an earlier position held the same value and we can stop. If not, we add it and move on:
def contains_duplicate(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
print(contains_duplicate([1, 2, 3, 1]))
print(contains_duplicate([1, 2, 3, 4]))Prints True, then False.
Comparing every value with every later value also answers the question, but at the limit that takes
The set does one membership test and at most one insertion per number, operations at most, and the next part explains why each takes expected constant time.
How does hashing work?
So how does a hash map find a key without searching every stored entry? It uses a hash function that computes an integer from the key, and then reduces that integer to one of the buckets of an internal array:
Let’s use a small table. It has buckets, numbered 0 through 7, and an integer key is its own hash, so key goes into bucket k % 8. Key 12 goes to bucket 4, and key 7 to bucket 7. The stored value plays no part in choosing the bucket.
What if two keys share a bucket?
What happens when we store keys 10, 18 and 26? Each leaves remainder 2 when divided by 8, so all three belong in bucket 2. When different keys map to the same bucket, we call it a collision. The table below holds 10 → 1, 18 → 2 and 26 → 3, and each bucket keeps a list of entries, a way of handling collisions called chaining.
18 mod 8 = 2Bucket 210 → 110 ≠ 1818 → 218 = 18 ✓26 → 3Not checkedLet’s read key 18. We compute 18 % 8 = 2 and inspect that bucket. The first entry has key 10, which is not 18, so we move on. The next entry has key 18, so we return its value, 2. A lookup for 34, which also lands in bucket 2, compares against all three entries and reports that the key is absent. Equal bucket numbers do not make the keys equal.
Removing key 18 works the same way: we find its entry in bucket 2 and take it out of the list, and keys 10 and 26 stay. Inserting key 18 again would then create a new entry, while updating a key that exists changes its value without adding an entry.
Is key % 8 a good hash function? It puts every multiple of eight into bucket 0, so on that input every search scans one long list. Real hash tables use a hash function that spreads the keys across the buckets, and the standard library supplies one for integers and strings. Near the end of this lesson, anti-hash tests use this same weakness against C++’s unordered_map.
Recall If 18 and 26 share a bucket, does updating 18 replace 26?
Keys 18 and 26 remain separate entries even though they share a bucket. A lookup compares keys to distinguish them, and updating the value under key 18 leaves the entry for key 26 unchanged.
Deeper read: open addressing
Chaining keeps a list at each bucket. Open addressing stores the entries directly in the table’s slots instead. In one version, linear probing, a key that finds its slot taken tries the next slot, then the one after, wrapping around at the end of the array.
Let’s place our keys in eight slots. Key 10 starts at slot 2, which is free. Key 18 also starts at slot 2, finds it taken, and goes to slot 3. A lookup for 18 follows the same path: it compares against key 10 in slot 2, then finds key 18 in slot 3. The table keeps some slots unused, and an unsuccessful lookup ends when it reaches a slot that has held no entry since the last rebuild.
Deletion has to preserve that path. If removing key 10 made slot 2 look unused, a later lookup for 18 would stop there and miss slot 3. One solution leaves a deleted marker, called a tombstone, which tells lookup to keep going. Other implementations repair the path by moving entries.
Load factor and resizing
Even with well-spread keys, the chains grow longer if the number of buckets stays fixed while entries keep arriving. How do we measure that crowding? The load factor does. With stored entries in buckets, it is
Eight entries in our eight buckets give . With 32 entries in the same eight buckets, , so an average chain holds four entries.
What does crowding cost? With chaining, a lookup takes expected time when the hash spreads the keys evenly: the 1 counts computing the bucket, and is the average length of the chain we scan. Keeping the load factor below a fixed limit keeps the expected cost constant as the collection grows. The limit depends on the implementation, and a chaining table can hold more entries than it has buckets.
So how does a table keep its load factor down? When it passes the limit, it allocates more buckets and places every entry again, which is called rehashing. Let’s double our table from eight buckets to sixteen and follow the three keys in bucket 2.
| Key | 8 buckets: key % 8 | 16 buckets: key % 16 |
|---|---|---|
| 10 | 2 | 10 |
| 18 | 2 | 2 |
| 26 | 2 | 10 |
Key 18 stays in bucket 2, but keys 10 and 26 move to bucket 10. If we copied each old bucket to the same position in the larger array, those two keys would sit in bucket 2, where lookup no longer searches for them. That is why every entry is placed again.
Why resizing stays cheap
Does rehashing make insertion slow? A rebuild moves every entry, so the one insertion that triggers it costs . Rebuilds are rare, though. Suppose a table doubles whenever its load factor reaches 1. Then successive rebuilds move 8, 16, 32 and 64 entries. Each is twice the one before, so their sum is less than twice the largest:
The same holds at any size. By the time a table holds entries, all of its rebuilds together have moved fewer than entries, so fewer than two moves per insertion. That bound is what amortized insertion means. It is an average over a whole sequence of insertions, a different promise from the expected cost of one lookup.
Count occurrences with a frequency map
Now that we can find an entry by key, we can update it as we read new input. A frequency map uses each input number as a key and the number of times it occurs as the value. Let’s read [7, 2, 7, 7, 2]. Each 7 updates the same entry, first to 1, then 2, then 3, and each 2 updates another. At the end the map holds 7 → 3 and 2 → 2.
The loop starts with an empty map. For each number, it reads the current count, using zero when the number has not appeared, and stores that count plus one. Only the current number’s count changes, so after each step every count is correct for the numbers read so far.
def frequencies(nums):
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
return count
print(frequencies([7, 2, 7, 7, 2]))Prints {7: 3, 2: 2}.
Python details
{} creates a dictionary. get(x, 0) returns the stored count or zero when the key is absent. Dictionary keys must be hashable: integers and strings qualify, lists do not, because a list can change after it is stored.
Choose a key that identifies a group
A map’s value need not be a count; it can hold several items. Suppose we want to group words by their first letter. We use that letter as the key and a list of words as the value, so reading ["apple", "pear", "apricot"] builds "a" → ["apple", "apricot"] and "p" → ["pear"].
If we want to count each complete word instead, the complete word becomes the key and its count the value, and apple and apricot get separate counts even though they share a first letter. The key is whatever makes two items belong together, and the value is the information we need about that group.
Store earlier positions to look up a complement
So far, our maps have stored how often each number appeared. What if we store where it appeared instead? Then a scan can recover earlier positions, which is what the next problem needs.
You get an array of integers nums and an integer target. Return the positions of two numbers that add up to target. You may not use the same position twice, and the answer may list the two positions in either order.
Every test has exactly one answer.
Constraints
- , where is the length of
nums
Sample 1 · Input
nums = [2,7,11,15], target = 9
Output
[0,1]
Sample 2 · Input
nums = [3,2,4], target = 6
Output
[1,2]
Sample 3 · Input
nums = [3,3], target = 6
Output
[0,1]
In the first sample, , so the answer is positions 0 and 1. Our version also returns [] when no pair exists, so the same function handles inputs without one.
Our first idea might be to try every pair. Will it be fast enough? At the limit , the number of pairs of positions is
On our machine that took about 0.01 seconds in C++ and 0.8 seconds in Python. It passes, but the problem’s follow-up asks for less than , and numbers would take a hundred times as long.
So what should we do? Let’s look at one value . Its partner must satisfy , so the partner has exactly one possible value:
Instead of searching for a partner, we only have to ask whether one exact key has been seen. We keep a map from each earlier number to its earliest position. Before storing the current number, we look up its partner. If the partner is in the map, its stored position and the current position form the answer.
Worked example
Trace the scan
Each step shows the current position, the partner it needs and the map of earlier positions. In Partner comes later, 9 and 2 find no partner. Then 7 needs 2, which is stored at position 1, so the answer is [1, 2]. Equal values and No pair show the two cases this preset does not.
Store values from earlier positions. Looking up the complement before inserting prevents reusing the same element.
Change the example input
Current result: [1,2]
The returned positions refer to the original array; the map’s keys are input values.
Look up the partner before storing the current value
The trace turns into a loop with one partner lookup before each insertion. Each version keeps the first position stored for a number and returns the first pair it finds as the right position moves from left to right.
def two_sum(nums, target):
first = {}
for i, x in enumerate(nums):
need = target - x
if need in first:
return [first[need], i]
if x not in first:
first[x] = i
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))
print(two_sum([1, 2, 4], 10))Prints [0, 1], [0, 1] and [].
Python details
need in first tests whether a key exists. The second membership test keeps the earliest stored position for x. Python integers compute the complement without overflow.
Why does the order matter? Take [4] with target 8. If we inserted first, the lookup would find the current position and wrongly return [0, 0]. The lookup must happen before the insertion. With [4, 4], the correct order stores the first 4, and the lookup at position 1 finds it and returns [0, 1].
The map contains every earlier value
Before processing position i, the map contains exactly the distinct values at positions before i, each with its earliest position.
Why does the statement hold? At the start, the earlier prefix and the map are both empty. After an unsuccessful lookup, we insert the current value if it is absent, so the statement holds again at the next position.
When a lookup succeeds, the stored position is earlier than i, so the two positions differ. The retrieved key equals target - nums[i], so the values at those positions add up to the target.
Could the scan miss a pair? Take any valid positions . If the scan has not returned before reaching , the value at is in the map by then. The partner that position needs equals that value, so the lookup succeeds; keeping only the earliest occurrence still supplies a valid earlier position. So if the scan finishes without a match, no valid pair exists.
Recall Choose what to store under each key
If Two Sum asked only whether a pair exists, a set of earlier values would be enough. Returning positions needs the value the map stores. An occurrence count would tell us how many partners appeared, but it would lose their positions.
Anti-hash tests against unordered_map
Every expected bound so far rests on one assumption: the keys spread across the buckets. What if someone who knows the hash function chooses keys that break it? On Codeforces, other contestants can read a submitted solution and send it a test of their own, called a hack, and one test can slow many solutions at once, because they share the same standard library.
GCC’s standard library, libstdc++, which the GNU G++ compilers on Codeforces use, makes such a test easy to build. Its std::hash returns an integer key unchanged, the bucket is that value modulo the bucket count, and the bucket counts come from a fixed list of primes. When we printed bucket_count() while inserting 200,000 keys with GCC 15, the table passed through 85,229, then 172,933, then 351,061 buckets.
Now let’s choose keys that are all multiples of 172,933. Each leaves remainder 0, so while the table has 172,933 buckets, all of them share bucket 0. That stage lasts from the 85,230th insertion to the 172,933rd, and each insertion compares the new key with every key already in the bucket. How many comparisons is that?
We inserted the 200,000 multiples through in shuffled order on an Apple M5 Pro. It took 60 seconds in one run and 94 in another, against 0.005 seconds for the keys 1 through 200,000. The largest key is about , so the test fits any problem that allows 64-bit values.
Randomize the hash with splitmix64
So what can we do? A hacker writes the test before our program runs. If the hash depends on a seed chosen when the program starts, the hacker cannot tell which keys will share a bucket. Is adding the seed to the key enough? For every multiple of 172,933, has the same value, so those keys would still collide. The hash has to scramble the bits after adding the seed, as splitmix64 does, so that keys with a simple pattern land far apart.
MASK = (1 << 64) - 1
SEED = random.getrandbits(64)
def splitmix64(x):
x = (x + 0x9e3779b97f4a7c15) & MASK
x = ((x ^ (x >> 30)) * 0xbf58476d1ce4e5b9) & MASK
x = ((x ^ (x >> 27)) * 0x94d049bb133111eb) & MASK
return x ^ (x >> 31)
def mixed_key(x):
return splitmix64((x + SEED) & MASK)
count = {}
for x in [172933, 345866, 172933]:
key = mixed_key(x)
count[key] = count.get(key, 0) + 1
print(len(count), count[mixed_key(172933)])Prints 2 2: two distinct keys, and 172,933 counted twice. Equal inputs give equal mixed keys, and different 64-bit integers give different ones, so the counts stay correct.
Python details
Python integers have no fixed width, so each step keeps the low 64 bits with & MASK; C++’s uint64_t arithmetic does that by itself. The dict holds the mixed keys, so a program that prints the original values has to store each one next to its count.
str(x) as the key also defeats the attack, because string hashes are randomized at startup, at the cost of a conversion per key.
On the attack keys, no chain held more than 7 keys. gp_hash_table from GCC’s policy-based data structures, covered in the reading list, accepts the same struct as its hash.
Is Python safe? It randomizes the hash of str and bytes keys each time the interpreter starts, but an integer hashes to the same value in every run: hash(12345) is 12345, and larger values are reduced modulo on 64-bit builds. An attacker can predict where integer keys land in a dict or set too.
Deeper read: what splitmix64 does to the bits
splitmix64 adds a constant, then twice XORs the value with a shifted copy of itself and multiplies by a large odd constant, and finishes with one more XOR and shift. Flipping one input bit changes 32 of the 64 output bits on average, measured over 1,280,000 flips.
Every step can be undone: adding a constant, XOR with a right-shifted copy, and multiplying by an odd number modulo are all invertible. So two different keys never receive the same 64-bit hash, and collisions come only from reducing it modulo the bucket count.
The function is the mixing step of the SplitMix64 generator, as published in Sebastiano Vigna’s public-domain splitmix64.c; the constants come from that code.
When map or a sorted vector is simpler
There are two simpler fixes. map keeps its keys in a balanced binary search tree (a red-black tree in libstdc++), so each lookup and insertion takes time on every input. A red-black tree with keys has height at most , and for 200,000 keys that is
so every key sits at most 35 levels deep. There is no hash to write, and iteration visits the keys in sorted order.
When all the keys are known before any lookup, a sorted vector is simpler still. We sort the values once and then find a key with lower_bound or binary_search in , or replace each value with its index among the sorted distinct values and count with a plain array.
| Structure | Worst case per operation | Measured time |
|---|---|---|
| unordered_map, default hash | O(n) | 60 s and 94 s in two runs |
| unordered_map with SplitMixHash | O(n), but a hacker cannot target it | 0.010 s |
| map | O(log n) | 0.027 s |
| Sorted vector, then binary search for each key | O(log n) per search | 0.022 s, including the sort |
Recall Does calling reserve(n) protect a default unordered_map?
No. reserve(200000) sets the bucket count by a fixed rule; with GCC 15 it is 202,409. A hacker who reads the code can compute that number and send multiples of 202,409. In our run all 200,000 such keys shared one bucket and the table never resized, so the collisions lasted for all 200,000 insertions instead of one stage.
Expected lookup time and amortized insertion time
- One lookup
O(1) expected - With well-spread hashes and a bounded load factor, a lookup checks a bounded expected number of entries. If all keys collide, it checks .
- One insertion
O(1) expected amortized - A rebuild of entries takes , but doubling keeps all rebuilds below two moves per insertion.
- Frequency counting or Two Sum
O(n) expected time, O(n) extra space - A bounded number of map operations per item, and at most distinct keys. Collision-heavy input raises the time to .
Both bounds treat hashing and comparing an integer key as constant-time; a string key adds the time to read its characters.
Common hashmap mistakes
Treating a stored position of 0 as missing:
if first.get(need):in Python,if (first[need])in C++.- Where it breaks
- For
[2, 7]and target 9, the entry2 → 0reads as false and the function returns[]instead of[0, 1]. In C++,first[need]also inserts each missing partner with value 0, so the run ends with a stray7 → 0although 7 sits at position 1. - The fix
- Test the key itself:
need in firstin Python,first.count(need)or C++20’sfirst.contains(need)in C++.
Setting a count to 0 when an item leaves, instead of removing its key.
- Where it breaks
- After counting
[1, 2]and removing the 1, the map is{1: 0, 2: 1}, solen(count)reports 2 distinct values while only one remains. - The fix
- Delete the key when its count reaches 0:
del count[x]in Python,count.erase(x)in C++.
Using a list as a dictionary key or set element in Python.
- Where it breaks
seen.add([1, 2])raisesTypeError(unhashable type:list), because a list can change after it is stored.- The fix
- Store a tuple, which cannot change:
seen.add((1, 2)).
Key terms
| Term | Meaning |
|---|---|
| map | Key and value pairs, one entry per key. |
| set | Distinct keys with no values. |
| hash function | Turns a key into an integer, which is reduced to a bucket number. |
| collision | Two different keys in the same bucket. |
| chaining | A list of entries in each bucket. |
| load factor | Stored entries divided by buckets, . |
| rehashing | Placing every entry again in a larger bucket array. |
| frequency map | A map from each item to its number of occurrences. |
| anti-hash test | Input built so that many keys collide under a known hash. |
Further reading
- Codeforces blog by nealBlowing up unordered_map, and how to stop getting hacked on it(opens in a new tab)
Builds the anti-hash test against GCC’s
unordered_mapand gives the splitmix64 fix used above. - Codeforces blogC++ STL: Order of magnitude faster hash tables with Policy Based Data Structures(opens in a new tab)
Benchmarks
gp_hash_table, GCC’s open-addressing table, againstunordered_map. Give it a randomized hash as well. - USACO Guide, Gold(Optional) Hashmaps(opens in a new tab)
Anti-hash tests, custom hashes in C++ and Java,
gp_hash_table, and 3SUM solved with a hash map. - MIT 6.006 lecture notes, Spring 2020Lecture 4: Hashing(opens in a new tab)
Shows why search by comparisons needs time, builds hashing from direct-access arrays and argues for choosing the hash function at random.
- OI Wiki, in Chinese哈希表(opens in a new tab)
Chaining and open addressing, each with a complete implementation, followed by example problems.
- cp-algorithmsString Hashing(opens in a new tab)
Turns strings into numbers with a polynomial hash and estimates how likely two different strings are to collide.
- Crosby and Wallach, USENIX Security 2003Denial of Service via Algorithmic Complexity Attacks(opens in a new tab)
Hash flooding outside contests: the authors slowed Perl, the Squid web proxy and the Bro intrusion detection system by sending them keys that collide.