Какие существуют способы решения хеш-коллизий?

1. Метод цепочек (Separate Chaining):

   • Каждый элемент массива хеш-таблицы (баккет) является указателем на связный список (или другую структуру данных, например, дерево).
   • Все элементы, хешированные в один баккет, добавляются в этот список.

   // Пример: узел связного списка для цепочек
   struct Node {
       int key;
       int value;
       Node* next;
   };
   
   // В баккете хранится указатель на голову списка
   Node* buckets[TABLE_SIZE];
   

2. Методы открытой адресации (Open Addressing):

   • Все элементы хранятся непосредственно в массиве хеш-таблицы.
   • При коллизии выполняется поиск следующего свободного места в массиве.
   • Различают по способу определения следующего места:

     • Линейное пробирование (Linear Probing): Проверяются ячейки по порядку с фиксированным шагом i, i+1, i+2, ... mod TABLE_SIZE.

       // Пример линейного пробирования
       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;
       }
       // Теперь table[i] либо пусто, либо содержит искомый элемент
       

     • Квадратичное пробирование (Quadratic Probing): Проверяются ячейки с шагом, зависящим от квадрата попытки i, i+1², i+2², ... mod TABLE_SIZE.

       // Пример квадратичного пробирования
       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;
       }
       // Теперь table[i] либо пусто, либо содержит искомый элемент (или таблица перегружена)
       

     • Двойное хеширование (Double Hashing): Используется вторая хеш-функция для определения шага пробирования i, i + step, i + 2*step, ... mod TABLE_SIZE, где step вычисляется второй хеш-функцией от ключа.

       // Пример двойного хеширования
       int hash1(int key) { return key % TABLE_SIZE; }
       int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); } // Вторая хеш-функция
       
       int i = hash1(key);
       int step = hash2(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + step) % TABLE_SIZE;
       }
       // Теперь table[i] либо пусто, либо содержит искомый элемент
       

3. Динамическое изменение размера (Resizing):

   • При достижении определенного коэффициента заполнения (load factor) создается новая, более крупная хеш-таблица.
   • Все элементы из старой таблицы перехешируются и вставляются в новую.

   // Пример логики при надобности ресайза
   if (current_size / (double)table_size > max_load_factor) {
       // Создать новую таблицу удвоенного размера
       // Перехешировать и вставить все элементы из старой таблицы
       // Удалить старую таблицу
   }
   

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