Какие существуют методы разрешения коллизий?

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

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

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

• Преимущества: Простота реализации, таблица никогда не переполняется (пока есть память для списков), удаление элементов выполняется легко.
• Недостатки: Требует дополнительной памяти для указателей, производительность может деградировать до O(n), если многие ключи попадают в один бакет.

// Упрощённый пример на Python
class HashTableChaining:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]  # Список списков

    def insert(self, key, value):
        index = hash(key) % self.size
        bucket = self.table[index]
        # Проверяем, не обновляем ли существующий ключ
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

Открытая адресация (Open Addressing)

При этом методе все элементы хранятся непосредственно в массиве таблицы. Если целевой слот занят, алгоритм ищет следующий свободный слот согласно определённой последовательности проб.

• Линейное пробирование (Linear Probing): Следующий слот ищется по формуле (hash(key) + i) % size, где i — номер попытки.
• Квадратичное пробирование (Quadratic Probing): Используется формула (hash(key) + c1*i + c2*i²) % size для уменьшения кластеризации.
• Двойное хэширование (Double Hashing): Для вычисления шага используется вторая хэш-функция: (hash1(key) + i * hash2(key)) % size.

// Пример линейного пробирования
class HashTableOpenAddressing:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size  # Массив для пар (key, value) или None

    def insert(self, key, value):
        index = self._hash(key)
        for i in range(self.size):
            probe_index = (index + i) % self.size
            if self.table[probe_index] is None or self.table[probe_index][0] == key:
                self.table[probe_index] = (key, value)
                return
        raise Exception("Хэш-таблица переполнена")

    def _hash(self, key):
        return hash(key) % self.size

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

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