Hashing — Paul Guardia

What a hash table is

An array, plus a function that turns any key into an index into it.

Where you meet them

Java's HashMap and HashSet, Python's dict, JavaScript objects. The most-used data structure in software after the array.

Caches

Key to cached value in one step. An LRU cache is a hash table plus a doubly linked list, which is why that pairing is a standard interview question.

Deduplication

"Have I seen this before?" is a hash set membership test — the visited set in every graph traversal is one.

Integrity

Cryptographic hashes are a different animal with a different goal, but the same core idea: arbitrary input, fixed-size fingerprint.

The function itself

Three requirements, one contract, and one bug that will find you eventually.

Deterministic. The same key must produce the same code every time the program runs. Anything derived from a memory address or the clock is disqualified — you would never find what you stored.

Uniform. Codes should spread across the table. A hash that returns 0 for everything is perfectly legal and turns the table into a linked list — correct, but O(n).

Fast. It runs on every single lookup. Java's String.hashCode is h = 31·h + c per character: 31 is an odd prime, and the JIT rewrites 31·h as (h << 5) − h.

The contract: if a.equals(b) then a.hashCode() == b.hashCode(). The reverse need not hold — unequal objects are allowed to collide, and must be, since there are more possible keys than int values. Override one and you must override the other, or two equal objects land in different buckets and your map holds both.

Java then spreads the code before using it: h ^ (h >>> 16). Because the index is taken with & (n−1), only the low bits would otherwise matter, and a hash function that varies mainly in its high bits would collide catastrophically.

Key	hashCode()	& 7	& 15

Real values from String.hashCode(). Note how doubling the capacity moves some keys and not others — that is exactly what a resize has to sort out.

Collision strategy 01

Separate chaining

Let each bucket hold a linked list. Collisions stop being a problem and become a list to walk.

Collision strategy 02

Open addressing

Keep everything in the array itself. If a slot is taken, go looking for another one — which turns deletion into a genuinely subtle problem.

Which strategy, and why

Both are O(1) on average. They fail differently, and they fail at different load factors.

Load factor is size / capacity — how full the table is. It is the single number that governs performance, because it drives the expected chain length or probe count. Java resizes at 0.75.

Chaining degrades gracefully. At a load factor of 2, the average chain is two entries long; the table still works, just slower. It can even exceed capacity, since the lists are unbounded. Java's HashMap goes further and converts a bucket to a red-black tree once its chain passes eight entries, so a worst case that would have been O(n) becomes O(log n).

Open addressing degrades catastrophically. As the table fills, probe sequences lengthen and start merging into each other — primary clustering — and at a load factor near 1 an unsuccessful lookup scans nearly the whole array. It can never exceed capacity at all.

In exchange, open addressing has no per-entry node objects and keeps everything in one contiguous block, so it is far kinder to the cache. That is why it wins in high-performance libraries and loses in general-purpose standard libraries, where predictable behaviour matters more than peak speed.

	Chaining	Open addressing
stores entries	in per-bucket lists	in the array itself
load factor > 1	allowed	impossible
typical resize at	0.75	0.5 – 0.7
deletion	unlink the node	needs tombstones
cache behaviour	pointer chasing	contiguous
memory per entry	value + node + ref	value only
worst case lookup	O(n), O(log n) if treeified	O(n)
used by	Java `HashMap`	Python `dict`, most C++ flat maps

Four ways to break a hash table

All four produce a map that compiles, runs, and quietly gives wrong answers.

Bug 01

equals without hashCode

Two objects compare equal but hash to different buckets, so get looks in the wrong place and returns null for a key that is definitely in the map. The most common Java bug there is.

Bug 02

Mutating a key

Change a field that hashCode reads and the entry is now in the bucket for its old hash. It is unreachable, and it will not even be found by iteration-plus-equals. Use immutable keys.

Bug 03

Modulo on a negative

hashCode() can be negative, and Java's % preserves the sign — -5 % 8 is -5, an ArrayIndexOutOfBounds. Use & (n-1) with a power-of-two capacity, or Math.floorMod.

Bug 04

Clearing a probed slot

In open addressing, emptying a slot severs every probe chain that ran through it. Entries further along become invisible. You must write a tombstone instead — the operation panel above demonstrates it.

Reference code

A chaining map, a probing map, and the contract both depend on.

Capacity is a power of two

Not for elegance — it makes index = h & (n-1) a single AND instead of a division, and division is the slowest integer op there is.

Resize is amortised

Rehashing everything is O(n), but it happens after n insertions, so the cost spread over those insertions is O(1) each. Same argument as a growable array.

Iteration order is not a thing

It follows bucket layout, which changes on every resize. If you depend on it, use LinkedHashMap and say so.

Compare with a tree map

TreeMap is O(log n) but keeps keys sorted and supports range queries. Hash tables are faster and have no order at all — pick on whether you need the ordering.