Хеширование

Содержание:

Введение

Существуют два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив H{\displaystyle H}, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение i=hash(key){\displaystyle i={\mbox{hash}}(key)} играет роль индекса в массиве H{\displaystyle H}. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту,
который хранится в соответствующей ячейке массива Hi{\displaystyle H}.

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

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

Число хранимых элементов, делённое на размер массива H{\displaystyle H} (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.

Введение

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

Плюсы и минусы алгоритма[править]

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

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

Обзор Мутцемахера представляет открытые проблемы, связанные с кукушкиным хешированием.

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

Закрытое хеширование.

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

Сам процесс заполнения хеш-таблицы с использованием алгоритма закрытого хеширования осуществляется следующим образом:

имеется изначально пустая хеш-таблица T размера M, массив A размера N (M≥N) и хеш-функция h(), пригодная для обработки ключей массива A;
элемент x_i, ключ которого key_i, помещается в одну из ячеек хеш-таблицы, руководствуясь следующим правилом:

a) если h(key_i) – номер свободной ячейки таблицы T, то в последнюю записывается x_i;

b) если h(key_i) – номер уже занятой ячейки таблицы T, то на занятость проверяется другая ячейка, если она свободна то x_i заноситься в нее, иначе вновь проверяется другая ячейка, и так до тех пор, пока не найдется свободная или окажется, что все M ячеек таблицы заполнены.

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

Рассмотрим метод закрытого хеширования на примере построения хеш-таблицы. Положим, имеется целочисленный массив A, состоящий из 9 элементов:

{A=data, здесь key – ключ, data – некоторые данные}

A=8, A=4, A=1, A=5, A=2, A=9, A=3, A=9, A=1

Также есть хеш-таблица размера M=10, и хеш-функция h(key)=key% M (% – операция «остаток от деления»). Заполним хеш-таблицу элементами массив A:Для расстановки элементов использовалась выбранная формула. Подставив ключ, например первого элемента в нее получим: h(13) = 13 % 10 = 3, поэтому его номер в хеш-таблице 3. Последовательное добавление элементов приведет к возникновению коллизии при обработке элемента A. Хеш-код его ключа 6, но в хеш-таблице ячейка с таким номером уже занята.

Используя формулу линейного пробирования (тип последовательности проб) h_i(key)=(h(key) + i) % M (i – число проверок, после первой проверки i=0), продолжим поиск свободной ячейки. Применим функцию при i=1: h₁(76)=7; убедившись, что ячейка 7 занята, продолжаем поиск, увеличив i на 1: h₂(76)=8. Ячейка 8 свободна, помещаем в нее элемент. Этот же метод используем и для всех остальных элементов.

Простое представление хеш-таблиц

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

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

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

Зная этот алгоритм хэширования, вы быстро найдете нужную книгу по ее названию.

Учтите, что хеш-функция должна иметь следующие свойства:

Всегда возвращать один и тот же адрес для одного и того же ключа;
Не обязательно возвращает разные адреса для разных ключей;
Использует все адресное пространство с одинаковой вероятностью;
Быстро вычислять адрес.

История

Исследования в области DHT изначально были мотивированы в частности пиринговыми системами, такими, как I2P, Napster, Gnutella, Freenet, которые использовали распределённые в интернете ресурсы для создания одного единственного приложения. В частности они использовали широкополосный интернет и пространство на жёстких дисках для предоставления сервиса распространения файлов.

Эти системы различаются тем, как они находили данные пиров:

Napster имел центральный индексный сервер: каждый узел, после присоединения, должен отправить список локально хранящихся файлов на сервер, который должен произвести поиск и направить запрос к узлам, содержащим результаты. Этот центральный компонент делал систему уязвимой для атак и рисков.
Gnutella и похожие сети двинулись к модели лавинных запросов — в основном, каждый поиск привёл бы к сообщению, передаваемому на все машины сети. Избегая централизованного отказа, этот метод был значительно менее эффективным, чем Napster.
Наконец, Freenet был также полностью распределённым, но маршрутизация работает на базе эвристического ключа, в котором каждый файл имеет ассоциированный с ним ключ, а файлы с похожими ключами имели тенденцию к объединению в кластеры на похожем наборе узлов. Запрос, скорее всего, направлялся таким кластерам без надобности опрашивать всех пиров. Однако Freenet не мог гарантировать, что данные будут найдены.

