What are the ways to resolve hash collisions?

1. Separate Chaining Method:

   • Each element of the hash table array (bucket) points to a linked list (or another data structure, such as a tree).
   • All elements hashed to the same bucket are added to this list.

   // Example: linked list node for chaining
   struct Node {
       int key;
       int value;
       Node* next;
   };
   
   // The bucket stores a pointer to the head of the list
   Node* buckets[TABLE_SIZE];
   

2. Open Addressing Methods:

   • All elements are stored directly in the hash table array.
   • When a collision occurs, the search for the next free slot in the array is performed.
   • The method of determining the next slot varies:

     • Linear Probing: Cells are checked in order with a fixed step i, i+1, i+2, ... mod TABLE_SIZE.

       // Example of linear probing
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + 1) % TABLE_SIZE;
       }
       // Now table[i] is either empty or contains the desired element
       

     • Quadratic Probing: Cells are checked with a step depending on the square of the attempt i, i+1², i+2², ... mod TABLE_SIZE.

       // Example of quadratic probing
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       int attempt = 0;
       while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
           attempt++;
           i = (hash(key) + attempt * attempt) % TABLE_SIZE;
       }
       // Now table[i] is either empty or contains the desired element (or the table is full)
       

     • Double Hashing: A second hash function is used to determine the probing step i, i + step, i + 2*step, ... mod TABLE_SIZE, where step is calculated by the second hash function from the key.

       // Example of double hashing
       int hash1(int key) { return key % TABLE_SIZE; }
       int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // Second hash function
       
       int i = hash1(key);
       int step = hash2(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + step) % TABLE_SIZE;
       }
       // Now table[i] is either empty or contains the desired element
       

3. Resizing (Dynamic resizing):

   • When a certain load factor is reached, a new, larger hash table is created.
   • All elements from the old table are rehashed and inserted into the new one.

   // Example logic when resizing is needed
   if (current_size / (double)table_size > max_load_factor) {
       // Create a new table of double the size
       // Rehash and insert all elements from the old table
       // Delete the old table
   }
   

The choice of method depends on performance requirements, memory, implementation complexity, and expected load factor. Separate chaining is usually easier to implement and works well at high load factors but requires additional memory for pointers. Open addressing methods can use memory more compactly but are more sensitive to the choice of hash function and prone to clustering issues. Resizing is necessary to maintain efficiency as the number of elements grows.