dict: таблица индексов и плотный массив записей

Если ты знаешь компактную раскладку dict, формулу проб с perturb, зачем удалённому ключу пустышка и когда словарь перестраивается, листай до «Теперь сам».

Как думаешь, что найдёт поиск

В разделе про хеширование был словарь с открытой адресацией. Теперь возьмём таблицу на 8 ячеек и вставим ключи 1, 9 и 17 - у всех трёх младшие три бита одинаковы (001), все хотят в ячейку 1. Потом удалим 9 и спросим, есть ли в словаре 17. Ключ 17 никто не трогал. Может ли поиск ответить «нет»?

Ответь себе до чтения. Может - если удаление просто опустошит ячейку. Как этого избегает CPython, покажет второй разбор.

На что это похоже

Библиотека с журналом выдачи. Журнал - тетрадь, куда книги записывают строка за строкой по мере поступления: это массив записей, и порядок в нём - порядок поступления. А на стене картотека с ящиками: в ящике лежит только номер строки журнала. Картотека маленькая и дешёвая, журнал без пропусков - поэтому вся система меньше, чем если бы в каждом ящике лежала целая карточка книги.

Когда книгу списали, её строку в журнале зачёркивают, а в ящик кладут записку «тут что-то было, ищи дальше». Пустой ящик значил бы «дальше не ищи» - и тот, кто ищет книгу, положенную в соседний ящик из-за тесноты, ушёл бы ни с чем.

Механизм: две таблицы и пробы

Таблица индексов dk_indices хранит в ячейке одно из трёх: номер записи (0, 1, 2…), «пусто» (-1) или «пустышка» (-2, удалённый ключ). Ширина ячейки зависит от размера: байт до 128 ячеек, два байта до 2¹⁵, дальше четыре и восемь. Массив записей dk_entries длиной 2/3 размера таблицы: для ключей-строк запись - ключ и значение (хеш строка хранит сама), для остальных - хеш, ключ и значение, по 8 байт каждое.

Поиск ключа с хешем h в таблице размера 2^k:

i = h & (2^k − 1)            # младшие k битов
perturb = h
пока ячейка i не «пусто»:
    если там номер записи и в записи тот же хеш и равный ключ - нашли
    perturb = perturb >> 5      # сдвигаем: в игру входят старшие биты
    i = (5·i + perturb + 1) & (2^k − 1)
не нашли

Пустышка поиск не останавливает - он идёт дальше. Вставка нового ключа занимает первую ячейку, где нет номера записи: пустую или пустышку.

Почему 5·i + 1? Повтор i → 5·i + 1 по модулю 2^k обходит все ячейки ровно по разу, так что пустое место найдётся. А perturb нужен, потому что хеш целого числа - само число: ключи 0, 1, 2, … садятся каждый в свою ячейку без единой коллизии, но ключи с одинаковыми младшими битами без старших битов шли бы по одной и той же цепочке.

Правило

dict = таблица индексов + плотный массив записей в порядке вставки. Пробы: старт h & маска, дальше perturb >>= 5; i = (5·i + perturb + 1) & маска. Удаление ставит в таблицу пустышку и оставляет дыру в записях; место записи не возвращается. Новый ключ при исчерпанном запасе записей (2/3 размера таблицы) вызывает перестройку: размер - наименьшая степень двойки, не меньшая max(8, 3 · ключей), пустышки и дыры при этом исчезают. Почему три: в таблице на 3k ячеек запас записей - 2/3 · 3k = 2k, то есть после перестройки занята ровно половина запаса, и до следующей можно вставить ещё столько же.

Разбор: старшие биты спасают ключи с общим хвостом

Вставим 300 ключей в таблицу на 512 ячеек дважды: подряд идущие числа и числа k << 16, у которых младшие 16 битов - нули. Считаем, сколько ячеек проверено за все вставки.

def vstavit_vse(klyuchi, razmer, s_perturb):
    # таблица индексов: -1 - пусто; возвращаем, сколько ячеек проверили
    maska = razmer - 1
    tablica = [-1] * razmer
    proverok = 0
    for nomer in range(len(klyuchi)):
        h = klyuchi[nomer]           # у целого числа хеш - само число
        i = h & maska
        perturb = h
        proverok = proverok + 1
        while tablica[i] != -1:
            if s_perturb:
                perturb = perturb >> 5
                i = (5 * i + perturb + 1) & maska
            else:
                i = (5 * i + 1) & maska
            proverok = proverok + 1
        tablica[i] = nomer
    return proverok

podryad = list(range(300))
sdvinutye = []
for k in range(300):
    sdvinutye.append(k << 16)        # младшие 16 битов - нули
for imya, klyuchi in [["0..299", podryad], ["k << 16", sdvinutye]]:
    print(imya, "без perturb:", vstavit_vse(klyuchi, 512, False),
          "с perturb:", vstavit_vse(klyuchi, 512, True))

0..299 без perturb: 300 с perturb: 300
k << 16 без perturb: 45150 с perturb: 1249

Подряд идущие ключи - ровно по одной пробе: «младшие биты как номер ячейки» здесь лучше любого случайного хеша. Сдвинутые ключи все стартуют с ячейки 0. Без perturb у них одна цепочка на всех: k-й ключ проходит k занятых ячеек, всего 1 + 2 + … + 300 = 45150 проб - квадрат. С perturb старшие биты уводят ключи по разным цепочкам: 1249 проб, около четырёх на ключ.

Разбор: почему удалённому ключу нужна пустышка

