What methods can be used to resolve collisions in hash tables?

Collisions in hash tables occur when different keys hash to the same index. The main methods to resolve collisions are:

1. Chaining method

   • Each cell of the array contains a linked list of elements that have the same hash.
   • When a collision occurs, the new element is added to the list.

2. Open addressing

   • All elements are stored within the array itself.
   • When a collision occurs, the next free cell is searched according to a specific strategy:
     • Linear probing: subsequent cells are checked sequentially.
     • Quadratic probing: steps increase quadratically.
     • Double hashing: a second hash function determines the step size.

3. Rehashing

   • When a certain load factor is reached, a new larger table is created, and all elements are rehashed and transferred.

Example of chaining method in C++:

struct Node {
    int key;
    int value;
    Node* next;
};

std::vector<Node*> table;

void insert(int key, int value) {
    int hash = key % table.size();
    Node* node = new Node{key, value, table[hash]};
    table[hash] = node;
}

The choice of method depends on performance and memory requirements.