DHT используют маршрутизацию на базе более структурированного ключа, чтобы достигнуть децентрализации I2P, Gnutella и Freenet, а также эффективности и гарантируемых результатов Napster. Один из недочётов в том, что, как Freenet, DHT поддерживает только поиск по точному совпадению, а не по ключевым словам, хотя эти возможности могут наслаиваться поверх DHT.

Первые четыре DHT — CAN, Chord, Pastry и Tapestry (англ. Tapestry) — были введены приблизительно в 2001 году. С тех пор эта область изысканий была достаточно активна. Вне научных кругов DHT-технологию приняли как компонент BitTorrent и Coral Content Distribution Network.

Методы борьбы с коллизиями

Основная статья: Коллизия хеш-функции

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

Методы борьбы с коллизиями в хеш-таблицах

Основная статья: Хеш-таблица

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

метод цепочек (метод прямого связывания);
метод открытой адресации.

При использовании метода цепочек в хеш-таблице хранятся пары «связный список ключей» — «хеш-код». Для каждого ключа хеш-функцией вычисляется хеш-код; если хеш-код был получен ранее (для другого ключа), ключ добавляется в существующий список ключей, парный хеш-коду; иначе создаётся новая пара «список ключей» — «хеш-код», и ключ добавляется в созданный список. В общем случае, если имеется N{\displaystyle N} ключей и M{\displaystyle M} списков, средний размер хеш-таблицы составит NM{\displaystyle {\frac {N}{M}}}. В этом случае при поиске по таблице по сравнению со случаем, в котором поиск выполняется последовательно, средний объём работ уменьшится примерно в M{\displaystyle M} раз.

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

Криптографическая соль

Основная статья: Соль (криптография)

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

Хэш-карта с открытой адресацией

В хэш-карте с закрытой адресацией в случае коллизии элементы кладутся в корзину, в качестве которой могут выступать, например, список или дерево.
В хэш-карте с открытой адресацией в случае коллизии берётся какой-то другой элемент из этого же массива. В самом простом случае может использоваться линейный поиск, когда интервал
между «пробами» элементов в массиве фиксированный. Например, индекс 12345, элементов в массиве 10, поэтому берём элемент с индексом 5. Если он занят и интервал равен единице, то
берём шестой элемент. Если шестой занят, то седьмой и т.д. Так как у нас имеется коэффициент заполнения, то известно, что пустая ячейка всё-таки существует.

При квадратичном поиске интервал между элементами увеличивается как значение некоторого полинома второй степени.

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

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

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

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

Двойное хеширование

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

M может быть степенью двойки, а всегда возвращать нечетные числа.
M простое, а меньше .

Общее количество последовательностей проб .

Использование хеш-таблиц

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

Использование программы

Для запуска необходиа java версии 1.8 и Apache Maven версии 3.5.0.
Для компиляции необходимо в корне проекта выполнить команду

А для запуска программы

Оба параметра являются обязательными.

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

Формат входных данных

Входной файл содержит последовательность команд, т.е. представляет набор строк вида

где command — add, delete, search, min, max, print или спец. команда;
key — ключ, целое число;
data — данные, целое число.

Примеры:

#Print

Команда print отражает внутреннее строение структуры данных. Для хэш-таблицы с методом цепочек вывод команды print будет
иметь следующий вид:

{} — отдельная ячейка массива, в которой храниться список ключей.
А для хеш-таблиц с открытой адресацией вывод будет выглядеть так:

__ — пустая ячейка, D — удаленная ячейка.

Формат выходных данных

