Информатика · объяснение и практика
Почему совпадение хешей не доказывает равенства объектов
Различаем хеш и полное равенство, объясняем коллизии на простой функции и проверяем требования Python к ключам словаря без обещаний уникальности хеша.

В теме Безопасность и надёжность данных · Учебная карта
Главная мысль
Одинаковые хеши не доказывают равенства объектов. Хеш-таблица использует хеш для поиска кандидатов, а затем проверяет равенство. Для корректных хешируемых объектов равенство требует одинакового хеша, но обратное неверно.
Как разные значения получают один короткий результат
Рассмотрим учебную функцию h(n) = остаток от деления n на 10. Числа 12 и 22 дают один результат 2, хотя сами не равны. Это коллизия. Из одного остатка нельзя восстановить исходное число: информация о десятках потеряна. Функция слишком проста для реальных словарей, но ясно показывает логику неуникального отображения.
Если пространство возможных входов больше конечного пространства хешей, какие-то входы неизбежно совпадут по хешу. Поэтому увеличение длины хеша уменьшает вероятность случайного совпадения в заданной модели, но не превращает отображение в доказательство равенства всех возможных входов. Проверка только h(a) == h(b) отвечает более слабому вопросу, чем a == b.
Что делает словарь при столкновении
Словарь использует хеш, чтобы не сравнивать ключ с каждым элементом подряд. Если несколько ключей попали в одну область поиска, реализация разрешает коллизию и проверяет фактическое равенство ключей. Разные строки с одинаковым хешем не должны автоматически перезаписывать друг друга только по этому совпадению. Хеш — ускоряющий признак, а не сам ключ по смыслу.
При определении собственного класса методы равенства и хеша должны быть согласованы: равные объекты обязаны иметь равный хеш. Хеш ключа не должен меняться во время его использования в таблице. Именно поэтому обычные изменяемые списки не подходят как ключи Python: изменение содержимого сделало бы поиск по старому расположению ненадёжным, если бы хеш зависел от него.
Пример
Учебный h(s) равен длине строки. Совпадение h(«кот») и h(«дом») доказывает равенство строк?
Нет. Оба хеша равны 3, но строки различаются. Нужно сравнить содержимое или использовать корректный механизм словаря, который делает такую проверку.
Почему встроенный hash не заменяет проверку файла
Встроенный hash Python предназначен для работы контейнеров, а не для долговременной криптографической проверки. Для некоторых типов, включая строки, значение может различаться между процессами из-за рандомизации. Поэтому сохранённый hash текста нельзя автоматически использовать как стабильный идентификатор файла между запусками.
Криптографические хеши имеют другие цели и свойства, но даже их совпадение является практическим свидетельством в принятой модели, а не математическим отсутствием коллизий для любых входов. Для задач безопасности нужно выбрать подходящий алгоритм и источник доверенного эталона. Для словаря достаточно соблюдать контракт равенства и хеширования. Смешение этих двух задач приводит либо к лишней сложности контейнера, либо к необоснованному обещанию защищённости данных.
От чтения к действию
А теперь — вы
Частые вопросы
Если объекты равны, их хеши должны совпадать?
Для корректных хешируемых объектов Python — да. Но совпадение хешей не гарантирует равенство.
Встроенный hash строки гарантированно одинаков между запусками?
Нет. На него нельзя полагаться как на стабильную криптографическую контрольную сумму.
Углублённый разбор
Минимальный хеш оценивает сходство Жаккара
Совпадение минимальных меток множества не доказывает равенство множеств. При общей случайной перестановке оно имеет точную вероятность, равную сходству Жаккара. Повторение независимых перестановок превращает это событие в несмещённую оценку пересечения относительно объединения.
Перед началом: Равномерная перестановка; Дисперсия индикатора.
Одна общая перестановка сравнивает два непустых множества
Пусть A,B — непустые подмножества конечной вселенной U. Выберем равномерную случайную перестановку U и определим minhash(A) как первый элемент A в этом порядке. Для B используется та же перестановка. Вероятность совпадения минимумов равна J(A,B)=|A∩B|/|A∪B|. Это свойство случайного порядка, а не обычная вероятность коллизии конечного хеша.
Доказательство: первый элемент A∪B равновероятно оказывается любым из его участников. Минимумы совпадут ровно тогда, когда этот первый элемент лежит в A∩B. Если он находится только в одном множестве, другое получит более поздний и потому другой минимум. Следовательно благоприятных первых элементов |A∩B| из общего числа |A∪B|. Элементы вселенной вне объединения не влияют на событие.
Доля совпадений имеет измеримую случайную ошибку
Для r независимых перестановок возьмём индикаторы совпадения I₁,…,I_r и оценку J_hat=ΣI/r. Её ожидание равно J, дисперсия J(1−J)/r. Независимость важна: использование одной перестановки r раз сохраняет то же единственное наблюдение и не уменьшает дисперсию в r раз. Реальная хеш-семья, лишь приближающая случайные перестановки, требует отдельного анализа смещения и одинаковых значений.
Одна равная координата совместима с различными множествами; одна неравная не означает нулевое пересечение. При большом числе проб доля приближается к J, но конечное наблюдение не является точным удостоверением сходства. Для маленькой вселенной можно независимо перебрать все перестановки и получить точную вероятность без статистического доверительного интервала.
Модель множеств забывает кратности
Повторное добавление уже присутствующего элемента не меняет A, минимум и J. Поэтому MinHash в этой форме не измеряет частотное сходство мультимножеств и не заменяет счётчики. Для пустых множеств минимум не определён; соглашения J(∅,∅)=1 или J(∅,B)=0 нужно обрабатывать отдельно. В работоспособном сравнении также нельзя независимо перенумеровать элементы двух документов: общая вселенная идентификаторов является частью модели.
Половина всех порядков даёт общий минимум
Условие. Возьмите A={a,b,d}, B={b,c,d}, U={a,b,c,d}. Найдите точную вероятность равенства MinHash и дисперсию оценки по16 независимым перестановкам.
- Пересечение равно{b,d}, объединение всей U. Сходство Жаккара J=2/4=1/2.
- Всего 4!=24 перестановки. Для каждого фиксированного первого элемента оставшиеся три можно расположить 3!=6 способами. Благоприятны первые b и d, значит совпадений 12.
- Точная вероятность равна 12/24=1/2. Например, порядок b,a,c,d даёт общий b, а порядок a,b,c,d даёт минимумы a и b и не совпадает.
- Каждый индикатор имеет дисперсию(1/2)(1−1/2)=1/4. Для среднего 16 независимых индикаторов дисперсия равна 1/64, стандартное отклонение 1/8.
Ответ. Вероятность 1/2; для 16 независимых проб дисперсия 1/64 и стандартное отклонение 1/8.
Проверка. Полный независимый перебор 24 порядков находит 12 совпадений. Точные дроби подтверждают ожидание и дисперсию индикатора; повторение одного порядка отдельно показывает отсутствие выигрыша от зависимых копий.
Где легко ошибиться. Не считайте один общий минимум доказательством равенства множеств и не называйте повторение одного хеша независимыми пробами. Общая случайная перестановка требуется внутри пары, независимость — между пробами.
Проверьте понимание
Вопросы к этой главе
Почему разные перестановки для A и B неправильны?
Тогда первый элемент объединения больше не связывает два минимума. Событие сравнивает разные случайные порядки и не имеет доказанной вероятности Жаккара. Одна и та же координата подписи должна использовать одну общую перестановку.
Может ли MinHash оценить количество элементов пересечения напрямую?
Он оценивает отношение |A∩B|/|A∪B|. Для абсолютного количества нужна ещё информация о размере объединения либо дополнительные данные. Одного совпадения минимумов недостаточно для восстановления обоих размеров.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Rashmi Vinayak: CMU15-853 Lecture22, §22.1
Прочитаны равенство вероятности minhash и сходства Жаккара, независимые перестановки и оценка долей совпавших координат. Доказательство через первый элемент объединения и все 24 перестановки четырёхэлементного примера изложены самостоятельно; LSHbanding из дальнейших разделов не применяется.
Кукку-хеширование и условие размещения в псевдолесе
При двух вариантах ячейки для каждого ключа свободные места в другой части таблицы могут оказаться бесполезны. Статическое размещение определяется компонентами графа выбора. Докажем критерий псевдолеса и отделим существование размещения от поведения конкретного алгоритма вытеснений.
Перед началом: Связная компонента, дерево и цикл графа; Различные ключи и вместимость одной ячейки.
Ячейки становятся вершинами, ключи — рёбрами
В двухтабличном cuckoo-хешировании ключ x может занимать либо ячейку h1(x) первой таблицы, либо h2(x) второй. Каждая физическая ячейка вмещает один ключ. Соединим два возможных места ребром, помеченным ключом. Получается двудольный мультиграф: разные ключи могут иметь одинаковую пару мест и тогда дают параллельные рёбра. Совпадающие номера в разных таблицах всё равно являются разными вершинами.
Размещение выбирает для каждого ребра один конец так, чтобы одна вершина не выбиралась дважды. Ключ не может выйти из своей связной компоненты. Поэтому для каждой компоненты с e рёбрами и v вершинами необходимо e≤v. Одного сравнения общего числа ключей с общим числом ячеек недостаточно: лишняя свободная компонента не исправляет локальную нехватку мест.
Почему условие также достаточно
Связная компонента с e≤v является деревом либо содержит ровно один цикл. В дереве можно назначить ребро листовой вершине, удалить лист с ребром и повторить. Каждое такое назначение использует отдельную ячейку и не мешает оставшимся рёбрам. В одноцикловой компоненте тем же способом сначала снимаются все ветви.
Оставшийся цикл размещается по кругу: каждому ребру назначается следующий по выбранному направлению конец. Все его вершины используются по одному разу. Два параллельных ребра образуют допустимый цикл длины 2: один ключ занимает первый конец, другой второй. Таким образом, каждая компонента должна быть псевдолесом, то есть иметь не более одного независимого цикла.
Свободная ячейка должна быть достижима для ключа
Пусть ключи имеют пары мест A1B1, A1B2, A2B1, A2B2. Это цикл на четырёх вершинах, и размещение существует: назначения A1, B2, B1, A2 соответственно различны. Добавим пятый ключ с той же парой A1B1. Теперь в компоненте пять рёбер и четыре вершины; разместить все ключи нельзя. Свободные A3, B3 вне компоненты не являются альтернативами ни одного из этих ключей.
Критерий описывает наличие хотя бы одного размещения при фиксированных хешах. Он не утверждает, что любой порядок вытеснений без ограничений и перехеширования обязательно найдёт его. Зацикливание конкретного поиска и доказанная нехватка мест — разные результаты диагностики. Если e>v, увеличение числа попыток с теми же двумя местами каждого ключа не устранит причину отказа.
Четыре ключа размещаются, пятый перегружает компоненту
Условие. Пары допустимых мест четырёх ключей: A1B1, A1B2, A2B1, A2B2. Затем добавляется новый ключ A1B1. В таблицах также свободны A3, B3. Проверьте размещение до и после добавления.
- Первые четыре ребра образуют связный цикл с e=v=4, поэтому удовлетворяют критерию.
- Назначаем четырём ключам места A1, B2, B1, A2. Все четыре ячейки различны и входят в допустимые пары.
- Пятый ключ создаёт пятое ребро той же компоненты. Необходимое условие 5≤4 нарушено.
- Ячейки A3, B3 изолированы от этих ключей. Общая вместимость 6 не помогает: внутри нужной компоненты доступны только 4 места.
Ответ. До добавления размещение есть; после — нет при данных хешах, несмотря на две свободные внешние ячейки.
Проверка. Перебор 16 назначений концов для четырёх рёбер находит допустимые варианты. Все 32 назначения для пяти рёбер имеют повтор выбранной ячейки.
Где легко ошибиться. Проверяйте вместимость каждой компоненты графа выбора, а не только общий коэффициент заполнения таблиц.
Проверьте понимание
Вопросы к этой главе
Запрещены ли любые циклы?
Нет. Один цикл в компоненте допускает размещение по кругу. Проблема возникает, когда независимых циклов становится больше одного и рёбер больше вершин.
Новые случайные хеши меняют вывод?
Они меняют граф возможных мест и потому могут убрать перегруженную компоненту. Доказательство невозможности относится к зафиксированному графу, а не к любым будущим хешам.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Rasmus Pagh: Cuckoo Hashing for Undergraduates, §3
Граф двух возможных мест и роль компонент при вытеснении. Критерий статического размещения через дерево или один цикл и пример локальной перегрузки здесь доказаны отдельно.
Линейное хеширование постепенно разделяет корзины без полного rehash
Во время постепенного роста одни корзины уже используют новый остаток, а другие ещё старый. Одного текущего числа корзин для адресации недостаточно. Разберём состояние с тремя корзинами между ёмкостями два и четыре и проверим, почему ключ шесть направляется во вторую корзину, хотя старый остаток равен нулю.
Перед началом: Остаток от деления; Коллизии и цепочки хеш-таблицы.
Пара m,s хранит незавершённую фазу расширения
Учебное линейное хеширование неотрицательных целых с цепочками переполнения. m — степень двойки, s — указатель очередной расщепляемой корзины, 0≤s<m.
На старте фазы имеются m исходных корзин. После s расщеплений существуют корзины с номерами 0,…,m+s−1. Вначале для ключа k вычисляют a=k mod m. Если a≥s, эта исходная корзина ещё не разделена и адрес равен a. Если a<s, используют уточнённый адрес k mod 2m.
Почему уточнённый адрес обязательно существует? Для уже разделённой корзины a<s остаток по 2m равен либо a, либо a+m. Во втором случае a+m<m+s. Для ещё не разделённого a≥s новая корзина a+m могла бы пока отсутствовать; именно поэтому переходить на новый модуль для всех ключей сразу нельзя.
Расщепляется указатель, а не обязательно место коллизии
Одна операция роста создаёт корзину m+s и перераспределяет только содержимое корзины s по модулю 2m. Ключи уходят либо обратно в s, либо в s+m. Затем s увеличивают на один. Когда s достигает m, фаза завершена: полагают m←2m и s←0. Число физических корзин при смене записи состояния не меняется.
Политика, вызывающая рост, задаётся отдельно: например, по общей загрузке. Если переполнилась другая корзина, текущая операция всё равно разделяет корзину указателя. До её очереди переполнение обслуживается цепочкой. Сам выбор порядка делает рост предсказуемым, но не означает, что любое столкновение исчезнет после ближайшего расщепления.
Проверяем инвариант каждого сохранённого ключа
После каждого шага все ключи должны находиться в корзине, которую возвращает правило адресации для новых m,s. Не затронутые корзины сохраняют корректность: для их ключей ветка правила не изменилась. Изменившаяся корзина и её новый партнёр проверяются тем же уточнённым остатком, который использован при переносе.
Расщепление одной корзины не обещает постоянной худшей задержки: в ней могла накопиться длинная цепочка. Оценки поиска требуют предположений о распределении хешей. Если ключи — строки, сначала получают согласованный целочисленный хеш, а равенство исходных ключей всё равно проверяют отдельно. Здесь остаток самого целого выбран только для прозрачности ручного примера.
Между двумя и четырьмя корзинами
Условие. Изначально m=2,s=0. В корзине 0 лежат ключи 0,2,4, в корзине 1 — 1,3. Выполните два расщепления и укажите адрес поиска ключа 6 между ними.
- Первым делится s=0. Создаётся корзина 2, а ключи 0,2,4 распределяются по модулю четыре: 0 и 4 остаются в 0, ключ 2 переходит в 2.
- Теперь m=2,s=1; физически существуют три корзины. Корзина 1 ещё не делилась и по-прежнему содержит 1,3.
- Для ключа 6 старый адрес 6 mod 2=0 меньше s. Поэтому уточняем: 6 mod 4=2. Поиск идёт в корзину 2, но это не утверждение о наличии там ещё не вставленного ключа 6.
- Следующим делится s=1. Новая корзина 3 получает ключ 3, а ключ 1 остаётся в 1. Указатель достигает двух, значит записываем новую фазу m=4,s=0.
- Итоговые корзины: 0:{0,4},1:{1},2:{2},3:{3}. Для каждого сохранённого ключа проверка k mod 4 даёт именно его текущую корзину.
Ответ. После первого шага m=2,s=1, адрес ключа 6 равен 2. После второго m=4,s=0; все пять исходных ключей сохранены.
Проверка. В каждом шаге число корзин увеличилось ровно на одну: 2→3→4. Каждый ключ перенесён только при расщеплении своей исходной корзины; полное повторное распределение остальных ключей не требовалось.
Где легко ошибиться. Не используйте k mod (m+s): это другое разбиение и оно переместило бы несвязанные корзины. Во время фазы нужны два согласованных модуля и указатель уже разделённого префикса.
Проверьте понимание
Вопросы к этой главе
Можно немедленно разделить ту корзину, где появилась коллизия?
Это уже другая политика адресации, если не хранить дополнительную информацию о произвольном наборе разделённых корзин. В описанной схеме один указатель работает благодаря фиксированному порядку 0,1,…,m−1.
Линейное здесь означает универсальный хеш ax+b?
Нет. В этой главе речь о постепенном изменении числа корзин и порядке расщеплений. Семейство хеш-функций и его вероятностные свойства — отдельный выбор; совпадение названий не переносит гарантий одной задачи в другую.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James K. Mullin: Unified Dynamic Hashing, Linear Hashing Instantiation
Прочитан раздел о последовательном физическом расщеплении и завершённом расширении. Двухмодульный учебный инвариант и обе стадии на ключах 0,…,4 выведены и проверены самостоятельно; показатели эффективности из экспериментов статьи здесь не переносятся.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Чем проверка случайной ошибки отличается от криптографической защиты
Отличаем обнаружение случайного повреждения от проверки подлинности, сохраняем доверенный эталон и проверяем, почему подмена файла вместе с его суммой может остаться незамеченной.
Открыть темуКак первичный ключ отличает запись от совпадающего имени
Выбираем устойчивый идентификатор записи, сохраняем разных людей с одинаковым именем и различаем ограничение ключа с порядком строк и показателем количества.
Открыть тему