Как устроены dict и set в CPython

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

Компактный dict

Начиная с Python 3.6 dict состоит из двух частей:

• indices: хеш-массив из небольших целых (пустой слот, удалённый слот или позиция в entries).
• entries: записи (hash, key, value) в порядке вставки.

Поиск идёт по открытой адресации в indices, найденная позиция ведёт в entries. Плюсы: экономия памяти (в разреженном массиве хранятся только маленькие индексы, а тяжёлые записи лежат плотно) и естественный порядок. Порядок гарантирован языком с Python 3.7.

Пробирование

CPython использует не простое линейное пробирование, а пертурбацию, зависящую от ключа: i = (5*i + perturb + 1) & mask, где perturb на каждом шаге сдвигается вправо на 5 бит, и старшие биты хеша тоже влияют на последовательность. Ключи с одинаковыми младшими битами быстро расходятся, кластеризация уменьшается.

def slots(h, size, n):
    mask = size - 1
    perturb = h & (2**64 - 1)
    i = h & mask
    out = []
    for _ in range(n):
        out.append(i)
        perturb >>= 5
        i = (i * 5 + perturb + 1) & mask
    return out

print(slots(1, 8, 5))
print(slots(1000, 8, 5))

[1, 6, 7, 4, 5]
[0, 0, 1, 6, 7]

Модель реализации