Hash Tables

Overview

A hash table is a data structure that provides near-instantaneous O(1) retrieval, insertion, and deletion. It works by passing a key (like a string or object) into a 'hash function', which mathematically scrambles it into a deterministic integer. This integer is used as the exact array index to store the value.

Direct addressing (creating an array slot for every possible key) requires impossible amounts of memory for things like 64-bit strings. Hash tables decouple the table size from the universe of possible keys, compressing the memory footprint while maintaining the O(1) speed of direct array access.

Where used: Database indexing for exact-match primary key lookups, Algorithmic problem solving to drop O(n^2) nested loops down to O(n) linear passes

Why learn this

• Hash tables (HashMaps/Dictionaries) are the most frequently used data structure in coding interviews to optimize brute-force solutions.
• Understanding that a hash function must be deterministic (same input always equals same output) is critical to avoiding elusive bugs when using custom objects as keys.
• It explains the architectural backbone of modern distributed systems and caching layers.

Aha moment

# The Two Sum Problem
target = 9
arr = [2, 11, 7, 15]
# Brute force: nested loops check (2,11), (2,7) -> 9. O(n^2) time.

# Hash map optimization:
seen = {}
for num in arr:
    complement = target - num
    if complement in seen:
        print("Found it!")
    seen[num] = True
# O(n) time. The hash map remembers the past instantly.

Prediction: You still have to search the `seen` hash map, so it must still be slow.

Common guess: Checking `if complement in seen` takes time proportional to how big `seen` is.

Checking `if complement in seen` takes O(1) time regardless of whether `seen` has 10 items or 10 billion items. The hash function instantly calculates the memory address of the complement. We completely eliminated the inner loop.

Common mistakes

• Using mutable objects as keys: If a key's internal state changes after it is inserted into the hash table, its computed hash value will also change. The table will look in the new hash slot and fail to find the object, effectively losing the data.
• Assuming O(1) is guaranteed: O(1) is the expected, amortized time complexity. In the worst-case scenario (where many keys collide), lookups can degrade to O(n) or O(log n). Real-time systems must account for this.

Glossary

deterministic integer

A number generated by a rule that guarantees the exact same output for the same input.

decouple

To separate two things so that changes in one don't necessarily affect the other.

memory footprint

The total amount of computer memory a program or data structure uses.

Recall questions

• What problem with 'direct addressing' do hash tables solve?
• What is the expected time complexity of retrieval in a hash table, and why?

Understanding checks

If you create a custom `User` class in Java or Python and use instances of it as keys in a hash map, but forget to implement a custom hash function, what happens when you look up a user with identical data?

The lookup fails. By default, languages hash the physical memory address of the object, not its contents. Two distinct objects with identical data will have different memory addresses and thus different hashes.

This is a notorious bug. If you want two distinct objects with the same logical data to be treated as the same key, you must override both the hash function and the equality operator.

An array of 1,000,000 elements needs to be searched for 10,000 specific targets. A nested loop takes 10^10 operations. If we put the 1,000,000 elements in a hash set, what is the new approximate operation count?

1,010,000 operations. It takes 1,000,000 operations to insert the elements into the hash set, and then 10,000 O(1) lookups to find the targets.

This math demonstrates the core pattern of hash-based algorithms: trading O(n) auxiliary space to drop a multiplicative time factor down to an additive one.

Practice tasks

Use a hash map to find a duplicate

Given an array of integers, use a hash map (or set) to find the first number that appears twice in O(n) time.

Continue learning

Previous: Arrays & Memory

Next: Hash Sets vs Maps

Next: Collisions & Load Factor

Next: Frequency Counting

Return to DSA Roadmap