Course contentsShow
← Computer Science
Lesson 417 of 2,87210. Hash TablesFree lesson

Collision Definition and Causes

Understanding what collisions are in hash tables and why they occur when multiple keys hash to the same index.

Collision Definition and Causes

What you'll learn: You'll understand what collisions are in hash tables and why they're an inevitable challenge when storing data.

What Is a Collision?

A collision occurs when two or more different keys produce the same hash value and therefore map to the same index in a hash table. Despite your best efforts to create a good hash function, collisions will happen—and understanding why is essential.

Think of it like a parking garage: even with numbered spots (indices), sometimes two cars (keys) end up assigned to the same parking space number by the ticketing system (hash function). Now you have a problem: where do you actually park the second car?

Why Do Collisions Occur?

There are two fundamental causes:

1. The Pigeonhole Principle

If you have more possible keys than available slots in your hash table, collisions are mathematically guaranteed. For example, if your hash function outputs values from 0-99 (100 slots) but you're hashing 150 different keys, at least 50 collisions must occur.

2. Imperfect Distribution

Even when you have more slots than keys, hash functions rarely distribute values perfectly randomly. Some indices get "unlucky" and receive multiple keys, while others remain empty. A hash function that maps both "cat" and "act" to index 42 creates a collision, even if index 43 is empty.

The Reality Check

No hash function is perfect. Even with excellent hash functions and reasonable load factors, collisions happen due to the compression of a large key space into a smaller index range. This is why hash table implementations need collision resolution strategies.

Key Takeaway: Collisions occur when multiple keys hash to the same index, caused by having more keys than slots or by imperfect hash function distribution—making collision handling essential for any hash table implementation.