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

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

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

   Копировать

   class HashTable:
       def __init__(self, size):
           self.size = size
           self.table = [[] for _ in range(size)]
       
       def insert(self, key, value):
           hash_key = hash(key) % self.size
           self.table[hash_key].append((key, value))

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

   Копировать

   def insert(self, key, value):
       index = hash(key) % self.size
       while self.table[index] is not None:
           index = (index + 1) % self.size
       self.table[index] = (key, value)

Нюансы:

• В CPython (dict) используется открытая адресация с псевдослучайным пробированием.
• Метод цепочек проще, но требует доп. памяти на ссылки.
• Open Addressing быстрее для небольших таблиц, но чувствителен к коэффициенту заполнения.