HashMaps: The Magic Lookup

The Most Important Structure

A HashMap (called a Dictionary in Python, an Object in JavaScript, a HashMap in Java) maps Keys to Values. It is the single most frequently used data structure in interview problem-solving because it converts O(N) search problems into O(1) lookup problems.

The core idea: instead of scanning a list to find something, you compute exactly where it is stored.

How It Works: The Hash Function

1. Hashing: You pass a key (e.g., the string "apple") to a hash function. The hash function deterministically converts any input into an integer. Same input always produces the same output. Example: hash("apple") → 3452891.

2. Index Mapping: You take that integer modulo the size of the underlying array: 3452891 % 16 = 5. This gives you an array index.

3. Storage: The value associated with "apple" is stored at index 5 of the backing array.

4. Lookup: To retrieve the value, you hash the key again, compute the same index, and read from that position — all in O(1).

# Python dict is a HashMap
inventory = {}
inventory["apple"] = "red"    # hash("apple") → index 5 → store "red"
color = inventory["apple"]    # hash("apple") → index 5 → read "red" → O(1)

Average-case complexities:

The worst case occurs when many keys collide at the same index — covered in the next section.