В выходной файл выводятся результаты исполнения программы.

Команда print должна отражать внутреннее строение структуры данных

Команда search выводит error, в случае, когда значение не было найдено, или значение найденное по ключу в противном случае.

Команда add добавляет значение в таблицу (Ничего не выводит).

Команда delete удаляетя число, или ничего не делает, если значение не было найдено (Ничего не выводит).

Команда min выводит минимальное число в таблице, или empty, если таблица пустая.

Команда max выводит максимальное число в таблице,или empty, если таблица пустая.

Тесты

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

3.Файлы с входными данными и правильными ответами.

На вход программе подается два файла.

Входной файл.
Выходной файл с результатами исполнения программы.

Заитем выходной файл с результатами исполнения программы сравнивается с файлом в котором находятся правильные ответы

Тесты находятся в ./tests/

Подробное описание тестов

1.Простая проверка всех операций кроме print

2.Проверка корректной работы add, delete(удаление элементов по несушествуюшему ключу) и print

3.Проверка корректной работы add, delete(удаление элементов по сушествуюшему ключу) и print

4.Проверка корректной работы search(поиск элементов по несушествуюшему ключу)

5.Проверка корректной работы search(поиск элементов по сушествуюшему ключу)

Время работы рачитываем тестом с 1000000 операций каждого типа.

Метод цепочек:

Add time: 545

Search time: 354

Delete time: 255

Линейное пробирование:

Add time: 562

Search time: 281

Delete time: 365

Двойное хэштрование:

Add time: 582

Search time: 273

Delete time: 377

Вывод

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

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

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

Двойное хеширование[править]

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

Принцип двойного хешированияправить

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

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

Выбор хеш-функцийправить

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

не равные
независимые от
взаимно простые с величиной хеш-таблицы

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

Например, если размер таблицы равен , то в качестве можно использовать функцию вида

Вставка при двойном хешировании

Примерправить

Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

Мы хотим вставить ключ 14. Изначально . Тогда . Но ячейка с индексом 1 занята, поэтому увеличиваем на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При получаем . Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных пара дает различные последовательности ячеек для исследования.

Простая реализацияправить

Пусть у нас есть некоторый объект , в котором определено поле , от которого можно вычислить хеш-функции и

Так же у нас есть таблица величиной , состоящая из объектов типа .

Вставка

function add(Item item):
     x = h1(item.key)
     y = h2(item.key)
        for (i = 0..m)    	
           if table == null
              table = item
           return      
        x = (x + y) mod m   
     table.resize()// ошибка, требуется увеличить размер таблицы

Поиск

Item search(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m)
        if table != null
           if table.key == key
              return table
           else
              return null
     x = (x + y) mod m   
     return null

Реализация с удалениемправить

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

Вставка

function add(Item item):
     x = h1(item.key)
     y = h2(item.key)
     for (i = 0..m)   	
        if table == null or deleted
           table = item
           deleted = false
           return      
        x = (x + i * y) mod m   
     table.resize()// ошибка, требуется увеличить размер таблицы

Поиск

Item search(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m) 
        if table != null
           if table.key == key and !deleted
              return table
        else
           return null
        x = (x + y) mod m   
     return null

Удаление

function remove(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m)
        if table != null
           if table.key == key
              deleted = true
        else 
           return
     x = (x + y) mod m

Разрешение коллизий

С коллизиями можно и нужно бороться. Существует несколько способов разрешения коллизий:

Метод цепочек

Каждая ячейка массива H{\displaystyle H} становится указателем на начало связного списка элементов ключ-значения, где хеш-значения каждого ключа в списке совпадают. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
Операции поиска или удаления элемента требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом(см.Рисунок 2).

Рисунок 2 — Разрешение коллизий при помощи цепочек

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

