Как Python решает коллизии при хешировании?

Question

При коллизии CPython применяет perturbation‑алгоритм (шаговая арифметика) для вычисления следующей позиции в таблице. Если таблица перегружена, происходит её расширение, и все элементы перехешируются заново. Удалённые слоты помечаются dummy, чтобы не нарушить поиск.

YeaHub · Accepted Answer

Perturbation Algorithm:perturb >>= PERTURB_SHIFT
index = (5*index + 1 + perturb) & maskуменьшает кластеризацию линейного пробирования.Dummy‑слоты:пометка удалённых позиций, чтобы продолжить поиск других ключей.Resize:при загруженности выше ≈66% создаётся новая таблица и перехеширование.Сложность:средняя O(1) даже при коллизиях.