Skip to main content

Collision Concepts

Learn Collision Concepts (Hashing, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is a Hash Collision? A collision happens when two DIFFERENT keys hash to the SAME bucket - unavoidable in general, since there are usually far more possible keys than buckets (pigeonhole principle). How a hash table handles collisions is what determines its worst-case behavior. Chaining: each bucket holds a list (or tree) of all entries that hashed there - Java's HashMap uses this. Open addressing: on a collision, probe for the next open slot using a fixed rule (linear probing, quadratic probing, double hashing) - no extra list structure needed.

More lessons in Hashing