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

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

1. Метод цепочек - элементы с одинаковым хэшем хранятся в связном списке. Пример:

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

2. Открытая адресация - поиск следующей свободной ячейки при коллизии:

   • Линейное пробирование: (hash(key) + i) % size
   • Квадратичное пробирование: (hash(key) + i^2) % size
   • Двойное хэширование: (hash1(key) + i * hash2(key)) % size

3. Увеличение размера таблицы - при достижении load factor (обычно 0.7-0.8) таблица расширяется и перехэшируется.

В CPython используется комбинация открытой адресации с псевдослучайным пробированием для минимизации кластеризации.