Hash Tables, Stacks, Queues and Linked Lists

Deterministic, fast to compute, and spreads keys uniformly across buckets so collisions are rare; equal keys must hash equally.

O(1) average with a good hash and bounded load factor; O(n) worst case when many keys collide into one bucket. Java 8+ HashMap converts long chains into balanced trees, capping that bucket at O(log n).

They must have equal hash codes; overriding equality without matching the hash breaks hash maps. Unequal objects may still share a hash.

If the key is mutated after insertion its hash changes, so it lands in the wrong bucket and becomes unfindable.

Each bucket holds a list (or small tree) of entries; colliding keys are appended to the bucket's chain. Expected chain length equals the load factor.

All entries live in the array itself; on collision you probe other slots (linear, quadratic, or double hashing) until an empty one is found.