What a hash function does

The trick: compute where to look

Searching a list compares your key with the entries one at a time. On average you check half the list; for a million entries that is half a million comparisons. A sorted list with binary search does better, about 20 comparisons for a million entries, but keeping a list sorted makes every insert expensive.

A hash table takes a different route. Instead of searching for the key, it computes where the key should be. A function turns the key into a number, the number picks a position in an array, and the table looks there. If the key was stored, it is in that position, or, as the third lesson shows, very close to it. One computation replaces the search.

That function is the hash function, and this lesson is about what it has to do.

What a hash function promises

A hash function takes a key of any size, a three-letter word or a whole document, and returns a number of a fixed size, typically 32 or 64 bits. For a hash table it has to keep three promises:

1. Same key, same number. Hashing "cat" twice must give the same result, or the table would look in a different place for a key it stored earlier. This property is called being deterministic.
2. Fast. The table hashes the key on every insert and every lookup. A hash function that takes a microsecond makes every operation take at least a microsecond.
3. Spread out. Different keys should produce numbers that look unrelated to each other, so that they land in different positions instead of piling up in a few.

Notice what is missing from that list: different keys are not promised different numbers. They can't be. There are far more possible strings than there are 64-bit numbers, so some different keys must share a hash. When that happens it is called a collision, and handling collisions is the subject of the third lesson.

For now the important rule runs in one direction only: equal keys always have equal hashes, but equal hashes don't mean equal keys. That is why a hash table stores the key itself next to the value and compares it on every lookup.

A real hash function

Java's String.hashCode is a good one to study, because it is short and its exact definition is part of the language specification. It starts at 0 and, for each character, multiplies the running total by 31 and adds the character's code. The trace above runs it on "cat":

• c is 99, so the total becomes 99.
• a is 97, so the total becomes 99 × 31 + 97 = 3,166.
• t is 116, so the total becomes 3,166 × 31 + 116 = 98,262.

That is three multiplications and three additions, with no memory allocated. For a string of length n it takes n steps, so hashing costs time in proportion to the key's length, but it reads each byte once and does almost nothing per byte.

Why multiply at all? The multiplication is what makes position matter. Without it, "cat", "act" and "tac" would all hash to the same value. With it, each character's contribution is scaled by a different power of 31 depending on where it sits in the string.

Why 31? It is odd, so multiplying by it never throws bits away, the way repeatedly multiplying by an even number shifts information off the end. It is also one less than 32, so a compiler can turn x * 31 into (x << 5) - x, a shift and a subtraction. For long strings the running total soon exceeds 32 bits, and Java simply lets it wrap around, keeping the low 32 bits. That is fine: the result only needs to be consistent and well spread, not mathematically meaningful.

Good and bad hash functions

The easiest way to see what "spread out" means is to look at a bad hash. Suppose you hash a word by adding up its character codes:

Every anagram collides, and short words produce small numbers that crowd into a narrow range. A table using this function would put many keys into the same few positions, and its lookups would degrade into searching again.

A good hash function behaves as if it scrambles its input: change one character and about half of the bits in the result change. You rarely need to design one, because every language ships a well-tested hash function for its built-in types. What you do need is to recognize the symptoms of a bad one, many keys with the same hash or hashes that differ in only a few bits, when you write a hash for a custom key type.

Hashing is not encryption

The word "hash" also appears in security: SHA-256 fingerprints files, and passwords are stored as hashes. Those are cryptographic hash functions. They promise much more than a hash table needs, for example that nobody can find two inputs with the same hash, or work backwards from a hash to the input. Keeping those promises costs time, so cryptographic hashes are far too slow to run on every dictionary lookup.

There is one place where the two worlds meet. If attackers know your hash function, they can craft thousands of keys that all hash to the same value and send them to your server, turning every lookup into a slow search. This attack is called hash flooding. Python, Rust and Go defend against it by mixing a random secret into their string hashes: Python picks one when the program starts, and Go and Rust pick one for each new table. Within one table the hash is still deterministic, which is all the table needs, but the attacker can't see the secret, so they can't work out colliding keys in advance. Java's string hash is fixed by its specification, so Java defends itself in a different way, which you will meet in the last lesson of this module.

Hashing anything

Strings are the most common keys, but anything that can be compared for equality can be hashed:

• Integers often hash to themselves. In Java, Integer.hashCode returns the value itself; in Python, hash(42) is 42.
• Records and tuples combine the hashes of their fields, usually with the same multiply-and-add pattern you saw above.
• Floating-point numbers need care. In Python, 0.0 == -0.0 is true, so both must hash to the same value even though their bits differ.

The rule from earlier applies to every type you will ever use as a key: if two keys are equal, their hashes must be equal. In the next lesson you will see how a table turns a number like 98,262 into one of its eight slots.

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

To translate What a hash function does 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.