AlgoScope

Hash Map

structurebeginnerTime O(1) average, O(n) worstSpace O(n + buckets)

A hash map is a row of buckets where the key itself says which bucket to use: hash the key, take the remainder, go there. The value is just luggage that travels with its key. Two keys can land in the same bucket, and with separate chaining the bucket simply holds a short list of entries, so a lookup hashes once and then compares keys along that list. Keep the number of entries close to the number of buckets and the lists stay short, which is why put, get and remove are O(1) on average.

01234

5 buckets, one per row, each able to chain entries left to right. A key's bucket is key mod 5. The value never affects where an entry goes: it just travels with its key. The load factor, entries divided by buckets, says how long the chains are on average.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.

  1. Key 12 with 5 buckets: which bucket?

    • 2
    • 3
    • 1

    Answer: 2. 12 mod 5 = 2. The value plays no part in the choice.

  2. Key 7 with 5 buckets: which bucket?

    • 2
    • 3
    • 1

    Answer: 2. 7 mod 5 = 2. The value plays no part in the choice.

  3. Key 22 with 5 buckets: which bucket?

    • 2
    • 3
    • 1

    Answer: 2. 22 mod 5 = 2. The value plays no part in the choice.

  4. Key 3 with 5 buckets: which bucket?

    • 3
    • 4
    • 2

    Answer: 3. 3 mod 5 = 3. The value plays no part in the choice.

  5. Key 17 with 5 buckets: which bucket?

    • 2
    • 3
    • 1

    Answer: 2. 17 mod 5 = 2. The value plays no part in the choice.

How it runs, step by step

  1. 5 buckets, one per row, each able to chain entries left to right. A key's bucket is key mod 5. The value never affects where an entry goes: it just travels with its key. The load factor, entries divided by buckets, says how long the chains are on average.

    Empty hash map with 5 buckets.

  2. put 12 5: hash the key. 12 mod 5 = 2, so bucket 2 is the only place this key can be. It is empty.

    put 12: bucket 2.

  3. The bucket is empty, so 12:5 becomes its first entry. Load 1/5.

    Key 12 appended to bucket 2.

  4. put 7 3: hash the key. 7 mod 5 = 2, so bucket 2 is the only place this key can be. It holds 1 entry.

    put 7: bucket 2.

  5. Compared against 1 key, none equal: a collision, 7 shares bucket 2 with them and is appended to the chain. Load 2/5.

    Key 7 appended to bucket 2.

  6. put 22 8: hash the key. 22 mod 5 = 2, so bucket 2 is the only place this key can be. It holds 2 entries.

    put 22: bucket 2.

  7. Compared against 2 keys, none equal: a collision, 22 shares bucket 2 with them and is appended to the chain. Load 3/5.

    Key 22 appended to bucket 2.

  8. put 3 1: hash the key. 3 mod 5 = 3, so bucket 3 is the only place this key can be. It is empty.

    put 3: bucket 3.

  9. The bucket is empty, so 3:1 becomes its first entry. Load 4/5.

    Key 3 appended to bucket 3.

  10. put 17 4: hash the key. 17 mod 5 = 2, so bucket 2 is the only place this key can be. It holds 3 entries.

    put 17: bucket 2.

  11. Compared against 3 keys, none equal: a collision, 17 shares bucket 2 with them and is appended to the chain. Load 5/5.

    Key 17 appended to bucket 2.

  12. 5 entries in 5 buckets, load 5/5, longest chain 4. With a good hash and the load kept near 1, chains stay short and put, get and remove all cost O(1) on average. Let the load grow and every operation degrades toward a scan of the chain.

    5 entries, longest chain 4.

Remember

  • The key is hashed to choose the bucket; the value never influences where the entry lives.
  • Colliding keys share a bucket and form a chain; a lookup compares keys along that chain only.
  • Load factor = entries / buckets. Near 1 the chains are short, so everything is O(1) on average.

Topics covered

Related

Where this is used

DatabasesHash join in a relational database

