DS Структуры данных Структура данных
Хеширование кукушки
Также: Cuckoo hashing · кукушкино хеширование · граф кукушки · cuckoo graph · кукушкин фильтр · cuckoo filter · вытеснение · порог заполнения
Хеш-таблица, где поиск всегда смотрит не больше чем в две ячейки — не в среднем, а в худшем случае. Каждому ключу дают два гнезда, а если оба заняты, новый ключ выселяет старого, как кукушонок, и тот перелетает в своё второе гнездо. Почему это работает до заполнения ровно в половину и резко ломается за ней, видно по графу, где гнёзда — вершины, а ключи — рёбра.
Обычная хеш-таблица быстра в среднем, но не обещает худшего случая: цепочка или ряд занятых ячеек иногда вытягивается. Хеширование кукушки обещает: искомый ключ лежит в одном из двух мест, и больше никуда смотреть не нужно. Платить за это приходится при вставке. Если оба места ключа заняты, он выселяет одного из жильцов, как кукушонок, и тот летит в своё второе гнездо — возможно, выселяя следующего. Ниже две таблицы по десять гнёзд и названия городов.
Пока названий мало, почти все садятся сразу. Ближе к половине заполнения начинаются цепочки вытеснений, а около неё одно из названий не находит места вовсе: вытеснения ходят по кругу. Линии между гнёздами объясняют почему — в куске графа, где это случилось, названий стало больше, чем гнёзд.
Идея
Хеширование кукушки держит две таблицы и две хеш-функции: ключ x может жить только в ячейке h1(x) первой таблицы или в ячейке h2(x) второй. Поиск проверяет обе ячейки — две пробы в худшем случае. Вставка кладёт ключ в свободную из двух; если обе заняты — выселяет жильца первой, жилец переезжает в своё место во второй таблице, оттуда выселяет следующего, и так, пока кто-то не найдёт пустую ячейку. Если цепочка слишком длинная, таблицу перестраивают с новыми хеш-функциями.
Граф кукушки
Нарисуем ячейки вершинами, а каждый ключ — ребром между двумя его ячейками. Получится граф кукушки — это линии в сцене. Разложить ключи по ячейкам — значит каждое ребро отдать одному из его концов, и так, чтобы у каждой вершины было не больше одного ребра. Когда это возможно?
Ключи можно разложить по ячейкам, по одному в ячейку, тогда и только тогда, когда в каждом связном куске графа кукушки рёбер не больше, чем вершин.
Если в куске рёбер больше, чем вершин, ключам этого куска не хватит ячеек: каждый живёт в одной из ячеек своего куска, а в ячейке один ключ.
Пусть в связном куске V вершин и E ≤ V рёбер. Связному графу нужно хотя бы V − 1 ребро, поэтому E = V − 1 или E = V. В первом случае кусок — дерево. Подвесим его за любую вершину и отдадим каждое ребро нижнему концу: у каждой вершины, кроме корня, ровно одно ребро — к родителю. Во втором случае кусок — дерево и ещё одно ребро, то есть в нём ровно один цикл. Отдадим рёбра цикла по кругу, каждое следующей вершине, а деревья, которые висят на цикле, подвесим за их вершины на цикле и раздадим, как в первом случае. Каждая вершина снова получает не больше одного ребра.
Вставка с вытеснениями ищет такую раскладку на ходу: цепочка вытеснений — это путь по рёбрам графа. В дереве или куске с одним циклом она находит свободную вершину. В куске, где рёбер больше, чем вершин, свободной вершины нет, и цепочка ходит по кругу, пока её не остановят.
В сцене это видно по точкам на линиях. Точка стоит у того конца, где название живёт, и у каждого гнезда не больше одной точки. Пока в куске линий не больше, чем гнёзд, точки удаётся расставить; когда линий становится больше, кусок краснеет, и у одной из линий точки нет — это название осталось без гнезда.
Когда цепочка не кончается
Как вставке понять, что пора сдаваться? Ждать, пока цепочка вернётся к началу, мало: и в куске, где место есть, она может обойти цикл — пройти его, вернуться к новому ключу, выселить его во второе гнездо и уже оттуда уйти по другой ветке к свободной вершине. Бесконечна она только в переполненном куске, где свободной вершины нет. На практике цепочку обрывают на заранее выбранном числе вытеснений: в работе Пагха и Родлера оно растёт как логарифм размера таблицы, в листинге ниже это 500.
Оборванная вставка оставляет одного жильца без места, и есть два выхода. Первый — перестроить таблицу с новыми хеш-функциями: новый граф кукушки, скорее всего, уже без переполненных кусков. Ниже порога это случается так редко, что в среднем почти ничего не стоит. Второй — заначка: маленький отдельный список на несколько ключей, которые не нашли места. Поиск заглядывает и в неё, а Адам Кирш, Майкл Митценмахер и Уди Видер в 2008 году показали, что для обычной кукушки с двумя таблицами заначка на s ключей уменьшает вероятность перестройки примерно с 1/n до 1/ns+1. Трёх-четырёх мест в заначке хватает, чтобы перестройка практически не случалась.
Худший случай поиска при этом остаётся постоянным: две ячейки и заначка из нескольких ключей. Обе ячейки можно читать из памяти одновременно: адрес второй не зависит от содержимого первой, процессор не ждёт одну, чтобы начать другую, и два чтения обходятся почти как одно.
Ровно половина
Когда же в графе появляются переполненные куски? У двух таблиц по r ячеек граф кукушки похож на случайный граф с 2r вершинами и n рёбрами. В случайных графах есть знаменитый порог, открытый Палом Эрдёшем и Альфредом Реньи в 1960 году: пока рёбер меньше половины вершин, все куски маленькие, и почти все — деревья, изредка с одним циклом; стоит рёбрам перевалить за половину вершин, появляется гигантский кусок, где циклов много и рёбер больше, чем вершин. Для кукушки «рёбер меньше половины вершин» — это заполнение n / 2r меньше 1/2.
Ниже порога вставка в среднем стоит O(1): Расмус Пагх и Флемминг Фрише Родлер, придумавшие этот способ в 2001 году, доказали, что ожидаемая длина цепочки ограничена константой, а перестройка нужна редко. Выше порога таблица ломается почти наверняка. Сцена показывает этот обрыв для таблиц на 4096 ячеек. У двух таблиц с одиночными ячейками он размазан — примерно от 40 до 57 %: таблица маленькая, и случайность в её графе заметна. У трёх таблиц и у корзин доля таблиц, куда помещается всё, падает с единицы до нуля за два-три процента заполнения.
Половина таблицы пустует — это дорого. Порог поднимают двумя способами, и оба видны в сцене. Три хеш-функции и три таблицы дают ключу три гнезда, и порог поднимается примерно до 0,918. Корзины по четыре ключа вместо одиночных ячеек, при двух хеш-функциях, — примерно до 0,98. Поиск по-прежнему смотрит в постоянное число мест: в три ячейки или в две корзины по четыре — восемь ячеек, которые лежат в памяти рядом.
Код
Листинг кладёт названия городов GeoNames — 42 311 различных — в таблицы кукушки трёх видов на 32 768 ячеек, пока очередное название не перестанет помещаться. Вытесняемый жилец выбирается случайно; после 500 вытеснений подряд вставка сдаётся. Хеш-функции — FNV-1a и перемешивание из splitmix64 с разными константами для разных таблиц. В конце программа проверяет, что каждое вставленное название находится, кроме одного, оставшегося без места.
42311 distinct names, 32768 slots, up to 500 evictions per insert tables x slots per bucket stored load kicks per key 2 x 1 16467 0.503 0.29 3 x 1 29504 0.900 1.95 2 x 4 31703 0.967 1.64
Две таблицы с одиночными ячейками ломаются на заполнении 0,503 — ровно у порога. Три таблицы доходят до 0,900, корзины по четыре — до 0,967; до теоретических 0,918 и 0,98 не хватает, потому что таблица конечная и цепочка обрывается на 500 вытеснениях. Вытеснений на ключ в среднем меньше двух даже у самого края.
Сколько это стоит
| Вид | Поиск, проб в худшем | Порог заполнения | На названиях городов |
|---|---|---|---|
| 2 таблицы, по 1 ключу | 2 | 1/2 | 0,503 |
| 3 таблицы, по 1 ключу | 3 | ≈ 0,918 | 0,900 |
| 2 таблицы, корзины по 4 | 2 корзины, 8 ячеек | ≈ 0,98 | 0,967 |
Сравните с обычной таблицей. Линейное пробирование при заполнении 90 % тратит на неудачный поиск в среднем около 50 проб, а цепочки — в среднем меньше двух, но без гарантии сверху. Кукушка с корзинами по четыре при 95 % никогда не смотрит больше чем в восемь ячеек двух корзин.
Вставка ниже порога — O(1) в среднем; удаление — просто убрать ключ из его ячейки, никаких надгробий, как в открытой адресации. Цена — вероятность неудачи: изредка вставка зацикливается, и всю таблицу перестраивают с новыми хеш-функциями за O(n). Поэтому кукушку выбирают, когда важен худший случай поиска, а не вставки: в сетевом оборудовании и обработке пакетов поиск идёт на каждый пакет, а вставки редки.
Где работает
- Обработка пакетов. Хеш-библиотека DPDK, на которой строят программные маршрутизаторы и балансировщики, по документации разрешает коллизии алгоритмом кукушки: у ключа основная и запасная корзины, и если в основной нет места, один из жильцов переезжает в свою запасную.
- Кэши. MemC3, вариант memcached 2013 года, заменил цепочки на кукушку с корзинами и оптимистичными блокировками: читатели не ждут писателя.
- Фильтры. Кукушкин фильтр 2014 года хранит вместо ключей короткие отпечатки в корзинах по четыре. Вторую корзину он вычисляет из первой и отпечатка — так переезд возможен без самого ключа. В отличие от фильтра Блума, он умеет удалять, а при малой доле ложных срабатываний ещё и экономнее.
- Два выбора. Идея «у каждого ключа два места» — та же, что у силы двух выборов, только там ключи не перекладывают, а здесь перекладывают.
История
Расмус Пагх и Флемминг Фрише Родлер представили хеширование кукушки в 2001 году на симпозиуме по алгоритмам ESA и назвали его по птице, которая подкладывает яйцо в чужое гнездо, а птенец выталкивает хозяйских. Они искали словарь с поиском за постоянное время в худшем случае, который был бы проще динамического совершенного хеширования и не тратил больше памяти, чем дерево поиска. Через девятнадцать лет работа получила премию ESA «испытание временем». Пороги для трёх и более хеш-функций и для корзин точно вычислили позже, в 2009–2010 годах, сразу несколько групп.
Задачи
В задаче нужно найти, сколько ключей помещается в таблицу одновременно, если раскладывать их как угодно, — прямое следствие теоремы о кусках графа. На названиях городов ответ показывает, что значит «выше порога».
Гнёзда кукушкиДанные: Населённые пункты: GeoNames, CC BY 4.0