Как разрешаются коллизии в хеш-таблице в Python

В Python хеш-таблицы реализованы через словари (dict). Коллизии разрешаются методом открытой адресации с использованием алгоритма "псевдослучайного зондирования".

Основные моменты:

1. При коллизии Python ищет следующую свободную ячейку в таблице по формуле:
   index = (5 * index + 1 + perturb) % table_size
   Где perturb — это сдвиг для уменьшения кластеризации.

2. При заполнении таблицы на 2/3 происходит ресайз (увеличение размера).

Пример:

d = {}
d['key1'] = 1  # hash('key1') % table_size → index1
d['key2'] = 2  # Если index1 занят, вычисляется новый индекс

Это обеспечивает амортизированную O(1) сложность для вставки и поиска.