When PostgreSQL joins two tables and no useful index exists, it builds a hash map in memory from the smaller side, keyed by the join column, then scans the larger side once and probes that map for each row. Comparing every row against every other row is n times m; one hash and one bucket lookup per row turns the join into a single pass over each input. If the build side does not fit in work_mem, the planner splits both inputs into batches by hash value so that one batch's map fits at a time, which is the bucket idea applied again at the level of disk files.

CompilersSymbol tables in a compiler

A compiler meets the same identifier thousands of times and must answer "what does this name refer to here" at every occurrence. Clang interns each identifier into one hash table keyed by its spelling, so the text of a name is stored once and every later comparison is pointer equality instead of a string compare. Lookup then walks outward through the enclosing scopes, each with its own map from name to declaration, so leaving a block just drops the innermost map.

NetworkingConnection tracking in the Linux kernel

A machine forwarding a million packets a second has to decide, for every single packet, which existing connection it belongs to. The kernel hashes the packet's 5-tuple, protocol plus both addresses and ports, and looks the entry up in one hash table: nf_conntrack for NAT and firewall state, the established socket hash for TCP. With a list or a tree, per-packet cost would grow as connections accumulate; the hash keeps it flat, which is why the table size is a tuning knob rather than the algorithm being replaced.

Programming languagesDictionary mode objects in V8

V8 normally stores a JavaScript object's properties at fixed offsets described by a hidden class, so obj.x compiles down to a load from a known offset rather than a lookup. When an object is used as a bag of arbitrary keys, with properties added and deleted at runtime, that fixed shape stops paying off and V8 switches the object into dictionary mode, a genuine hash table keyed by property name. It is the trade in miniature: the hash map accepts any key at any time, and gives up the inline caching that a fixed layout allows.

Why it works this way

Why key % buckets, and what a power-of-two table throws away

The remainder is the cheapest way to fold an unbounded key into a bucket index, but it only looks at the low end of the number. With a power-of-two bucket count, key % size is exactly a mask over the lowest bits, so keys that differ only higher up - pointers, timestamps, ids that are all multiples of 16 - pile into a few buckets while the rest sit empty. Libraries fix this one of two ways: choose a prime bucket count, so no regular bit pattern lines up with the modulus, or keep powers of two and mix the high bits down first, which is what java.util.HashMap's h ^ (h >>> 16) does before masking.

A key that changes after it is inserted is lost

The bucket is chosen once, at insert time, from the key's hash. Mutate a field that the hash depends on and the entry stays in the bucket it was put in, while every later get hashes to a different bucket and reports the key missing - the entry is still in the table, unreachable, and remove will not find it either. This is why keys are immutable in practice: Python refuses to hash a list at all, and hashes a tuple only when every element inside it is itself hashable, and Java states the same rule as a contract, that equal keys must return equal hash codes and a key's hash must not change while it is in the map.

Iteration order is a property of the buckets, not of your inserts

Walking the table means walking bucket 0, then bucket 1, and so on, so the order you see reflects where the hashes landed, and it can change completely after a resize moves every entry. Code that passes because the first key out happened to be the one you wanted will break on a different input size. If you need an order, ask for it explicitly with something like Java's LinkedHashMap or a sorted list of keys. Python's dict is the exception that confuses people: since 3.7 it guarantees insertion order, because CPython keeps entries in a compact append-only array and the buckets store only indexes into it.

Colliding keys can be chosen on purpose

If an attacker knows your hash function, they can generate thousands of distinct keys that all land in one bucket and send them as form fields or JSON keys. Every insert then walks the whole chain, an O(1) map becomes O(n) per operation, and one small request burns a CPU core: this is hash flooding, and in 2011 the same attack hit PHP, Java, Ruby and Python web stacks. The two standard defences are a randomly seeded keyed hash, so an attacker cannot predict buckets, which is why CPython adopted SipHash in PEP 456 and Rust's default hasher does the same, and bounding the damage instead, which is why java.util.HashMap converts a bucket into a red-black tree once that bucket holds eight entries in a table of at least 64 buckets, so the worst case per operation becomes O(log n) instead of O(n).

Read more

Next up