What methods exist to prevent or resolve collisions when working with hash functions?

Hash collisions occur when different keys produce the same hash value. The following methods are used to prevent or resolve collisions:

1. Chaining method — each cell in the hash table stores a linked list of elements with the same hash. When a collision occurs, the new element is added to the list.

2. Open addressing — upon collision, the next free cell is sought according to a certain sequence (linear probing, quadratic probing, double hashing).

3. Double hashing — when a collision occurs, a second hash value is calculated, which determines the step size for searching the next cell.

4. Rehashing — when a certain load factor is reached, a new larger table is created, and all elements are rehashed.

Example of chaining method:

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

Node* hashTable[SIZE];

void insert(int key) {
    int hash = key % SIZE;
    Node* newNode = new Node{key, hashTable[hash]};
    hashTable[hash] = newNode;
}