What is a hash map?

Keys, values, and the problem a hash map solves

Suppose you know a student’s ID and want their name. In a list of ID–name pairs, you might check every pair until the ID matches. A hash map organizes the pairs so you can usually find the right place with only a small amount of work. It is also called a hash table or dictionary. Python calls it dict.

In 10 → "Maya", 10 is the key and "Maya" is the value. The key identifies the entry; the value is the information attached to it. A key is not an array index. Key 18 does not mean “the nineteenth position.” The table calculates a storage location from the key.

A map has one current value per key. Assigning a new value to key 18 changes that entry. Different keys can have the same value. The basic operations are insert, find, update, check whether a key exists, and delete. The short Python example below shows these operations before we inspect the storage.

students = {}                   # An empty dictionary.
students[10] = "Maya"            # Insert key 10 and its value.
students[18] = "Ravi"            # Insert a different key.
print(students[18])              # Ravi: find the value for key 18.
print(18 in students)            # True: check whether key 18 exists.
students[18] = "Ravi Kumar"      # Update; still only two keys.
del students[10]                # Delete the pair for key 10.
print(students.get(10, "Missing"))  # Missing: a safe absent-key lookup.

How does it work?

1. Turn the key into a number.

   A hash function calculates a number from a key. For this small integer-key teaching model, use the key itself as the hash number. Real hash functions can also process strings and other supported key types.

2. Turn that number into a bucket index.

   A bucket is a storage position in the table. We have eight buckets, numbered 0 to 7. Use hash number % 8 to pick one. The % symbol means remainder after division: 10 divided by 8 leaves remainder 2, so key 10 belongs in bucket 2.

3. Store the complete key–value pair.

   Store both 10 and "Maya" in bucket 2. Keeping the key matters because another key can choose the same bucket. Our model keeps a list of pairs in each bucket; this is called separate chaining.

4. To find a value, repeat the calculation and compare keys.

   For key 18, calculate 18 % 8 = 2. Search only bucket 2. Compare the stored keys with 18; return the value only when a key matches. If no key matches, the requested entry is missing.

Work through an example

Follow the visual using exactly two pairs: 10 → "Maya" and 18 → "Ravi". Key 10 uses bucket 2 because 10 % 8 = 2. Key 18 also uses bucket 2 because 18 % 8 = 2. Two different keys choosing the same bucket is a collision. Keep both pairs; do not replace Maya with Ravi.

To find student 18, go to bucket 2. First compare 10 with 18: they differ. Then compare 18 with 18: they match, so return "Ravi". To update student 18 to "Ravi Kumar", replace only the matching pair’s value. To delete student 10, remove only its pair. Student 18 must remain available.

The illustration is a teaching model, not a drawing of Python’s exact dictionary implementation. Python performs hashing, collision handling, and resizing for you. You use dict’s public operations, such as students[18], rather than calculating its internal buckets yourself.

Time and space complexity

Let n be the number of stored key–value pairs and m the number of buckets. O(1), called constant time, means the expected amount of lookup work stays roughly independent of the number of stored pairs. It does not mean exactly one instruction. This bound assumes hashes spread keys reasonably well, the table grows to keep buckets from becoming crowded, and hashing and comparing a key take bounded work.

If all n keys land in one bucket, finding the last key can require n comparisons: O(n), called linear time. An insertion that triggers a resize can also take O(n). “Amortized O(1) insertion” means that occasional expensive growth is spread across many insertions; it does not promise that every insertion is constant time.

Space: the whole table stores n pairs and m buckets, so the chained model uses O(n + m) space, excluding the contents of any large key or value objects. With m kept proportional to n, this is O(n). A lookup itself needs O(1) extra space: it does not copy the table. Hashing a new string of k characters can take O(k); include this cost when keys are long.

Why it works

Insertion and lookup use the same bucket rule, and every pair keeps its original key. This makes it possible to distinguish key 10 from key 18 even though they share a bucket. An update finds the existing key before changing its value, so it does not create a second copy of that key.

Common mistakes

• A key is what you search with; the bucket index is a location calculated from that key. They are different things.
• A collision does not mean the keys are equal. Compare the actual keys before returning or replacing a value.
• A hash map is fast for exact-key lookup. It does not automatically keep keys sorted or quickly answer “what is the next larger key?”

Chapter lab · Python implementation

The code below builds the same teaching table shown above: eight buckets, integer keys, and a list of pairs in each bucket. make_table creates the buckets; put inserts or updates; get finds a value; remove deletes one pair; resize moves pairs into a new table. This is separate chaining, one possible hash-table implementation. Its simple key % capacity rule makes collisions visible; Python’s real dict uses its own hashing and storage rules. This small table does not resize automatically. Run the assertions to see that two colliding keys stay separate and that updates do not create duplicates. The final two functions apply Python dictionaries to Two Sum and frequency counting.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def make_table(capacity=8):
    if capacity <= 0:
        raise ValueError("capacity must be positive")
    return [[] for _ in range(capacity)]


def put(table, key, value):
    bucket = table[key % len(table)]
    for position, (stored_key, stored_value) in enumerate(bucket):
        if stored_key == key:
            bucket[position] = (key, value)  # Update this key.
            return
    bucket.append((key, value))  # A new key, even if its bucket is used.


def get(table, key):
    bucket = table[key % len(table)]
    for stored_key, value in bucket:
        if stored_key == key:
            return value
    raise KeyError(key)  # No matching key in this bucket.


def remove(table, key):
    bucket = table[key % len(table)]
    for position, (stored_key, value) in enumerate(bucket):
        if stored_key == key:
            bucket.pop(position)
            return value
    raise KeyError(key)


def resize(table, capacity):
    new_table = make_table(capacity)
    for bucket in table:
        for key, value in bucket:
            # Existing keys are unique, so no duplicate-key scan is needed.
            new_table[key % capacity].append((key, value))
    return new_table


def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        needed = target - value
        if needed in seen:
            return seen[needed], index
        seen[value] = index
    return None


def count_values(values):
    counts = {}
    for value in values:
        counts[value] = counts.get(value, 0) + 1
    return counts

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

table = make_table()
put(table, 10, "Maya")
put(table, 18, "Ravi")
assert table[2] == [(10, "Maya"), (18, "Ravi")]
assert get(table, 10) == "Maya"
assert get(table, 18) == "Ravi"

put(table, 18, "Ravi Kumar")
assert get(table, 18) == "Ravi Kumar"
assert sum(len(bucket) for bucket in table) == 2

larger = resize(table, 16)
assert larger[10] == [(10, "Maya")]
assert larger[2] == [(18, "Ravi Kumar")]
assert get(larger, 10) == "Maya"
assert get(larger, 18) == "Ravi Kumar"
assert remove(table, 10) == "Maya"
assert get(table, 18) == "Ravi Kumar"
assert table[2] == [(18, "Ravi Kumar")]

try:
    get(table, 26)  # Same bucket, but this key was never inserted.
    raise AssertionError("missing keys must not return another value")
except KeyError:
    pass

try:
    remove(table, 10)  # Already removed.
    raise AssertionError("a missing key cannot be removed")
except KeyError:
    pass

try:
    make_table(0)
    raise AssertionError("zero buckets cannot hold a table")
except ValueError:
    pass

assert two_sum([2, 7, 11, 15], 9) == (0, 1)
assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([3], 6) is None
assert count_values([1, 2, 1]) == {1: 2, 2: 1}
assert count_values([]) == {}