Page 105 - Data Structures Handout_Neat

9.4 Collision Resolution Techniques

Collisions are inevitable in hash tables because different keys may map to the same

index. To ensure that no data is lost and operations remain efficient, we need strategies to
resolve collisions. The two broad categories are separate chaining and open addressing.

Open addressing itself includes several variations: linear probing, quadratic probing, and

double hashing.

9.4.1 Chaining

Chaining stores multiple keys at the same index using a linked list (or another dynamic

structure). When a collision occurs, the new key is simply added to the list at that index.

Searching involves traversing the list.

Example: Chaining in C++

105