Computer Science · Ch 6 — Searching
Collision
Collision
What is a Collision?
Hashing works beautifully when every element in a list maps to a unique slot in the hash table. But that ideal situation does not always happen. Consider a list like [34, 16, 2, 26, 80]. If we use the hash function list[i] % 10, then both 16 and 26 give a hash value of 6. This is a problem because, by definition, two or more elements cannot occupy the same position in a list. This situation is called a collision in hashing.
When a collision occurs, we cannot simply ignore it. We need a mechanism to place the other items that share the same hash value into the hash table. This process is called collision resolution.
Collision Resolution
Collision resolution is the method used to find an alternative slot for the second (and subsequent) items that hash to the same index. The textbook notes that there are many ways to resolve collisions, but it does not discuss those methods in detail — they are considered beyond the scope of the Class XII syllabus.
Perfect Hash Function
If every item in the list maps to a unique index in the hash table, the hash function is called a perfect hash function. When a hash function is perfect, collisions will never occur. This is the ideal case, but it is not always easy to achieve in practice.
Other Hash Functions
Apart from the modulo division method (like % 10), hash functions can be based on several other techniques. These include:
- Integer division
- Shift folding
- Boundary folding
- Mid-square function
- Extraction
- Radix transformation
Again, these methods are beyond the scope of the Class XII textbook.
Time Complexity of Hashing
The time taken by different hash functions may vary, but for a particular hash function, the time remains constant. The key advantage of hashing is that the time required to compute the index value is independent of the number of items in the search list. This makes hashing extremely efficient for searching.
The cost of computing a hash function must be small enough to make hashing-based searching more efficient than other search methods. If the hash function itself is too slow, the overall benefit of hashing is lost.
Summary of Key Points from the Section
- Collision: When two elements map to the same slot in the hash table.
- Collision Resolution: The process of identifying a slot for the second and further items in the hash table when a collision occurs. …