Hashmap

Also known as a dictionary, hash table, or map. A hashmap transforms a key into a number using a hash function, and uses that number as the index to store the value in an array.

key → [hash function] → index → array[index] = value

Example:

{}.get("augusto")  # → "azul"   O(1)

No need to search through the whole structure — the hash function tells you exactly where to look.

How the Hash Function Works

A hash function takes any input (string, number, object) and returns a fixed number. That number, after applying a modulo (%) with the array size, becomes the index.

hash("augusto") % array_size  →  index 3
hash("bernardo") % array_size →  index 7

So the array internally looks like:

index 0: empty
index 1: empty
index 2: empty
index 3: ("augusto", "azul")
...
index 7: ("bernardo", "vermelho")

Well-known hash functions used in cryptography and checksums: - SHA-256 — used in blockchain, TLS, and file integrity checks - MD5 — older, faster, used for non-security checksums

Hashmaps use simpler, faster internal hash functions since security is not the goal — speed is.

Load Factor

The load factor is the ratio of how full the array is:

load factor = number of items / array size

Most implementations resize the array when the load factor reaches 0.7 (70%).

Why 70%?

At 70% capacity, the probability of collisions starts increasing significantly. Keeping the array less than 70% full keeps the average performance close to O(1).

Collisions

A collision happens when two different keys produce the same index after hashing:

hash("augusto")  % 10 → index 3
hash("cleiton")  % 10 → index 3   ← collision!

Both keys map to the same slot. The most common solution is chaining: each slot holds a linked list (or sub-list) of all key-value pairs that landed there.

index 3: [("augusto", "azul") → ("cleiton", "verde")]

When you look up a key, you go to the index and then scan the sub-list for a match.

What Happens at 70% Load Factor?

When the load factor hits 0.7, the hashmap:

1. Allocates a new, larger array (usually doubles in size)
2. Re-hashes all existing keys into the new array
3. Resets the load factor — e.g. 70% of old size becomes ~35% of new size (0.35)

This resize operation is O(n), but it happens rarely. Amortized over many insertions, the average cost stays O(1).

Big O Summary

• Average O(1): the hash function gives you the index directly.
• Worst O(n): happens when many keys collide into the same slot, forcing a scan of the entire sub-list. A good hash function makes this extremely rare.

In Python

Python's dict is a hashmap:

colors = {
    "augusto": "azul",
    "bernardo": "vermelho",
}

colors["augusto"]      # "azul"   → O(1)
colors.get("cleiton")  # None     → O(1)
colors["cleiton"] = "verde"       # O(1)
del colors["augusto"]             # O(1)

Key Takeaways

• A hashmap uses a hash function to convert a key into an array index — enabling O(1) average lookups.
• Internally it is an array + hash function + collision handling (usually chaining with linked lists).
• The load factor (default 0.7) controls when the array resizes to avoid too many collisions.
• Worst-case is O(n), but a good hash function keeps collisions rare, so the average stays O(1).
• In Python, dict is the built-in hashmap implementation.