Hash maps in five standard libraries

Every mainstream language ships a hash map, and the five covered here, Python’s dict and set, Java’s HashMap and HashSet, C++’s unordered_map and unordered_set, Go’s built-in map and JavaScript’s Map and Set, all give insert, find and delete in O(1) time on average. They differ in four places, and those four cause most of the bugs people write with them: what reading a missing key does, the order in which a loop visits the keys, what may be a key, and how two keys are judged equal. This lesson runs one counting task in two languages, puts the five libraries side by side on those four questions, and names the trap each library is known for.

The same count in two languages

Counting how many roll numbers belong to each branch, given by the first three characters, takes one map from branch code to count and one pass:

"""Count roll numbers by branch code (the first three characters) and print the branches in sorted order."""
rolls = ["ECE21004", "CSE21001", "MEC21010", "CSE21007", "ECE21002", "CSE21013", "CIV21003"]

counts = {}
for roll in rolls:
    branch = roll[:3]
    counts[branch] = counts.get(branch, 0) + 1  # get() returns 0 for a branch not seen yet

print("as inserted:", counts)
for branch in sorted(counts):
    print(f"{branch}: {counts[branch]}")

as inserted: {'ECE': 2, 'CSE': 3, 'MEC': 1, 'CIV': 1}
CIV: 1
CSE: 3
ECE: 2
MEC: 1

// Count roll numbers by branch code (the first three characters) and print the branches in sorted order.
const rolls = ['ECE21004', 'CSE21001', 'MEC21010', 'CSE21007', 'ECE21002', 'CSE21013', 'CIV21003'];

const counts = new Map();
for (const roll of rolls) {
  const branch = roll.slice(0, 3);
  counts.set(branch, (counts.get(branch) ?? 0) + 1); // get() returns undefined for a branch not seen yet
}

console.log('as inserted:', [...counts.keys()].join(' '));
for (const branch of [...counts.keys()].sort()) console.log(`${branch}: ${counts.get(branch)}`);

as inserted: ECE CSE MEC CIV
CIV: 1
CSE: 3
ECE: 2
MEC: 1

Both programs read a missing branch as zero in one expression, counts.get(branch, 0) in Python and counts.get(branch) ?? 0 in JavaScript, because a plain read of a missing key gives no number in either language. Both maps list the branches in the order they first appeared, ECE before CSE, so both sort the keys before printing.

Five libraries side by side

Read the first row before writing a lookup in an unfamiliar language: the same expression, m[k], raises an error in Python, quietly inserts in C++, returns 0 in Go and is a different operation altogether on a JavaScript Map. The third row is why the counting programs above sort before they print.

Sets in the five libraries

A set is the same table without values, and each library has one. Python has set and the unchangeable frozenset, which can itself be a key. Java’s HashSet is documented as backed by a HashMap, so it inherits that map’s costs and its lack of order. C++ has unordered_set. JavaScript has Set, with the same insertion order and key comparison as Map. Go has no set type; the usual stand-in is a map[string]struct{}, whose empty struct values take no space at all, or a map[string]bool when reading a missing key as false is convenient.

The trap each library is known for

• Python: a defaultdict creates an entry for every missing key it is asked about, even in a loop that only reads.
• Java: comparing two Integer values with == compares objects, so it works for small numbers and then fails.
• C++: reading with operator[] inserts the key when it is missing, so a loop that only reads can grow the map.
• Go: a loop over a map visits the keys in a different order each time, so output needs sorted keys.
• JavaScript: a plain object turns every key into a string, so 1 and "1" become the same key.

Each of these compiles, runs and passes a quick test, which is what makes it dangerous: the map still works, but reports a size that is too large, a comparison that is wrong only for larger numbers, or an order that changes between runs.

Choosing keys that hash and compare correctly

A key must keep its hash for as long as it is stored, so use values that cannot change: strings, numbers and tuples in Python, records or strings in Java, structs of comparable fields in Go. Build composite keys from their parts rather than by gluing strings together, because “AB” + “C” and “A” + “BC” give the same text: a tuple (city, day) in Python, a record in Java, a struct in Go. In C++, std::pair has no standard std::hash, so a pair key needs a hash function of your own. In JavaScript, a Map compares object keys by identity, so two objects with the same contents are two different keys; turn such a key into a string or a number first.

Check yourself

Each library's trap, reproduced and fixed Pro: opens with a Pro, Premium or Ultimate pass

Memory, presizing and ordered alternatives, measured Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• All five libraries give O(1) average insert, find and delete, but they differ on missing keys, iteration order, key requirements and equality.
• A missing key raises in Python, returns null in Java, inserts in C++ with [], returns the zero value in Go and undefined from a JavaScript Map.
• Only Python’s dict and JavaScript’s Map promise insertion order; sort the keys whenever output order matters.
• Keys must not change while stored; build composite keys from their parts, not by gluing strings.