In this lesson, you will learn how hash indexes maintain data integrity when different keys produce the same hash value, a scenario known as a "collision."
The Collision Reality
A hash index works by applying a mathematical hash function to a search key to determine exactly where a record lives in a memory-based bucket. Because there are a finite number of buckets, it is statistically inevitable that two different keys will occasionally produce the exact same hash value. This is called a collision.
If the database simply overwrote the existing data, you would lose information. Instead, hash indexes must handle these conflicts gracefully to ensure every record remains accessible.
Chaining: The Solution
The most common technique to handle collisions is Chaining. When two keys produce the same hash result, the database does not force them into the same slot. Instead, it creates a "linked list" (or chain) starting at that bucket.
Imagine your hash index has a bucket for the value 501. If UserA and UserB both hash to 501, the database stores them like this:
Bucket 501 -> [UserA | Pointer] -> [UserB | NULL]
When you perform a lookup for UserB:
- The engine hashes the key and finds
501. - It jumps to bucket
501. - It checks the first entry: "Is this
UserB?" No, it’sUserA. - It follows the pointer to the next entry in the chain.
- It finds
UserBand returns the data.
Performance Considerations
While chaining keeps the data safe, long chains can degrade performance. If too many keys collide in the same bucket, the hash index starts to behave like a linked list, requiring a "scan" of the chain rather than an instant "seek." This is why database engines carefully choose hash functions that distribute keys as evenly as possible across all available buckets to minimize the likelihood of long chains forming.
Key Takeaway: When a hash collision occurs, the database uses "chaining" to store multiple records in a linked list at the same bucket, allowing it to navigate through the conflict to retrieve the correct row.