Core Data Structures

Hash Tables

A hash table maps keys to array indices via a hash function, giving O(1) average-case lookup, insert, and delete. Collisions — two keys hashing to the same slot — are handled by chaining or open addressing, and the load factor governs when to resize.

A hash function maps a key to an array index; a good one distributes keys uniformly to minimize collisions
Chaining: each bucket holds a list (or, in modern HashMap, a tree once a bucket gets large) of all keys that hashed there
Open addressing: on collision, probe for the next open slot in the same array (linear, quadratic, or double hashing) — no extra structure per bucket
Load factor α = n / capacity governs performance; resizing (rehashing everything into a bigger array) keeps α bounded and operations O(1) amortized
Worst case is O(n) — if all keys collide into one bucket — which is why hashCode quality and randomized seeding both matter
A key's hashCode and equals must agree: equal objects must have equal hash codes, or hash-based lookups silently fail to find them

Chaining vs. open addressing
Aspect	Chaining	Open addressing
On collision	Append to the bucket's list/tree	Probe for the next free slot
Load factor > 1?	Fine — buckets just get longer	Impossible — table can never be full past capacity
Deletion	Simple — remove from the bucket	Needs tombstones, or the probe chain breaks
Memory overhead	Pointer per entry	None extra, but needs empty slack space
Used by	Java `HashMap` (chaining, treeified when a bucket gets long)	Python `dict`, many C hash-table libraries

The equals/hashCode contract, and what breaks when it is violated

final class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override public boolean equals(Object o) {
        return o instanceof Point p && p.x == x && p.y == y;
    }
    @Override public int hashCode() {
        return Objects.hash(x, y);      // MUST be consistent with equals
    }
}

// Without a matching hashCode(), two "equal" Points could land in different
// buckets, and map.get(new Point(1,2)) would return null even after
// map.put(new Point(1,2), value) — the classic silent hash-table bug.

Java's HashMap uses chaining, but since Java 8 a bucket that grows past a threshold (8 entries, with table size ≥ 64) converts from a linked list to a small red-black tree, capping the true worst case at O(log n) per bucket instead of O(n) — a defense specifically against hash-flooding attacks or unlucky hash distributions. See the Java-specific hashing internals topic for the full mechanism.