Какие знаешь способы решения хеш коллизии

В Python хеш-коллизии решаются несколькими способами, в зависимости от реализации словаря (до Python 3.6 и после):

1. Метод цепочек (Chaining)
   Каждый бакет содержит связанный список элементов с одинаковым хешем. При коллизии элемент добавляется в список.
   python

   Копировать

   # Пример упрощенной реализации
   bucket = [[] for _ in range(10)]
   def insert(key, value):
       index = hash(key) % 10
       bucket[index].append((key, value))

2. Открытая адресация (Open Addressing)
   Используется в современных Python (3.6+). При коллизии ищется следующий свободный бакет (например, линейное пробирование).

   python

   Копировать

   # Псевдокод для поиска следующего бакета
   def find_slot(key):
       index = hash(key) % size
       while table[index] is not None and table[index].key != key:
           index = (index + 1) % size
       return index

3. Улучшенные хеш-функции
   Python использует рандомизированные хеши (PYTHONHASHSEED) для защиты от DoS-атак, что уменьшает вероятность коллизий.

4. Перехеширование (Rehashing)
   При заполнении таблицы > 2/3 происходит ресайз и перераспределение элементов.

Современные Python словари (compact dict) комбинируют открытую адресацию с дополнительным массивом индексов для эффективности.