Определение «Коэффициент заполнения таблицы»
Коэффициентом заполнения таблицы называется отношения числа занятых индексов m{\displaystyle m} в таблице H{\displaystyle H} к ее длине n{\displaystyle n}. alfa=mn{\displaystyle alfa = m/n}.

Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка, и, в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива H{\displaystyle H} и перестроить таблицу. Добавление элемента в таблицу в любом случае занимает O(1){\displaystyle O(1)} и в лучшем, и в худшем случаях. Среднее время поиска и удаления элементов займут O(1+alfa){\displaystyle O(1 + alfa)}.

Открытая адресация

В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент(см.Рисунок 3). Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность h(x),h1(x),…,hn—1(x){\displaystyle h0(x), h1(x), …, hn — 1(x)}, где x{\displaystyle x} — ключ элемента, а hi(x){\displaystyle hi(x)} — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него одним из приведённых ниже способов. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.

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

Рисунок 3 — Пример хеш-таблицы с открытой адресацией

История

Шифровка сообщений без возможности однозначной расшифровки, а только с целью подтверждения авторского приоритета, применялась издавна.

Галилео Галилей наблюдал кольца Сатурна, которые принял за «ушки». Не будучи уверен, но желая утвердить свой приоритет, он опубликовал сообщение с перестановленными буквами: smaismrmilmepoetaleumibunenugttauiras. В 1610 году он раскрыл исходную фразу: Altissimum planetam tergeminum obseruaui, что в переводе с латинского языка означает «высочайшую планету тройною наблюдал». Таким образом, на момент публикации первого сообщения исходная фраза не была раскрыта, но была создана возможность подтвердить её позже.

В середине 1650-х Христиан Гюйгенс разглядел кольца и опубликовал сообщение с буквами, расставленными по алфавиту: ааааааа, ссссс, d, еееее, g, h, iiiiiii, lllll, mm, nnnnnnnnn, oooo, pp, q, rr, s, ttttt, uuuuu. Через некоторое время была опубликована и исходная фраза: Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato — «Окружен кольцом тонким, плоским, нигде не подвешенным, наклоненным к эклиптике». От применения хеш-функции, включая и цель позднее подтвердить некоторое нераскрытое сообщение, данный случай отличается только тем, что выходное сообщение не имеет фиксированной длины, а определяется длиной входного. Фактически, расстановка букв исходного сообщения по алфавиту является некоторой хеш-функцией, но только с результатом нефиксированной длины.

В январе 1953 года Ханс Петер Лун (нем. Hans Peter Luhn) (сотрудник фирмы IBM) предложил «хеш-кодирование». Дональд Кнут считает, что Ханс первым выдвинул систематическую идею «хеширования».

В 1956 году Арнольд Думи (англ. Arnold Dumey) в своей работе «Computers and automation» первым описал идею «хеширования» такой, какой её знает большинство программистов сейчас. Думи рассматривал «хеширование» как решение «проблемы словаря», предложил использовать в качестве «хеш-адреса» остаток от деления на простое число.

В 1957 году в журнале «IBM Journal of Research and Development» была опубликована статья Уэсли Питерсона (англ. W. Wesley Peterson) о поиске текста в больших файлах. Эта работа считается первой «серьёзной» работой по «хешированию». В статье Уэсли определил «открытую адресацию», указал на уменьшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz), в которой было проведено обширное исследование «хеш-функций». В течение нескольких последующих лет «хеширование» широко использовалось, однако никаких значимых работ не публиковалось.

В 1967 году «хеширование» в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris) опубликовал в журнале «Communications of the ACM» большой обзор по «хешированию». Эта работа считается «ключевой» публикацией, вводящей понятие о «хешировании» в научный оборот, и закрепившей термин «хеш», ранее применявшийся только специалистами (жаргон).

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Петровича Ершова использовалось слово «расстановка», а для «коллизий» использовался термин «конфликт» (А. П. Ершов использовал «расстановку» с 1956 года). В русскоязычном издании книги Никлауса Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка». Предлагалось также назвать метод другим русским словом: «окрошка». Однако ни один из этих вариантов не прижился, и в русской литературе используется преимущественно термин «хеширование».