Кукушкино хеширование: два места на ключ и поиск за две пробы

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

Как думаешь, можно ли гарантировать две пробы

В хеш-таблице с цепочками поиск «в среднем» быстрый, но самая длинная цепочка растёт с размером таблицы - это показал прошлый урок. При открытой адресации то же самое с сериями занятых ячеек.

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

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

Птенец кукушки выталкивает из гнезда чужое яйцо. Здесь выталкивают не насовсем: у каждого жильца есть второй адрес. Новый жилец приходит по своему первому адресу и занимает квартиру, даже если она занята. Прежний жилец собирает вещи и едет по своему второму адресу, где так же выселяет того, кто там жил.

Цепочка переездов кончается, когда кто-то приезжает в пустую квартиру. Найти любого человека после этого просто: он либо по первому адресу, либо по второму, третьего варианта нет.

Механизм: выселение и граф адресов

Две таблицы t1 и t2 по m ячеек, две хеш-функции h1 и h2. Ключ k может лежать только в t1[h1(k)] или в t2[h2(k)].

поиск(k):     k лежит в t1[h1(k)] или в t2[h2(k)]?           две пробы, всегда
удаление(k):  найти и очистить ячейку                         две пробы

вставка(k):
    повторять не больше предела раз:
        положить k в t1[h1(k)]; если там было пусто - готово
        иначе k = выселенный ключ
        положить k в t2[h2(k)]; если там было пусто - готово
        иначе k = выселенный ключ
    предел исчерпан: выбрать новые h1, h2 и переложить все ключи

Почему вставка вообще может не закончиться. Нарисуем граф: вершины - ячейки обеих таблиц, а каждый ключ - ребро между двумя своими ячейками. Разложить ключи по ячейкам значит выбрать для каждого ребра один из его концов так, чтобы ни одна вершина не была выбрана дважды. В куске графа, где рёбер больше, чем вершин, это невозможно по принципу Дирихле: ключей больше, чем мест, куда им разрешено лечь. Три ключа с одной и той же парой ячеек - самый простой такой кусок.

Откуда порог в половину. Ячеек всего 2m, ключей n. При независимых равномерных хешах это случайный граф. Если доля занятых ячеек не больше 1/2 − ε для постоянного ε > 0, то вероятность допустимой раскладки стремится к единице с ростом n. При доле не меньше 1/2 + ε вероятность компоненты с избытком рёбер стремится к единице. Это асимптотический порог, а не гарантия конкретного набора: три ключа с одной парой адресов не разместятся даже в почти пустой таблице.

Правило

В кукушкиной таблице ключ k лежит либо в t1[h1(k)], либо в t2[h2(k)]. Поиск и удаление - не больше двух проб в худшем случае. Вставка выселяет занимающего ячейку на его второе место и повторяет это до пустой ячейки. При независимых равномерных хешах и заполнении не выше 1/2 − ε для постоянного ε > 0 ожидаемое число выселений постоянно, а вероятность неудачного размещения - O(1/n). При заполнении не ниже 1/2 + ε вероятность невозможности размещения стремится к единице с ростом n.

Разбор: цепочка выселений на таблицах из 11 ячеек

Функции взяты простейшие, чтобы всё считалось в уме: h1(k) = k mod 11, h2(k) = (k div 11) mod 11. Ноль в ячейке означает «пусто», поэтому ключи в примере - положительные числа. Функция вставки возвращает путь - список троек «номер таблицы, ячейка, ключ, который туда лёг».

def h1(k):
    return k % 11

def h2(k):
    return k // 11 % 11

def vstavit(t1, t2, k):
    put = []
    for popytka in range(12):
        m = h1(k)
        put.append([1, m, k])
        vytesnen = t1[m]
        t1[m] = k
        if vytesnen == 0:
            return put
        k = vytesnen
        m = h2(k)
        put.append([2, m, k])
        vytesnen = t2[m]
        t2[m] = k
        if vytesnen == 0:
            return put
        k = vytesnen
    return []

t1 = [0] * 11
t2 = [0] * 11
for k in [20, 50, 53, 75, 100, 67, 105, 3, 36, 39]:
    put = vstavit(t1, t2, k)
    if len(put) > 1:
        print(k, put)
print(t1)
print(t2)

53 [[1, 9, 53], [2, 1, 20]]
75 [[1, 9, 75], [2, 4, 53]]
67 [[1, 1, 67], [2, 9, 100]]
105 [[1, 6, 105], [2, 4, 50], [1, 9, 53], [2, 6, 75]]
36 [[1, 3, 36], [2, 0, 3]]
39 [[1, 6, 39], [2, 9, 105], [1, 1, 100], [2, 6, 67], [1, 9, 75], [2, 4, 53], [1, 6, 50], [2, 3, 39]]
[0, 100, 0, 36, 0, 0, 50, 0, 0, 75, 0]
[3, 20, 0, 39, 53, 0, 67, 0, 0, 105, 0]

Напечатаны только вставки, где кого-то пришлось выселить. Ключ 53: 53 mod 11 = 9, там лежал 20; 20 едет во вторую таблицу в ячейку 20 div 11 = 1. Ключ 105 запускает цепочку из четырёх переездов. Ключ 39 - из восьми, и в конце сам оказывается выселен: 39 занял ячейку 6, по цепочке туда вернулся 50, и 39 уехал на своё второе место, 39 div 11 = 3. Это нормально: цепочка может пройти через одну ячейку дважды и всё равно закончиться. Если же предел в двенадцать кругов исчерпан, функция возвращает пустой путь, и последний выселенный ключ остаётся без места: настоящая реализация в этот момент перестраивает таблицу с новыми функциями и вставляет его заново.

Десять ключей на 22 ячейки - заполнение 45%. Найти любой из них - две пробы: для 105 это t1[6], где лежит 50, и t2[9], где он и есть.

Разбор: что происходит у порога

Таблицы по 500 ячеек, всего 1000. Хеш-функции здесь - приём этого раздела: random.seed(k * 2 + nomer) засевает генератор числом, зависящим от ключа и номера таблицы, и первое случайное число после этого намертво привязано к ключу. Получается функция, которая ведёт себя как случайная. Ключи вставляются по порядку; на отметках печатается заполнение, число выселений с начала и самая длинная цепочка.

import random

def mesto(k, nomer, m):
    random.seed(k * 2 + nomer)
    return random.randrange(m)

def vstavit(t, k, m, predel):
    nomer = 0
    for shag in range(predel):
        i = mesto(k, nomer, m)
        vytesnen = t[nomer][i]
        t[nomer][i] = k
        if vytesnen == 0:
            return shag
        k = vytesnen
        nomer = 1 - nomer
    return -1

m = 500
t = [[0] * m, [0] * m]
granicy = [100, 200, 300, 400, 450]
vytesnenij = 0
hudshaya = 0
kljuch = 1
for g in granicy:
    while kljuch <= g:
        shagov = vstavit(t, kljuch, m, 40)
        vytesnenij = vytesnenij + shagov
        hudshaya = max(hudshaya, shagov)
        kljuch = kljuch + 1
    print(g, round(g / (2 * m), 2), vytesnenij, hudshaya)

100 0.1 8 1
200 0.2 28 1
300 0.3 71 3
400 0.4 163 5
450 0.45 192 5

На первую сотню ключей пришлось 8 выселений, на четвёртую - 92, почти по одному на вставку. Самая длинная цепочка до заполнения 45% - пять переездов.

Теперь вставка продолжается до первого отказа - до вставки, которой не хватило сорока переездов. Четыре опыта с разными наборами ключей; печатаются число вставленных ключей, заполнение и среднее число выселений на вставку.

import random

def mesto(k, nomer, m):
    random.seed(k * 2 + nomer)
    return random.randrange(m)

