Объясните, что происходит при возникновении коллизий в хэш-таблицах и как с ними бороться.

A collision in a hash table occurs when two different keys, after applying the hash function, receive the same index (hash). This is inevitable due to the limited size of the array in which data is stored.

To handle collisions, several main methods are used:

1. Chaining method — each cell of the array stores a linked list (or another container) of elements that received the same index. When a collision occurs, the new element is simply added to the list.

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

Example of chaining method in C++:

#include <iostream>
#include <list>
#include <vector>

class HashTable {
    static const int SIZE = 10;
    std::vector<std::list<int>> table;
public:
    HashTable() : table(SIZE) {}

    int hashFunction(int key) {
        return key % SIZE;
    }

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    bool search(int key) {
        int index = hashFunction(key);
        for (int k : table[index]) {
            if (k == key) return true;
        }
        return false;
    }
};

Thus, collisions do not lead to data loss, and their handling methods ensure the correct operation of the hash table.