Turning a key into a slot

A hash table is an array

Underneath, a hash table is one ordinary array. Each element, called a slot or a bucket, can hold one entry: a key together with its value. Arrays are fast for one reason. The address of element i is the array's start address plus i times the size of an element, so reaching any slot takes one multiplication and one memory access, however big the array is.

So the table's whole job is to turn a key into that index i. The previous lesson turned the key into a number. This lesson turns the number into an index between 0 and the array's length minus one.

From a big number to a slot

The obvious way to squeeze a big number into a small range is the remainder after division. For a table of 8 slots, 98262 % 8 is 6, so "cat" goes into slot 6. The remainder of any number divided by 8 is between 0 and 7, so the result is always a valid index. This works for a table of any size, and tables that use prime-numbered sizes, such as the common implementations of C++'s std::unordered_map, do exactly this.

The catch is the cost. Integer division is one of the slowest arithmetic instructions a processor has, many times slower than an addition, and the table divides on every insert and every lookup.

The power-of-two trick

If the table's capacity is a power of two, there is a shortcut. Dividing by 8 and keeping the remainder gives the same result as keeping the lowest three bits, because 8 is 2 to the power of 3. Keeping the lowest bits takes a single AND instruction with a mask, and the mask is the capacity minus one: 7, or 111 in binary.

Here is the arithmetic from the trace, written out in binary:

98262       = 1 0111 1111 1101 0110
7 (mask)    = 0 0000 0000 0000 0111
98262 & 7   = 0 0000 0000 0000 0110   → slot 6

The AND keeps the bits where the mask has a 1 and clears all the others. It gives the same answer as the division at a fraction of the cost. This is why Java's HashMap, Python's dict, Go's map and Rust's HashMap all keep their capacity at a power of two.

The price of the trick: only the low bits count

The mask throws away everything except the lowest few bits. With 8 slots, only three bits of a 32-bit hash decide where a key goes; the other 29 are ignored. If a hash function produces values that differ mostly in their high bits, many keys will land in the same slot, even though their full hashes are all different.

Real tables guard against this by mixing the hash before masking it. Java's HashMap takes the key's hashCode() and XORs its top 16 bits into its bottom 16 bits, h ^ (h >>> 16), so that a difference anywhere in the hash can change the slot. Other tables run the hash through extra multiply and shift steps for the same reason. The practical lesson for you is short: if you write a hash function for your own type, make sure its low bits vary, not just its high ones.

Insert and lookup

With the slot computation in hand, the two basic operations are short:

• Insert computes the slot and stores the key and the value there.
• Lookup computes the slot in the same way, then compares the key stored there with the key it was given. If they are equal, it returns the value. If the slot is empty, the key is not in the table.

The comparison matters. The mask keeps only a few bits of the hash, so many different keys share each slot, and even two keys with equal full hashes can be different keys. A full slot tells you that some key landed there, not that it is the one you are looking for. That is why a hash table stores the keys and not only the values, and why every key type needs a correct equality check as well as a hash.

What it costs

Count the work in a lookup: hash the key, one AND, one memory access and one key comparison. None of those steps depends on how many entries the table holds. Whether it holds 8 entries or 8 million, a lookup that lands on its slot does the same amount of work. In the notation of the Big-O module, that is O(1), constant time, compared with O(n) for searching an unsorted list.

There are two honest caveats. First, hashing a key takes time in proportion to its length, so a lookup with a 10,000-character string key is slower than one with an integer key; O(1) counts the table's operations, not the size of the key. Second, this lesson only looked at keys that landed on empty slots. The next lesson deals with what happens when two keys want the same slot.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Turning a key into a slot from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function two_sum_hash(nums, target):
    seen = empty_hash_map()
    for i from 0 to length(nums) - 1:
        need = target - nums[i]
        if need in seen:
            return (seen[need], i)
        seen[nums[i]] = i
    return (-1, -1)

#include <vector>
#include <unordered_map>
 
std::pair<int, int> twoSumHash(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    seen.reserve(nums.size() * 2);
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {-1, -1};
}

import java.util.*;
 
public class HashSolver {
    public static int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) return new int[]{seen.get(need), i};
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

def two_sum_hash(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return -1, -1

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.