Arrays are fast. If you know an element's index, you can jump directly to it in constant time, or $O(1)$. But what if your lookup key isn't a simple integer? What if you want to store a user's profile information and retrieve it using their username, like 'john_doe'? An array can't use a string as an index.

You could search through an array of user objects until you find the right one, but that's a linear search, an $O(n)$ operation that slows down as your data grows. Hash maps, also called hash tables, solve this problem. They provide a way to map a key of almost any type, like a string, to an integer index. This gives us the power of array-like direct access but with flexible, meaningful keys.

The magic happens through a hash function. This is a special function that takes a key as input and produces a seemingly random integer index as output. A good hash function is deterministic, meaning the same key will always produce the same output index. It should also distribute keys evenly across the available array indices to avoid clustering.

No hash function is perfect. Sooner or later, two different keys will produce the same index. This is called a hash collision. When it happens, we can't store both values in the same array slot. We need a strategy to handle it.

There are two primary methods for collision resolution: chaining and open addressing.

Separate Chaining: With this method, each array slot, often called a bucket, doesn't hold a single value. Instead, it holds a pointer to another data structure, typically a linked list. If multiple keys hash to the same index, their key-value pairs are simply added to that index's linked list. To find an element, you first hash the key to find the correct bucket, then traverse the linked list to find the matching key.

Open Addressing: This strategy stores all entries directly within the main array. If a collision occurs at a specific index, the algorithm probes for the next available empty slot and places the new element there. Common probing techniques include:

• Linear Probing: Check the next slot ($index + 1$), then $index + 2$, and so on, until an empty spot is found.
• Quadratic Probing: Check slots $index + 1^2$, $index + 2^2$, $index + 3^2$, etc. This helps spread out clustered elements.
• Double Hashing: Use a second hash function to determine the step size for probing.

A hash map's performance depends heavily on keeping collisions to a minimum. We measure how full the map is using the load factor.

If the load factor gets too high, collisions become frequent, and performance drops. For a chained hash map, lookup time becomes proportional to the average length of the linked lists, which is equal to the load factor. For open addressing, a high load factor means probes have to travel further to find an empty slot.

To solve this, when the load factor exceeds a certain threshold (often around 0.75), the hash map performs a rehashing operation. It creates a new, larger array, typically double the size. Then, it iterates through every element in the old array, recalculates its hash based on the new array's size, and inserts it into the new array. This is an expensive $O(n)$ operation.

While a single rehash can be slow, it doesn't happen often. Because we double the size each time, the expensive rehashing cost is spread out over many fast, $O(1)$ insertions. This gives hash maps an amortized constant time complexity of $O(1)$ for insertions. On average, the operation is constant time, even though it occasionally has a performance spike.

Ready to test your understanding of hash maps?

By managing the trade-offs between load factor, memory overhead, and collision resolution, hash maps provide an incredibly powerful tool for building high-performance applications.