Name: Sobes.tech
Rating: 4.9 (250 reviews)

В хеш-таблицах для обработки коллизий (когда два ключа хешируются в одну ячейку) обычно применяются следующие методы:

Метод цепочек (chaining) — в каждой ячейке таблицы хранится связанный список (или другой контейнер) элементов, которые попали в эту ячейку. При коллизии новый элемент добавляется в список.
Открытая адресация (open addressing) — при коллизии ищется следующая свободная ячейка по определённому правилу (линейное пробирование, квадратичное пробирование, двойное хеширование).
Двойное хеширование — используется в открытой адресации, но шаг поиска следующей ячейки определяется вторым хеш-функцией, что уменьшает кластеризацию.
Перехеширование (rehashing) — при достижении определённой загрузки таблицы создаётся новая таблица большего размера, и все элементы перехешируются.

Пример метода цепочек на Python:

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

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

    def insert(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

Этот пример показывает, как при коллизии элементы хранятся в списке (цепочке) в одной ячейке.

Какие методы обработки коллизий в хеш-таблицах вам знакомы?