def vstavit(t, k, m, predel):
    nomer = 0
    for shag in range(predel):
        i = mesto(k, nomer, m)
        vytesnen = t[nomer][i]
        t[nomer][i] = k
        if vytesnen == 0:
            return shag
        k = vytesnen
        nomer = 1 - nomer
    return -1

m = 500
for opyt in range(4):
    t = [[0] * m, [0] * m]
    kljuch = opyt * 100000 + 1
    vytesnenij = 0
    vstavleno = 0
    while True:
        shagov = vstavit(t, kljuch, m, 40)
        if shagov < 0:
            break
        vytesnenij = vytesnenij + shagov
        vstavleno = vstavleno + 1
        kljuch = kljuch + 1
    print(vstavleno, round(vstavleno / (2 * m), 3), round(vytesnenij / vstavleno, 3))

519 0.519 0.732
590 0.59 0.864
513 0.513 0.819
535 0.535 0.936

Отказ наступил на 520-м, 591-м, 514-м и 536-м ключе - при заполнении от 51 до 59%. Порог в половину - асимптотическая граница: с постоянным превышением порога вероятность отказа растёт к единице при увеличении таблицы. В конечной таблице точка первого отказа зависит от хешей.

Граница схемы «две функции, один ключ в ячейке» - как раз эти 50%: почти половина памяти обязана пустовать. Её сдвигают двумя способами. Для больших таблиц и хеш-функций, близких к случайным, ячейка на четыре ключа поднимает порог до 98% (на практике таблицу держат заполненной до 95%), а поиск по-прежнему смотрит в две ячейки; при коротких ключах каждая целиком помещается в строку кеша процессора. Три хеш-функции вместо двух дают порог около 91% при одном ключе в ячейке, четыре - около 97%.

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

Вставка без предела. Если в графе адресов образовался кусок, где ключей больше, чем ячеек, цепочка выселений ходит по кругу бесконечно. Предел числа переездов обязателен, и за ним должна стоять перестройка с новыми функциями.

Плохие хеш-функции. Три ключа, у которых совпали оба адреса, не раскладываются никогда. У функций из первого разбора это, например, 6, 127 и 248: h1 у всех равна 6, h2 - нулю, одиннадцати и двадцати двум по модулю 11, то есть тоже нулю. Двух независимых функций хорошего качества схема требует строже, чем таблица с цепочками, которая на плохой функции всего лишь замедляется.

Заполнение «как у обычной таблицы». Привычные 70-75% для схемы с одним ключом в ячейке лежат за порогом. Расширять таблицу нужно до половины, а не после.

Гарантия на вставку. Две пробы обещаны поиску. Отдельная вставка может занять десятки переездов или вызвать полную перестройку за Θ(n); постоянна только её средняя цена.

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

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

Кукушкин фильтрРазбирается в разделе 20, глава «Фильтр Блума, count-min, HyperLogLog»: Фильтр Блума изнутри: откуда формулы, что при переполнении и как удалять - вероятностная структура того же назначения, что фильтр Блума, но с удалением: в ячейках лежат не ключи, а их короткие отпечатки. О нём - в главе про вероятностные структуры этого раздела.

И сама идея «у элемента два допустимых места, и занятые можно перекладывать» шире хеш-таблиц: это способ превратить случайную раздачу с длинным худшим случаем в раздачу с гарантией, заплатив редкой дорогой перестройкой.

Теперь сам

1. По функциям из первого разбора: в каких двух ячейках может лежать ключ 100?
2. В таблицах из первого разбора ищут ключ 61, которого там нет. Какие ячейки проверит поиск и что в них лежит?
3. Две таблицы по 1000 ячеек. Сколько ключей можно хранить, не выходя за порог?
4. Почему три ключа с адресами (4, 7), (4, 7), (4, 7) невозможно разместить?
5. Вставка в среднем стоит постоянное число шагов. Что тогда означает фраза «вставка за O(1) в ожидании, но не в худшем случае» для системы, которой нужно ответить за 10 мс?