Page 116 - Data Structures Handout_Neat
P. 116
9.7 Limitations of Hashing
Although hashing is a powerful technique that provides fast average-case
performance, it is not without limitations. Understanding these drawbacks is essential for
designing efficient systems and avoiding pitfalls. The limitations can be grouped into issues of
collision overhead, memory usage, and security concerns.
9.7.1 Collision Overhead
Collisions occur when two different keys map to the same index. While collision
resolution techniques (like chaining or open addressing) exist, they introduce overhead. In
chaining, long linked lists at a single index can slow down searches. In open addressing,
probing sequences can become long, especially when the table is nearly full, degrading
performance from (1)to ( ).
Example: Demonstrating Collision Overhead in C++
116
