Что такое хэш в программировании
Перейти к содержимому

Что такое хэш в программировании

  • автор:

Хэш-функция

Хэш-функция — функция, осуществляющая хэширование массива данных посредством отображения значений из (очень) большого множества-значений в (существенно) меньшее множество-значений.

По-английски: Hash-function

См. также: Криптографические алгоритмы

Финансовый словарь Финам .

  • Хэширование
  • Царгасов Марат (Феликсович)

Смотреть что такое «Хэш-функция» в других словарях:

  • Хэш-функция — Хеширование (иногда хэширование, англ. hashing) преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш функциями или функциями свёртки, а их результаты… … Википедия
  • криптографическая хэш-функция — Функция, преобразующая текст произвольной длины в текст фиксированной (в большинстве случаев меньшей) длины. Основное применение хэш функции нашли в схеме цифровой подписи. Так как хэш функция вычисляется быстрее цифровой подписи, то вместо… … Справочник технического переводчика
  • Односторонняя хэш-функция — хэш функция, являющаяся вычислительно необратимой функцией. По английски: One way hash function См. также: Криптографические алгоритмы Финансовый словарь Финам … Финансовый словарь
  • TIGER — хэш-функция — TIGER хэш функция, разработанная Росом Андерсоном и Эли Бихамом в 1996 году. Хэш функция TIGER является новой быстрой хэш функцией, которая призвана быть очень быстрой на современных компьютерах, в частности, на 64 разрядных компьютерах. TIGER… … Википедия
  • односторонняя хэш-функция — Для односторонней функции вычислительно невозможно найти два разных аргумента, для которых ее значения совпадают. [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN one way hash function … Справочник технического переводчика
  • Tiger (хэш-функция) — Tiger хеш функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64 разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с… … Википедия
  • функция хэширования — хэшфункция 1. Функция, которая управляет процессом занесения данных в хэш таблицу, определяя (адреса свободных ячеек. 2. Функция, представляющая собой отображение фрагмента открытого сообщения в шифрованную строку фиксированной длины. В… … Справочник технического переводчика
  • Хэш-таблица — В программировании хеш таблица это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления … Википедия
  • Хэш код — Хеширование (иногда хэширование, англ. hashing) преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш функциями или функциями свёртки, а их результаты… … Википедия
  • Коллизия хэш-функции — Коллизией хеш функции H называется два различных входных блока данных x и y таких, что H(x) = H(y). Коллизии существуют для большинства хеш функций, но для «хороших» хеш функций частота их возникновения близка к теоретическому минимуму. В… … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,

WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Поделиться ссылкой на выделенное

Прямая ссылка:

Нажмите правой клавишей мыши и выберите «Копировать ссылку»

Хеширование

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

«IT-специалист с нуля» наш лучший курс для старта в IT

Что такое хеш

устройство хеширования

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

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

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

vsrat_7 1 (1)

Кто работает с хешированием

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

Читайте также Кто такой «белый» хакер: чем занимается и сколько зарабатывает

Для чего нужно хеширование

Основное назначение хеширования — проверка информации. Эта задача важна в огромном количестве случаев: от проверки паролей на сайте до сложных вычислений в блокчейне. Так как хеш — это уникальный код определенного набора данных, по нему можно понять, соответствует ли информация ожидаемой. Поэтому программа может хранить хеши вместо образца данных для сравнения. Это может быть нужно для защиты чувствительных сведений или экономии места.

Вот несколько примеров:

  • вместо паролей на сервере хранятся хеши паролей;
  • антивирус хранит в базе хеши вирусов, а не образцы самих программ;
  • электронная подпись использует хеш для верификации;
  • информация о транзакциях криптовалюты хранится в виде кешей;
  • коммиты в Git идентифицируются по хешу (подробнее про Git и коммиты можно прочесть в нашей статье).

Среди других, менее распространенных примеров использования — поиск дубликатов в больших массивах информации, генерация ID и построение особых структур данных. Это, например, хеш-таблицы — в них идентификатором элемента является его хеш, и он же определяет расположение элемента в таблице.

пример хеш-таблицы

Как работает хеш-функция

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

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

А вот хеш-функции для более простых случаев, например построения таблиц, не обязаны быть криптографическими. Там преобразования могут быть проще.

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Свойства криптографических хеш-функций

Необратимость. Из хеша нельзя получить исходные данные даже теоретически. Слишком много информации отбрасывается в процессе; это не зашифровка информации.

Детерминированность. Если подать хеш-функции одинаковые данные, то и хеш у них будет одинаковым. Именно это свойство позволяет использовать хеши для проверки подлинности информации.

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

Разнообразие. Даже если два набора информации различаются одним-двумя символами, их хеши будут кардинально разными. У них не будет общих блоков, по ним невозможно будет понять, что исходные данные схожи.

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

Профессия / 13 месяцев
«Белый» хакер

Взламывайте ПО безнаказанно и за оплату

cables_2 2-PhotoRoom 1 (2)

Безопасность криптографической хеш-функции

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

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

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

Современные криптографические хеш-функции не полностью устойчивы к коллизиям. Но так как они очень сложные, для поиска коллизии нужно огромное количество вычислений и много времени — годы или даже столетия. Задача такого поиска становится практически невыполнимой.

Стойкость к восстановлению данных. Частично это означает все ту же необратимость, о которой мы писали выше. Но восстановить данные в теории можно не только с помощью обратной функции — еще есть метод подбора. Стойкость к восстановлению данных подразумевает, что, даже если злоумышленник будет очень долго подбирать возможные комбинации, он никогда не сможет получить исходный массив информации.

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

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

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

1 и 2 прообраз и коллизия хеш-функций

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

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

Обеспечение целостности данных с помощью хэш-кодов

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

В этом разделе описываются способы создания и проверки хэш-кодов с помощью классов пространства имен System.Security.Cryptography.

Создание хэша

Хэш-классы могут хэш-классы хэширования массива байтов или объекта потока. В следующем примере используется хэш-алгоритм SHA-256 для создания хэш-значения для строки. В примере используется Encoding.UTF8 для преобразования строки в массив байтов, хэшированных с помощью SHA256 класса . После этого хэш-код выводится на консоль.

using System; using System.IO; using System.Security.Cryptography; using System.Text; string messageString = "This is the original message!"; //Convert the string into an array of bytes. byte[] messageBytes = Encoding.UTF8.GetBytes(messageString); //Create the hash value from the array of bytes. byte[] hashValue = SHA256.HashData(messageBytes); //Display the hash value to the console. Console.WriteLine(Convert.ToHexString(hashValue)); 
Imports System.Security.Cryptography Imports System.Text Module Program Sub Main() Dim messageString As String = "This is the original message!" 'Convert the string into an array of bytes. Dim messageBytes As Byte() = Encoding.UTF8.GetBytes(messageString) 'Create the hash value from the array of bytes. Dim hashValue As Byte() = SHA256.HashData(messageBytes) 'Display the hash value to the console. Console.WriteLine(Convert.ToHexString(hashValue)) End Sub End Module 

Этот код выводит на консоль следующую строку:

67A1790DCA55B8803AD024EE28F616A284DF5DD7B8BA5F68B4B252A5E925AF79 

Проверка хэша

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

В примере ниже ранее полученный хэш-код строки сравнивается с ее новым хэш-кодом.

using System; using System.Linq; using System.Security.Cryptography; using System.Text; //This hash value is produced from "This is the original message!" //using SHA256. byte[] sentHashValue = Convert.FromHexString("67A1790DCA55B8803AD024EE28F616A284DF5DD7B8BA5F68B4B252A5E925AF79"); //This is the string that corresponds to the previous hash value. string messageString = "This is the original message!"; //Convert the string into an array of bytes. byte[] messageBytes = Encoding.UTF8.GetBytes(messageString); //Create the hash value from the array of bytes. byte[] compareHashValue = SHA256.HashData(messageBytes); //Compare the values of the two byte arrays. bool same = sentHashValue.SequenceEqual(compareHashValue); //Display whether or not the hash values are the same. if (same) < Console.WriteLine("The hash codes match."); >else
Imports System.Linq Imports System.Security.Cryptography Imports System.Text Module Module1 Sub Main() 'This hash value is produced from "This is the original message!" 'using SHA256. Dim sentHashValue As Byte() = Convert.FromHexString("67A1790DCA55B8803AD024EE28F616A284DF5DD7B8BA5F68B4B252A5E925AF79") 'This is the string that corresponds to the previous hash value. Dim messageString As String = "This is the original message!" 'Convert the string into an array of bytes. Dim messageBytes As Byte() = Encoding.UTF8.GetBytes(messageString) 'Create the hash value from the array of bytes. Dim compareHashValue As Byte() = SHA256.HashData(messageBytes) 'Compare the values of the two byte arrays. Dim same As Boolean = sentHashValue.SequenceEqual(compareHashValue) 'Display whether or not the hash values are the same. If same Then Console.WriteLine("The hash codes match.") Else Console.WriteLine("The hash codes do not match.") End If End Sub End Module 

См. также раздел

  • Модель криптографии
  • службы шифрования
  • Кроссплатформенное шифрование
  • Защита данных ASP.NET Core

Совместная работа с нами на GitHub

Источник этого содержимого можно найти на GitHub, где также можно создавать и просматривать проблемы и запросы на вытягивание. Дополнительные сведения см. в нашем руководстве для участников.

Хэширование в строковых задачах

Хэш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

  • Быстро считается — за линейное от размера объекта время;
  • Имеет не очень большие значения — влезающие в 64 бита;
  • «Детерминированно-случайная» — если хэш может принимать \(n\) различных значений, то вероятность того, что хэши от двух случайных объектов совпадут, равна примерно \(\frac\) .

Обычно хэш-функция не является взаимно однозначной: одному хэшу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны \(n\) строк длины \(m\) , и нас просят \(q\) раз проверять произвольные две на равенство. Вместо наивной проверки за \(O(q \cdot n \cdot m)\) , мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

  • Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
  • Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём \(n\) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию \(f\) с областью значений \([0, n)\) . При обработке .insert(x) мы будем добавлять элемент \(x\) в \(f(x)\) -тый список. При ответе на .find(x) мы будем проверять, лежит ли \(x\) -тый элемент в \(f(x)\) -том списке. Благодаря «равномерности» хэш-функции, после \(k\) добавлений ожидаемое количество сравнений будет равно \(\frac\) = \(O(1)\) при правильном выборе \(n\) .
  • Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
  • Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
  • Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
  • Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди \(m\) точек в \(n\) -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

Хэшируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

Сегодня же мы остановимся на строках.

Полиномиальное хэширование

Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хэшами.

Будем считать, что строка — это последовательность чисел от \(1\) до \(m\) (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c — ‘a’ + 1) .

Определим прямой полиномиальный хэш строки как значение следующего многочлена:

\[ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \mod p \]

Здесь \(k\) — произвольное число больше размера алфавита, а \(p\) — достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время, поддерживая переменную, равную нужной в данный момент степени \(k\) :

 const int k = 31, mod = 1e9+7; string s = "abacabadaba"; long long h = 0, m = 1; for (char c : s)  int x = (int) (c - 'a' + 1); h = (h + m * x) % mod; m = (m * k) % mod; >

Можем ещё определить обратный полиномиальный хэш:

\[ h_b = (s_0 k^n + s_1 k^ + \ldots + s_n) \mod p \]

Его преимущество в том, что можно написать на одну строчку кода меньше:

 long long h = 0; for (char c : s)  int x = (int) (c - 'a' + 1); h = (h * k + x) % mod; >

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хэш и обозначать его просто буквой \(h\) .

Зачем это нужно?

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

Например, если нужно посчитать хэш от конкатенации строк \(a\) и \(b\) (т. е. \(b\) приписали в конец строки \(a\) ), то можно просто хэш \(b\) домножить на \(k^<|a|>\) и сложить с хэшом \(a\) :

Удалить префикс строки можно так:

А суффикс — ещё проще:

В задачах нам часто понадобится домножать \(k\) в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

 const int maxn = 1e5+5; int p[maxn]; p[0] = 1; for (int i = 1; i  maxn; i++) p[i] = (p[i-1] * k) % mod;

Как это использовать в реальных задачах? Пусть нам надо отвечать на запросы проверки на равенство произвольных подстрок одной большой строки. Подсчитаем значение хэш-функции для каждого префикса:

 int h[maxn]; h[0] = 0; // h[k] -- хэш префикса длины k // будем считать, что s это уже последовательность int-ов for (int i = 0; i  n; i++)  h[i+1] = (h[i] + p[i] * s[i]) % mod;

Теперь с помощью этих префиксных хэшей мы можем определить функцию, которая будет считать хэш на произвольном подотрезке:

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хэш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к \(n\) -ной. Так проще — нужно будет домножать, а не делить.

 int hash_substring (int l, int r)  return (h[r+1] - h[l]) * p[n-l] % mod; >

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за \(O(1)\) .

Упражнение. Напишите то же самое, но используя обратный полиномиальный хэш — этот способ тоже имеет право на существование, и местами он даже проще. Обратный хэш подстроки принято считать и использовать в стандартном виде из определения, поскольку там нет необходимости в делении.

Лайфхак. Если взять обратный полиномиальный хэш короткой строки на небольшом алфавите с \(k=10\) , то числовое значение хэша строки будет наглядно соотноситься с самой строкой:

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хэши от всех подстрок за \(O(n^2)\) и добавим их все в std::set . Чтобы получить ответ, просто вызовем set.size() .

Поиск подстроки в строке. Можно посчитать хэши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хэш текущей подстроки. Если хэш какой-то из этих подстрок совпал с хэшом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение строк (больше-меньше, а не только равенство). У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше сравним два символа, идущие за ним.

Палиндромность подстроки. Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно.

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

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

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

У алгоритмов, использующих хэширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хэширование — можно в оффлайне сгенерировать тест против конкретного решения.

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set \(O(n^2)\) различных случайных значений в промежутке \([0, m)\) . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать \(m\) , чтобы не бояться такого?

Выбор констант

Практическое правило: если вам нужно хранить \(n\) различных хэшей, то безопасный модуль — это число порядка \(10 \cdot n^2\) . Обоснование — см. парадокс дней рождений.

Не всегда такой можно выбрать один — если он будет слишком большой, будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хэшей параллельно.

Можно также брать модуль \(2^\) . У него есть несколько преимуществ:

  • Он большой — второй модуль точно не понадобится.
  • С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long , процессор сам автоматически сделает эти взятия остатков при переполнении.
  • С ним хэширование будет быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию % .

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако, его добавляют далеко не на все контесты — имейте это в виду.

В выборе же \(k\) ограничения не такие серьезные:

  • Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
  • Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения \(k\) и модуля не знал человек, который генерирует тесты.

Парадокс дней рождений

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить \(\Theta(\sqrt)\) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть \(f(n, d)\) это вероятность того, что в группе из \(n\) человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от \(1\) до \(d\) .

\[ f(n, d) = (1-\frac) \times (1-\frac) \times . \times (1-\frac) \]

Попытаемся оценить \(f\) :

Из последнего выражения более-менее понятно, что вероятность \(\frac\) достигается при \(n \approx \sqrt\) и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем \(\frac\) индикаторов — по одному для каждой пары людей \((i, j)\) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна \(\frac\) .

Обозначим за \(X\) число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть \(\frac \cdot \frac\) .

Отсюда понятно, что если \(d = \Theta(n^2)\) , то ожидание равно константе, а если \(d\) асимптотически больше или меньше, то \(X\) стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *