Solution

The correct answer is Chaining

Key Points

• Chaining:
  • Chaining is a technique where each cell in the hash table is treated as a separate linked list (or any dynamic data structure).
  • When a collision occurs, the key-value pair is stored in the same slot, but as the next node in the linked list.
  • This provides an intuitive and efficient way of handling collisions, and there is no need for an empty spot in the hash table to handle a collision.
  • However, the disadvantage is potential inefficiency due to poor distribution of keys, which could result in a few chains growing very long while others are short or empty.

Additional Information

• Linear Probing:
  • This is an open addressing technique where each cell of a hash table is treated as a slot that can store one key-value pair.
  • When a collision occurs, the algorithm searches linearly in the table until it finds an empty slot.
  • The drawback of linear probing is that it can lead to clustering, where a group of adjacent cells gets filled, increasing the average search time.
• Quadratic Probing:
  • Similar to linear probing, quadratic probing is also an open addressing method intended to deal with collisions.
  • However, instead of searching linearly for an empty slot upon collision, quadratic probing searches the hash table for an empty slot by following a quadratic function (usually of the form i², where i is the attempt number).
  • This method reduces primary clustering, but a unique problem called secondary clustering can occur.
• Double Hashing:
  • Double hashing is a technique where two hash functions are used, one as a primary function and another as a secondary function.
  • If a collision occurs with the first hash function, the second hash function is used to determine another location for the slot.
  • This method is less susceptible to clustering than the linear and quadratic probing methods, but it requires more computational cost due to the use of two hash functions.