Hash maps and sets: interview prep with practice questions

Hash maps: find by key

A hash map (dictionary, associative array) stores key → value pairs and finds a value by its key in O(1) on average. Inside it is an array of buckets. To store a pair, it runs the key through a hash function, which turns the key into a number, and uses that number to pick a bucket. To look the key up later, it computes the same hash and goes straight to the same bucket.

No scanning, no sorting: the key itself says where to look. That's why hash maps are the most used data structure in everyday code.

Three keys hashed into buckets; two keys land in the same bucket

In real life

user id → profile, word → how many times it appears, product code → price. Any time you'd write a loop to 'find the one with this id', a hash map is usually the answer.

In code: Python · Rust

price = {"apple": 0.5, "bread": 1.2}
price["milk"] = 0.9            # insert, O(1) average
price.get("tea", 0)            # 0 when missing

counts = {}
for w in "a b a".split():
    counts[w] = counts.get(w, 0) + 1   # {'a': 2, 'b': 1}

use std::collections::HashMap;
let mut price: HashMap<&str, f64> = HashMap::new();
price.insert("apple", 0.5);
let tea = price.get("tea");          // Option<&f64>: None

let mut counts: HashMap<&str, u32> = HashMap::new();
for w in "a b a".split(' ') {
    *counts.entry(w).or_insert(0) += 1;
}

Python: d[key] raises KeyError for a missing key; d.get(key, default) doesn't.
Rust: get returns an Option, so a missing key is handled explicitly; the entry API inserts or updates in one lookup.

Check yourself

How does a hash map find the value for a key without scanning all entries?

Collisions and the worst case

Two different keys can hash to the same bucket: a collision. It's normal and handled. Either the bucket holds a small list of entries (chaining), or the map tries the next free slot (open addressing). A lookup then checks one or two extra entries.

The map keeps collisions rare by watching its load factor, entries divided by buckets. When it gets too high, the map allocates more buckets and re-places every entry, like a dynamic array growing. That's why the O(1) is an average: if many keys land in one bucket, lookups degrade towards O(n). Attackers have used this, sending thousands of keys crafted to collide to slow servers down. Python randomises string hashing per process and Rust's default HashMap uses a keyed hash (SipHash) for exactly this reason.

In real life

A web server that puts request parameters into a hash map: with predictable hashing, one request with 100,000 colliding parameter names could tie up a CPU for seconds.

In code: Python · Rust

# Python randomises str hashes per process (see PYTHONHASHSEED)
hash("abc")   # differs between runs

# Your own key type: define __eq__ and __hash__ consistently
from dataclasses import dataclass
@dataclass(frozen=True)
class Point:
    x: int
    y: int      # frozen dataclass gets __hash__ for free

// The default hasher is SipHash with random keys: resistant to crafted collisions.
#[derive(Hash, PartialEq, Eq)]
struct Point { x: i32, y: i32 }

let mut seen = std::collections::HashMap::new();
seen.insert(Point { x: 1, y: 2 }, "start");

Rule for custom keys in any language: equal keys must have equal hashes.
For non-hostile data where speed matters, Rust code often swaps in a faster hasher; the default favours safety.

Check yourself

Why is hash map lookup described as O(1) on average rather than always?

Order: hashed or sorted

A hash map scatters keys over buckets, so it has no natural order. Languages differ in what they promise. Python's dict keeps insertion order (guaranteed since Python 3.7). Rust's HashMap promises no order at all, and it can differ between runs.

When you need keys sorted, use a tree-based map: Rust's BTreeMap, Java's TreeMap. Lookups cost O(log n) instead of O(1), but you get keys in order and can ask for ranges, like every key between 'm' and 'p'. Python has no sorted map built in; people sort the keys when needed or use a third-party package.

In real life

Printing a config file with keys in a stable order; finding every order placed between two timestamps (a range query, natural in a sorted map, impossible to do efficiently in a hash map).

In code: Python · Rust

d = {"b": 2, "a": 1}
list(d)              # ['b', 'a']: insertion order
sorted(d)            # ['a', 'b']: sort when you need it

use std::collections::BTreeMap;
let mut d = BTreeMap::new();
d.insert("b", 2);
d.insert("a", 1);
for (k, v) in &d { println!("{k}={v}"); }   // a=1, b=2: always sorted
let some: Vec<_> = d.range("a".."b").collect();  // range query

Don't rely on HashMap iteration order in Rust, not even in tests.
Insertion order in Python is not sorted order: it's the order you added the keys.

Check yourself

You need all orders with timestamps between 10:00 and 10:15, out of millions keyed by timestamp. Which map fits?

Sets: membership and uniqueness

A set is a hash map without values: it only answers 'is this in here?', in O(1) on average. Adding something already present does nothing, so a set holds each value once.

Sets also support set algebra: union (in either), intersection (in both), difference (in one but not the other). The same rules as hash map keys apply: members must be hashable in Python, and implement Hash + Eq in Rust. Rust also has a sorted BTreeSet, like BTreeMap.

Two overlapping circles: viewers of episode 1 and episode 2

In real life

'Has this user already voted?', unique visitors per day, tags shared by two articles, users who watched episode 1 but not episode 2.

In code: Python · Rust

voted = set()
voted.add("ann")
"ann" in voted              # True, O(1) average

a = {"ann", "li", "bo"}
b = {"bo", "kim", "raj"}
a & b, a | b, a - b        # intersection, union, difference
unique = set([3, 1, 3, 2])  # {1, 2, 3}

use std::collections::HashSet;
let mut voted = HashSet::new();
voted.insert("ann");
voted.contains("ann");   // true

let a: HashSet<_> = ["ann", "li", "bo"].into();
let b: HashSet<_> = ["bo", "kim", "raj"].into();
let both: Vec<_> = a.intersection(&b).collect();

Checking 'x in some_list' inside a loop is O(n) each time; converting the list to a set first turns it into O(1).
insert returns a bool in Rust: false if the value was already there, handy for de-duplication.

Check yourself

Hash maps and sets

Hash maps: find by key

How does a hash map find the value for a key without scanning all entries?

Collisions and the worst case

Why is hash map lookup described as O(1) on average rather than always?

Order: hashed or sorted

You need all orders with timestamps between 10:00 and 10:15, out of millions keyed by timestamp. Which map fits?

Sets: membership and uniqueness

Code checks 'if user_id in banned' for every request, where banned is a list of 200,000 ids. What is the simplest big improvement?

Section complete