Ключи 1, 9, 17 в таблице на 8 ячеек: 1 садится в ячейку 1, у 9 и 17 хеш маленький, perturb >> 5 сразу ноль, и они уходят по 5·i + 1: 9 - в ячейку 6, 17 - в 7. Удалим 9 двумя способами - пометим ячейку пустой (-1) или пустышкой (-2) - и поищем 17.

def najti(indeksy, zapisi, klyuch):
    # пробы по таблице индексов, как в CPython; zapisi - [ключ, значение]
    maska = len(indeksy) - 1
    i = klyuch & maska
    perturb = klyuch
    puti = [i]
    while indeksy[i] != -1:
        ix = indeksy[i]
        if ix >= 0 and zapisi[ix][0] == klyuch:
            return [zapisi[ix][1], puti]
        perturb = perturb >> 5
        i = (5 * i + perturb + 1) & maska
        puti.append(i)
    return ["нет", puti]

def vstavit(indeksy, zapisi, klyuch, znachenie):
    maska = len(indeksy) - 1
    i = klyuch & maska
    perturb = klyuch
    # -1 пусто, -2 пустышка: занимать можно и то, и другое
    while indeksy[i] >= 0:
        perturb = perturb >> 5
        i = (5 * i + perturb + 1) & maska
    indeksy[i] = len(zapisi)
    zapisi.append([klyuch, znachenie])

for metka in [-1, -2]:
    indeksy = [-1] * 8
    zapisi = []
    for k in [1, 9, 17]:             # у всех трёх младшие биты 001
        vstavit(indeksy, zapisi, k, "v" + str(k))
    print("индексы:", indeksy)
    # удаляем 9: в записи - дыра, в ячейке индексов - метка
    for i in range(8):
        if indeksy[i] >= 0 and zapisi[indeksy[i]][0] == 9:
            zapisi[indeksy[i]] = [None, None]
            indeksy[i] = metka
    print("метка", metka, "-> ищем 17:", najti(indeksy, zapisi, 17))

индексы: [-1, 0, -1, -1, -1, -1, 1, 2]
метка -1 -> ищем 17: ['нет', [1, 6]]
индексы: [-1, 0, -1, -1, -1, -1, 1, 2]
метка -2 -> ищем 17: ['v17', [1, 6, 7]]

С пустой ячейкой поиск остановился в 6 и ответил «нет» - ключ 17 потерян, хотя лежит в записи 2. С пустышкой поиск прошёл 6 насквозь и нашёл 17 в ячейке 7. Цена: пустышки копятся. Место записи при удалении не возвращается, и словарь, где постоянно удаляют и добавляют, перестраивается, даже не вырастая, - перестройка заодно выметает и пустышки, и дыры в записях.

Когда именно перестраивается растущий словарь, видно на настоящем Python 3.12:

import sys

d = {}
razmer = sys.getsizeof(d)
for i in range(100):
    d[i] = None
    if sys.getsizeof(d) != razmer:
        razmer = sys.getsizeof(d)
        print("ключей", len(d), "- байт", razmer)

ключей 1 - байт 224
ключей 6 - байт 352
ключей 11 - байт 632
ключей 22 - байт 1168
ключей 43 - байт 2264
ключей 86 - байт 4688

Таблица на 8 ячеек держит 5 записей, на шестой - перестройка в ≥ 3 · 5 = 15, то есть 16 ячеек и 10 записей; на одиннадцатой - в 32 ячейки и 21 запись, дальше 64 и 42, 128 и 85. Пороги 6, 11, 22, 43, 86 - ровно на единицу больше запаса записей.

Что ломается без этого

Ключ, сменивший хеш. Ячейку ищут по хешу, вычисленному при вставке. Изменишь объект-ключ так, что изменится хеш, - поиск пойдёт по другой цепочке и ключа не найдёт, хотя он лежит в записях. Поэтому у встроенных изменяемых типов (list, dict, set) хеша нет вовсе, а свой __hash__ обязан зависеть только от тех полей, которые не меняются, пока объект лежит в словаре.

Словарь-очередь. Удаляют самый старый ключ, добавляют новый - и так миллионы раз. Записи копят дыры в начале, и чтобы найти «самый старый», next(iter(d)) идёт по дырам. Для очереди с поиском по ключу есть OrderedDict (from collections import OrderedDict): od[k] = v кладёт в конец, od.popitem(last=False) снимает самый старый.

Зачем это в работе

Компактная раскладка - это и память, и порядок. Словарь на 5 ключей в старой раскладке держал 8 ячеек по 24 байта; в новой - 8 байт индексов и 5 записей по 24 байта: 128 байт вместо 192 (без заголовка словаря, который sys.getsizeof тоже считает), и чем больше словарь, тем ощутимее (байт индекса против трёх слов). А порядок вставки, который раньше был побочным эффектом, с Python 3.7 гарантирован языком: на нём держатся **kwargs, порядок полей в JSON и в dataclasses. Знание о пустышках объясняет, почему кеш на словаре с постоянной сменой ключей периодически «подвисает» на перестройке без всякого роста.

Теперь сам

1. Таблица на 8 ячеек, хеш ключа - 3, ячейка 3 занята. Какая ячейка следующая (хеш маленький, perturb после сдвига равен нулю)?
2. В словаре 10 ключей, таблица на 16 ячеек, запас записей исчерпан. Ты удаляешь один ключ и добавляешь другой. Будет ли перестройка, и какого размера станет таблица?
3. Почему цепочка 5·i + 1 без perturb годится для подряд идущих ключей и плоха для k << 16?