Принцип Дирихле: гарантированные коллизии и искусство выбирать клетки
Разложите n+1 предметов по n ящикам — в каком-то окажется два. Принцип очевиден и силён тем, что ящики проектируете вы: месяцы, остатки mod n, корзины хеша. Таблица на 1000 корзин с 1001 ключом сталкивается по арифметике, а вероятной коллизия становится куда раньше.
Однажды джуниор завёл тикет с приоритетом P1: «Кеш сессий повреждён — два разных ID пользователей захешировались в одну корзину. Хеш-функция сломана». В кеше было 4096 корзин и около 100 000 живых сессий. Дежурный сеньор закрыл тикет двумя строками арифметики: если бы каждая корзина держала не больше 24 сессий, весь кеш вместил бы не больше 4096 · 24 = 98 304 — меньше его реальных 100 000. Значит, какая-то корзина держит не меньше 25 сессий — при любой хеш-функции, включая ещё не изобретённые. Присмотритесь к форме аргумента: ни симуляции, ни чтения кода хеша, ни вероятностей — вывод выжат чистым счётом. У этого аргумента есть имя, ему около четырёх веков, а та его часть, что требует настоящего мастерства, в этой истории невидима: кто-то должен был решить, что считать ящиком. Этот урок — сам принцип и ремесло проектирования ящиков.
- Формулировать принцип Дирихле и его однострочное доказательство от противного
- Проектировать ящики (остатки mod n, диапазоны, корзины хеша) под конкретную задачу
- Применять обобщённый принцип: n·k+1 предметов → k+1 в одном ящике
- Объяснять, почему хорошая хеш-функция не избегает коллизий, а размазывает их
Принцип Дирихле (в английской традиции — принцип голубиных гнёзд) гласит: разложите больше чем n предметов по n ящикам — и хотя бы в один ящик попадут хотя бы два. Доказательство — одна строка счёта: предположим, наоборот, что в каждом ящике не больше одного предмета; тогда n ящиков вмещают суммарно не больше n предметов, а мы разложили n + 1. Противоречие — честное, из доказательства от противного: допущение «ни в одном ящике нет двух» не переживает подсчёта.
Следите за тем, что принцип говорит, а что — нет. Он доказывает, что общий ящик существует; он никогда не скажет, какой это ящик и какие два предмета его делят. Существование без адреса — фирменный почерк принципа, и именно он позволил закрыть тикет из пролога, не читая кода.
Две классики, разобранные не спеша.
Первая: среди любых 13 человек двое родились в один месяц. Ящики — 12 месяцев, кролики — 13 человек; 13 в 12 клетках — общая клетка неизбежна.
Вторая, знаменитая: у двух москвичей в точности одинаковое число волос на голове. На голове человека не больше примерно 1 000 000 волос, так что ящики — количества волос от 0 до 1 000 000, около миллиона штук. В Москве больше 13 000 000 жителей. Людей больше, чем возможных ответов, в тринадцать раз — значит, какое-то количество совпало. Аргумент не разглядывает ни одной головы: размер населения бьёт размер пространства ответов, и этого достаточно.
В комнате 13 человек. Какое утверждение ВЫНУЖДЕНО быть истинным?
В формулировке принцип звучит слишком очевидно, чтобы быть полезным. Его сила — в степени свободы, которую формулировка прячет: что считать ящиком, решаете вы. Большинство доказательств через Дирихле отделяет от тривиальности ровно один удачный дизайн ящиков.
Рабочая лошадка — остатки. Поделите любое целое на n — остаток будет одним из ровно n значений: 0, 1, …, n−1. Эти n значений и есть ящики. Поэтому среди любых n + 1 целых найдутся два с одинаковым остатком от деления на n — а их разность тогда делится на n:
// Любые 4 целых: у двух одинаковый остаток mod 3.
// Три ящика (0, 1, 2) не вместят четыре числа по одному.
const xs = [7, 12, 22, 31];
xs.map(n => n % 3); // [1, 0, 1, 1] — 7, 22 и 31 попали в ящик 1
// 22 - 7 = 15 делится на 3, как и обещаноЯщиками работают и диапазоны. Возьмите любые 6 различных чисел от 1 до 10: какие-то два обязательно соседние. Спроектируйте ящики как пять пар — 2, 4, 6, 8, 10 — и 6 чисел в 5 ящиках-парах загоняют два числа в одну пару. Озарение никогда не в счёте; оно в том, чтобы увидеть, как «соседние» кодируется в «один ящик».
Принцип масштабируется. Разложите n · k + 1 предметов по n ящикам — и в каком-то окажется не меньше k + 1. Доказательство всё то же, в одну строку: будь в каждом ящике не больше k, всего набралось бы не больше n · k — на один меньше нужного.
Конкретно: 25 кроликов в 12 клетках (25 = 12 · 2 + 1) — в какой-то клетке трое. Арифметика из пролога — ровно эта форма: 100 000 сессий на 4096 корзин — раз 4096 · 24 = 98 304 меньше 100 000, какая-то корзина держит не меньше 25. Общий рецепт: поделите предметы на ящики и округлите вверх — это гарантированная заселённость самого полного ящика в худшем случае.
Хеш-функция отображает огромное пространство ключей — все возможные строки — в маленькое пространство корзин. Как только сохранённых ключей становится больше, чем корзин, принцип Дирихле срабатывает без каких-либо условий: в таблице с 1000 корзин и 1001 ключом коллизия есть. Не «вероятно». Не «из-за слабого хеша». По счёту.
На практике коллизии приходят задолго до того, как становятся гарантированными — это эффект парадокса дней рождения. При 1000 корзин шанс, что какие-то два столкнутся, переваливает за 50% уже примерно на 38 ключах: 38 ключей образуют 703 пары, каждая пара — независимый шанс примерно 1 к 1000.
Что хорошая хеш-функция делает на деле — распределяет ключи почти равномерно, чтобы неизбежные коллизии размазались ровно. Плохая — сбивает их в кучу. Единственный честный путь к нулю коллизий — совершенное хеширование над фиксированным известным множеством ключей: слотов не меньше, чем ключей — клеток больше, чем кроликов, принуждать нечего.
100 000 сессий на 4096 корзин → какая-то корзина держит ≥ 25 сессий.
Применяем обобщённый принцип Дирихле: n · k + 1 предметов в n ящиках → k+1 в каком-то.
- n = 4096 корзин
- Предметов = 100 000 сессий
Шаг 1: найдём максимальное k, при котором 4096 · k < 100 000.
4096 · 24 = 98 304 < 100 000 — значит, при k = 24 «места хватает»… нет: 98 304 < 100 000, то есть предметов больше.
Шаг 2: поэтому какая-то корзина держит не менее ⌈100 000 / 4096⌉ = 25 сессий.
Вывод: при любой хеш-функции (включая идеальные, несуществующие) хотя бы одна из 4096 корзин содержит ≥ 25 сессий. Тикет о «сломанной хеш-функции» закрыт двумя строками арифметики — без чтения кода хеша.
В хеш-таблице 1000 корзин, и в ней лежит 1001 ключ. Замечена коллизия. Что это говорит о хеш-функции?
Разложите больше чем n предметов по n ящикам — какой-то ящик получит два; разложите n·k+1 — какой-то получит k+1: оба факта доказываются строкой счёта, ведь n ящиков ёмкостью k вмещают лишь n·k. Принцип доказывает существование без адреса: среди 13 человек двое делят месяц рождения, но ни один конкретный месяц не назван; два москвича делят точное число волос, потому что тринадцать миллионов жителей превосходят миллион возможных значений — и ни одна голова не осмотрена. Ремесло живёт в проектировании ящиков, потому что сам счёт тривиален: остатки mod n дают n ящиков, и среди любых n+1 целых есть два, чья разность делится на n; дни календаря дают 366 ящиков, и 367 человек вынуждают общий день рождения; пары соседних чисел дают 5 ящиков для чисел от 1 до 10, и любые 6 содержат соседей. В инженерии ящики — корзины хеша: таблица на 1000 корзин с 1001 ключом сталкивается по арифметике — хеш-функция, сколь угодно сильная, выбирает лишь, какая корзина удвоится, — а по эффекту дней рождения коллизии вероятны уже близ 38 случайных ключей, ибо пары растут квадратично. Поэтому хорошая хеш-функция не избегает коллизий — она размазывает их равномерно, а цепочки и ресайз существуют потому, что коллизии — принятая арифметика, не невезение.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.