Что такое коллизия в хеш-таблицах и как с ней работать?

Коллизия в хеш-таблице — это ситуация, когда хеш-функция вычисляет один и тот же индекс для двух разных ключей.

Методы разрешения коллизий:

1. Метод цепочек (Separate Chaining): В ячейке таблицы хранится указатель на связный список (или другую структуру данных), содержащий все элементы, хеширующиеся в этот индекс.

   // Пример структуры для связного списка в ячейке таблицы
   struct Node {
       KeyType key;
       ValueType value;
       Node* next;
   };
   
   // Хеш-таблица: массив указателей на Node
   Node* table[TABLE_SIZE];
   
   // Вставка: если ячейка занята, добавляем в связный список
   void insert(KeyType key, ValueType value) {
       int index = hash_function(key) % TABLE_SIZE;
       Node* newNode = new Node{key, value, table[index]};
       table[index] = newNode;
   }
   

2. Метод открытой адресации (Open Addressing): При коллизии ищется следующая свободная ячейка в таблице согласно некоторому правилу пробирования. Элементы хранятся непосредственно в ячейках самой таблицы.

   • Линейное пробирование (Linear Probing): Ищется следующая ячейка по формуле (hash(key) + i) % TABLE_SIZE, где i увеличивается на 1 при каждой попытке.
   • Квадратичное пробирование (Quadratic Probing): Ищется следующая ячейка по формуле (hash(key) + i^2) % TABLE_SIZE, где i увеличивается при каждой попытке.
   • Двойное хеширование (Double Hashing): Ищется следующая ячейка по формуле (hash1(key) + i * hash2(key)) % TABLE_SIZE, где i увеличивается при каждой попытке, а hash2 - другая хеш-функция.

   // Пример структуры для ячейки таблицы с открытой адресацией
   enum State { EMPTY, OCCUPIED, DELETED };
   
   struct Cell {
       KeyType key;
       ValueType value;
       State state;
   };
   
   // Хеш-таблица: массив Cell
   Cell table[TABLE_SIZE];
   
   // Вставка с линейным пробированием
   void insert_open_addressing(KeyType key, ValueType value) {
       int index = hash_function(key) % TABLE_SIZE;
       int i = 0;
       while (table[(index + i) % TABLE_SIZE].state == OCCUPIED) {
           i++;
       }
       table[(index + i) % TABLE_SIZE] = {key, value, OCCUPIED};
   }
   

Метод цепочек обычно проще реализовать и имеет предсказуемую производительность при высокой загрузке. Открытая адресация может иметь лучшую локальность данных, но более чувствительна к коэффициенту загрузки и требует особого подхода при удалении элементов (пометку как "удаленные"). Выбор метода зависит от требований к производительности, использованию памяти и простоты реализации.