A session store does sessions.get(token) on every request. The Javadoc says constant time. Then someone puts a User as a key whose hashCode is always 0, because equals was generated and hashCode was not. Every lookup walks one giant chain. The product feels like a list. The type is still HashMap.
A hash table maps a key to a bucket, then searches that bucket — not the whole table. The cheap lookup is a bet on a decent hash and a load you respect. Break either and you paid for an array of lists that you still walk.
Glossary words this post will not re-teach — ADT vs implementation, amortized vs worst-case, how to read a complexity table — live on the Data Structures Roadmap. The one that matters here: HashMap.get is expected O(1), not a law. Amortized is the other average (a rare resize spread over many inserts). Expected is the hash bet. Neither one is a guarantee on the next call.
The job: unique keys, fast lookup
Four lines that look the same and are not:
boolean known(List<Session> sessions, String token) {
return sessions.stream().anyMatch(s -> s.token().equals(token));
}
boolean known(Map<String, Session> sessions, String token) {
return sessions.containsKey(token);
}Both pass a test with five sessions. Only the map stays cheap at a hundred thousand. The list walks. The map hashes, then checks a bucket. Same verb, different layout, different bill — the hub already named that gap. This post is the layout behind HashMap and HashSet.
Hash function: key in, bucket index out
A hash function turns a key into an integer. The table turns that integer into an index:
index = hash(key) mod table.lengthA tiny table of eight buckets, and three string keys:
int bucketIndex(String key, int tableLength) {
return Math.floorMod(key.hashCode(), tableLength);
}
// tableLength = 8
bucketIndex("alpha", 8); // some slot in 0..7
bucketIndex("bravo", 8); // usually a different slot
bucketIndex("alpha", 8); // always the same slot as the first "alpha"Two properties matter more than the formula:
- Same key, same hash — otherwise you cannot find what you stored.
- Different keys, well-spread hashes — otherwise every key lands in one bucket and you are back to a list.
Java already gives you Object.hashCode(). A production table also spreads the bits so keys that only differ in high bits do not all collide in a power-of-two table. HashMap does this internally. You do not reimplement it; you make sure your type’s hashCode is not a constant.
Note: hashCode is not encryption and not a unique id. Collisions are expected. The table’s job is to survive them, not to pretend they cannot happen.
Buckets and load factor
The table is an array of buckets. Each bucket holds zero or more entries that hashed to that index. Capacity is how many buckets exist. Size is how many keys you stored. The ratio is the load factor:
load factor α = n / capacityHashMap defaults to capacity 16 and load factor 0.75. When n would pass capacity * loadFactor, the table resizes — usually doubles — and rehashes every key into the new array.
Map<String, Session> sessions = new HashMap<>(); // 16 buckets, 0.75
Map<String, Session> bigger = new HashMap<>(1024); // capacity hint
Map<String, Session> tight = new HashMap<>(1024, 0.50f); // resize earlierA low load factor wastes space and keeps chains short. A high load factor packs the array and makes collisions more likely. 0.75 is the JDK’s compromise, not a number you tune on day one.
Resize is the expensive call: copy the array, re-place every entry. Averaged over a long sequence of inserts, that cost is amortized — same idea as ArrayList growth on the hub. The next put after a resize is not O(1). The long run of puts still is.
Collisions: chaining
Two different keys can produce the same bucket index. That is a collision. Chaining stores every collision in that bucket as a list (or, in Java, sometimes a tree — later).
capacity = 8
hash("token-a") % 8 → 3
hash("token-b") % 8 → 3 collision
hash("token-c") % 8 → 5
buckets:
[0] empty
[1] empty
[2] empty
[3] token-a → token-b chain
[4] empty
[5] token-c
[6] empty
[7] emptyLookup hashes, then walks only that chain and compares keys with equals:
Session get(String token) {
int i = bucketIndex(token, buckets.length);
for (Node n = buckets[i]; n != null; n = n.next) {
if (n.key.equals(token)) {
return n.value;
}
}
return null;
}Insert is the same walk: replace if the key is there, otherwise prepend. Delete unlinks the node.
Chaining is simple and never “runs out of slots” — the chain just grows. The bill shows up when one bucket gets fat. If the hash is decent, chains stay short and the walk looks constant. If every key hashes to bucket 3, get is O(n) and you bought an array of one list.
Collisions: open addressing
Open addressing does not chain. Every entry lives in the table array itself. On a collision, the insert probes for another empty slot.
Linear probing is the picture worth remembering: try i, then i+1, then i+2, wrapping around.
capacity = 8, insert token-a, token-b, token-c
hash("token-a") % 8 → 3 store at 3
hash("token-b") % 8 → 3 3 taken → probe 4 → store at 4
hash("token-c") % 8 → 5 store at 5
slots: _ _ _ a b c _ _
index: 0 1 2 3 4 5 6 7Lookup follows the same probe sequence until it finds the key or an empty slot (the key is absent). Delete cannot leave a naked hole — a later probe would stop too early — so implementations use a tombstone or re-probe on delete.
Quadratic probing and double hashing change the step size so clusters do not grow as fast. The trade-off is the same: no extra node objects, better cache behavior when the table is an array of entries, and a hard ceiling — the table must have an empty slot. Load factor has to stay strictly below 1, and clustering makes “almost full” much worse than chaining at the same load.
Java’s HashMap does not use open addressing. IdentityHashMap does (linear probe). Most of the time you are looking at chaining. Open addressing is the other classic answer, and the reason “hash table” in a textbook is not always the same machine as java.util.HashMap.
Java HashMap: chaining, then trees
HashMap is an array of bins. A bin starts as a linked list. When a bin grows past a threshold (eight entries, and the table is already large enough), Java 8+ treeifies that bin into a red-black tree so a hostile or unlucky hash cannot turn one bucket into a linear scan of n.
That is a mitigation, not a new complexity class for your mental model. Typical bins never treeify. A tree bin makes the worst bucket O(log n) instead of O(n). It does not make get a law of O(1), and it does not fix a broken hashCode.
Other JDK facts that matter in production, not in a textbook diagram:
- Default capacity
16, load factor0.75, resize by doubling. nullkey is allowed (one of them);Hashtableis the legacy synchronized cousin — do not reach for it.- Iteration order is unspecified. Need insertion order?
LinkedHashMap. Need sorted keys?TreeMap— a different layout, later in this series. HashMapis not thread-safe. Concurrent writers needConcurrentHashMap, not a hope.
HashSet is a HashMap whose values are a dummy object. Same buckets, same contract, same “expected O(1)” asterisk. The set post will own uniqueness as an ADT; the machine underneath is this one.
The equals / hashCode contract
The table finds a bucket with hashCode, then confirms the key with equals. Break the pair and the table lies. Implementing the pair on your type is equals and hashCode; this section is the table’s consequence.
The contract, in the only form that matters:
If a.equals(b) is true, then a.hashCode() == b.hashCode() must hold
If hashCodes differ, then equals cannot be true
Equal hashCodes do not imply equals — that is a collisionA class that overrides equals and forgets hashCode is the classic footgun:
final class User {
private final String email;
User(String email) { this.email = email; }
@Override
public boolean equals(Object o) {
return o instanceof User u && email.equals(u.email);
}
// hashCode inherited from Object — identity, not email
}
Map<User, String> roles = new HashMap<>();
roles.put(new User("ada@ex.com"), "admin");
roles.get(new User("ada@ex.com")); // null — different hash, never looks in the right bucketequals says those two Users are the same person. hashCode says they are strangers. The map believes hashCode.
Records get this right because both methods come from the components. A mutable key is the other way to lose an entry: put it, mutate a field that hashCode uses, and the map still has the node in the old bucket.
record UserId(String email) {}
Map<UserId, String> roles = new HashMap<>();
roles.put(new UserId("ada@ex.com"), "admin");
roles.get(new UserId("ada@ex.com")); // "admin"Note: Do not use arrays as keys. array.equals is identity; Arrays.equals is content. hashCode on an array is identity too. If the key is “these values,” wrap them in a record.
Complexity: expected vs worst-case
Read this as a shopping list, the way the hub taught. The cheap column assumes a decent hash and a bounded load factor.
Structure: hash table (chaining, e.g. HashMap)
get(key) expected O(1) worst O(n) — one fat chain
put(key, v) expected O(1) worst O(n) — plus amortized resize
remove(key) expected O(1) worst O(n)
containsKey expected O(1) worst O(n)
scan / iterate O(n)
get by sorted rank not supportedExpected O(1) means: average over typical keys and a hash that spreads. It is not “the next call is one CPU instruction.” A resize is amortized across inserts. A degenerate hash is neither amortized nor expected — it is a list.
Treeified bins in HashMap improve the hostile worst case toward O(log n) per bucket. Do not write O(1) in a design doc and call treeification the proof. Write expected O(1), and measure if the keys are under someone else’s control.
When not to use a hash table
Skip HashMap / HashSet when the job is not “find this key.”
- You need sorted keys or a range. “All sessions with id ≥
X,” iteration in key order, first/last. That is a tree map (TreeMap/TreeSetin the JDK). Hashing destroys order on purpose. - You need insertion order.
HashMapiteration is a walk of buckets, not a timeline.LinkedHashMapkeeps a linked list of entries on top of the table. - The hash is under an adversary, or is constant. Untrusted keys plus a weak
hashCodeused to be a real denial-of-service. Tree bins mitigate; a correct, spreading hash is still the fix. AhashCodethat returns0makes the table a list regardless of JDK version. - The key is mutable and you mutate fields that participate in equality after insert. The entry is still in the table. You will not find it.
nis tiny and the hot path is a scan you already do. Five entries in anArrayListis not a hash-table problem. Do not add a map to look serious.
Do not sort a HashMap on every read to fake ordered keys. You are paying for hashing and for sorting, and you still do not have a sorted structure.
Cheat sheet
Hash: key → int; table does int % capacity → bucket
Collision: two keys, one bucket
Chaining: bucket is a list (HashMap); walk equals
Open address: probe other slots in the array (not HashMap)
Load factor: n / capacity; HashMap default 0.75, then resize
equals/hash: equal keys MUST share a hashCode; records do this
get / put: expected O(1); worst O(n) if the hash collapses
Resize: amortized, like ArrayList growth — not the next-call guarantee
JDK: HashMap / HashSet; LinkedHashMap for insert order; TreeMap for sorted keysDo:
- Name the hot operation (
get/containsKey) before you name the type. - Override
equalsandhashCodetogether, or use a record as the key. - Treat Javadoc “constant time” as expected cost; measure if
nis large or the hash is yours to botch. - Prefer
HashMapfor unordered key → value. PreferHashSetfor uniqueness. Neither is a sorted map.
Don’t:
- Override
equalsand leavehashCodeon identity. - Mutate a key after it is in the table.
- Use a hash table when you need order (insertion or sorted).
- Tune load factor before you have a profile that says the default is the problem.
- Treat treeified bins as permission to ignore a terrible hash.
Wrap-up
A hash table is an array of buckets plus a function that picks one. Collisions are normal: chaining hangs them off the bucket; open addressing slides to the next slot. HashMap chains, treeifies a bin that gets too long, and resizes when the load factor says so. That is why get is cheap in the code you already write — and why it is expected O(1), not physics.
The contract that keeps the bet honest is equals / hashCode. Break it and the map is a list with extra steps. Need order? Different layout. Need sorted keys? TreeMap when that post lands; until then the JDK map on the roadmap is the pointer.
If the next question is “I only care that the key exists, not what it maps to,” that is a set — same machine, smaller surface. The living index on the hub is the map for everything else.