Криптографические хеш-функции.

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

Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.

Понятие хеш-функции

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

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

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

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

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Результат (0110 0101 (2) или 65 (16) ) и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

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

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

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

h i =H(M i ,h i-1),

где h i-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

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

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

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

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

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

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

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

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть М i – блок исходного сообщения, h i – значение хеш-функции на i-том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

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

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

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

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

Если базовый набор содержит N элементов, то его можно разбить на 2 N различных подмножеств.

Хеш-таблица и хеш-функции

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

i = h (key );

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

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

Хорошей хеш-функцией считается такая функция, которая минимизирует коллизии и распределяет данные равномерно по всей таблице, а совершенной хеш-функцией – функция, которая не порождает коллизий:

Разрешить коллизии при хешировании можно двумя методами:

– методом открытой адресации с линейным опробыванием;

– методом цепочек.

Хеш-таблица

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

Хеш-структуру считают обобщением массива, который обеспечивает быстрый прямой доступ к данным по индексу.

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

Примеры хеш-функций

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

Метод деления . Исходными данными являются – некоторый целый ключ key и размер таблицы m . Результатом данной функции является остаток от деления этого ключа на размер таблицы. Общий вид функции:

int h(int key, int m) {

return key % m; // Значения

Для m = 10 хеш-функция возвращает младшую цифру ключа.

Для m = 100 хеш-функция возвращает две младшие цифры ключа.

Аддитивный метод , в котором ключом является символьная строка. В хеш-функции строка преобразуется в целое суммированием всех символов и возвращается остаток от деления на m (обычно размер таблицы m = 256).

int h(char *key, int m) {

Коллизии возникают в строках, состоящих из одинакового набора символов, например, abc и cab .

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

int h(char *key, int m) {

int len = strlen(key), s = 0;

if(len < 2) // Если длина ключа равна 0 или 1,

s = key; // возвратить key

s = key + key;

В этом случае коллизии будут возникать только в строках, например, abc и amc .

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

Например, ключом является целое 32-битное число, а хеш-функция возвращает средние 10 бит его квадрата:

int h(int key) {

key >>= 11; // Отбрасываем 11 младших бит

return key % 1024; // Возвращаем 10 младших бит

Метод исключающего ИЛИ для ключей-строк (обычно размер таблицы m =256). Этот метод аналогичен аддитивному, но в нем различаются схожие слова. Метод заключается в том, что к элементам строки последовательно применяется операция «исключающее ИЛИ».

В мультипликативном методе дополнительно используется случайное действительное число r из интервала . Если это произведение умножить на размер таблицы m , то целая часть полученного произведения даст значение в диапазоне от 0 до m –1.

int h(int key, int m) {

double r = key * rnd();

r = r – (int)r; // Выделили дробную часть

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

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

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

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

Коллизией для функции h называется пара значений x, y, x ≠ y , такая, что h(x) = h(y) . Т.о. хеш-функция должна обладать следующими свойствами:

Для данного значения h(x) невозможно найти значение аргумента x . Такие хеш-функции называют стойкими в смысле обращения или стойкими в сильном смысле ;

Для данного аргумента x невозможно найти другой аргумент y такой, что h(x) = h(y) . Такие хеш-функции называют стойкими в смысле вычисления коллизий или стойкими в слабом смысле .

В случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то это значение называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

На практике хеш-функции используют в следующих целях:

Для ускорения поиска данных в БД;

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

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

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

Рис.10.1. Процедура вычисления значения хеш-функции

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

2) Для инициализации процедуры хеширования используется синхропосылка y 0 .

3) Прообраз X разбивается на n блоков x i (i = 1 .. n) фиксированной длины L бл , над которыми выполняется однотипная процедура хеширования f(y i-1 , x i) , зависящая от результата хеширования предыдущего блока y i-1 .

4) Хеш-образом h(T) исходного сообщения Т будет результат процедуры хеширования y n , полученный после обработки последнего блока x n .

10.2. MD5

MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 г. Является улучшенной в плане безопасности версией MD4 .

Ниже приведен алгоритм вычисления хеша.

1. Выравнивание потока.

В конец исходного сообщения, длиной L , дописывают единичный бит, затем необходимое число нулевых бит так, чтобы новый размер L" был сравним с 448 по модулю 512 (L’ mod 512 = 448). Добавление нулевых бит выполняется, даже если новая длина, включая единичный бит, уже сравнима с 448.

2. Добавление длины сообщения.

К модифицированному сообщению дописывают 64-битное представление длины данных (количество бит в сообщении). Т.е. длина сообщения T становится кратной 512 (T mod 512 = 0). Если длина исходного сообщения превосходит 2 64 - 1, то дописывают только младшие 64 бита. Кроме этого, для указанного 64-битного представления длины вначале записываются младшие 32 бита, а затем старшие 32 бита.

3. Инициализация буфера.

Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения (шестнадцатеричное представление):

A = 67 45 23 01;
B = EF CD AB 89;
C = 98 BA DC FE;
D = 10 32 54 76.

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

4. Вычисление хеша в цикле.

Исходное сообщение разбивается на блоки T , длиной 512 бит. Для каждого блока в цикле выполняется процедура, приведенная на рис.10.2. Результат обработки всех блоков исходного сообщения в виде объединения 32-битных значений переменных ABCD и будет являться хешем.

Рис.10.2. Шаг основного цикла вычисления хеша

В каждом раунде над переменными ABCD и блоком исходного текста Т в цикле (16 итераций) выполняются однотипные преобразования по следующей схеме.

Рис.10.3. Одна итерация цикла раунда

Условные обозначения.

1) RF - раундовая функция, определяемая по следующей таблице.

Таблица 10.1. Раундовые функции RF

2) t j - j-ая 32-битовая часть блока исходного сообщения Т с обратным порядком следования байт;

3) k i - целая часть константы, определяемой по формуле

k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10.1)

где i – номер итерации цикла (i = 1..16);
r – номер раунда (r = 1..4).

Аргумент функции sin измеряется в радианах.

4) ⊞ – сложение по модулю 2 32 .

5) <<< s i – циклический сдвиг влево на s i разрядов.

Используемая 32-битовая часть блока исходного сообщения t j и величина циклического сдвига влево s i зависят от номера итерации и приведены в следующей таблице.

Таблица 10.2. Величины, используемые на шаге цикла раунда

№ итерации		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Раунд 1	t j	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
Раунд 1	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
Раунд 2	t j	t 2	t 7	t 12	t 1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
Раунд 2	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
Раунд 3	t j	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t 1	t 4	t 7	t 10	t 13	t 16	t 3
Раунд 3	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
Раунд 4	t j	t 1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
Раунд 4	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

После 4 раундов новое (модифицированное) значение каждой из переменных ABCD складывается (⊞ ) с исходным (значением переменной до 1-го раунда).

5. Перестановка байт в переменных ABCD . После обработки всех блоков исходного сообщения для каждой переменной выполняется обратная перестановка байт.

Поиск коллизий.

В 2004 г. китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере IBM p690) находить коллизии.

10.3. Применение шифрования для получения хеш-образа

Для выработки устойчивого к коллизиям хеш-образа могут применяться специальные режимы, предусмотренные в блочных шифрах (например, сцепление блоков шифра у ), или в самой хеш-функции, как составная часть, может использоваться один из режимов блочного шифра (например, составной часть хеш-функции по ГОСТ 34.11-94 1 является режим простой замены алгоритма криптографического преобразования по 2).

Напомним что в случае, когда значение хеш-функции зависит не только от прообраза, но и закрытого ключа, то хеш-образ называют кодом проверки подлинности сообщений (Message Authentication Code, MAC), кодом проверки подлинности данных (Data Authentication Code, DAC) или имитовставкой .

В качестве примера приведем режим (сцепление блоков шифра - Cipher Block Chaining).

Рис.10.4. Схема алгоритма DES в режиме сцепления блоков шифра

Последний зашифрованный блок C n и есть хеш-образ сообщения T = {T 1 , T 2 , …, T n } .

1 ГОСТ 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования».

2 ГОСТ 28147-89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».

Вопросы для самопроверки

1. Дайте определение понятиям: « », « », « ».

Рассмотренные нами алгоритмы поиска обычно основаны на абстрактной операции сравнения. Из этого ряда существенно выделяется метод распределяющего поиска, описанный в "Таблицы символов и деревья бинарного поиска" , при котором элемент с ключом i хранится в i-ой позиции таблицы, что позволяет обратиться к нему непосредственно. При распределяющем поиске значения ключей используются в качестве индексов массива, а не операндов операции сравнения; сам метод основан на том, что ключи являются различными целыми числами из того же диапазона, что и индексы таблицы. В этой главе мы рассмотрим хеширование ( hashing ) - расширенный вариант распределяющего поиска, применяемый в более типичных приложениях поиска, где ключи не обладают столь удобными свойствами. Конечный результат применения данного подхода совершенно не похож на методы, основанные на сравнении - вместо перемещения по структурам данных словаря с помощью сравнения ключей поиска с ключами в элементах, мы пытаемся обратиться к элементам в таблице непосредственно, выполняя арифметическое преобразование ключей в адреса таблицы.

Алгоритмы поиска, использующие хеширование , состоят из двух отдельных частей. Первый шаг - вычисление хеш-функции ( hash function ), которая преобразует ключ поиска в адрес в таблице. В идеале различные ключи должны были бы отображаться на различные адреса, но часто два или более различных ключа могут дать один и тот же адрес в таблице. Поэтому вторая часть поиска методом хеширования - процесс разрешения коллизий ( collision resolution ), который обрабатывает такие ключи. В одном из методов разрешения конфликтов, который мы рассмотрим в этой главе, используются связные списки, поэтому он находит непосредственное применение в динамических ситуациях, когда трудно заранее предугадать количество ключей поиска. В других двух методах разрешения коллизий достигается высокая производительность поиска, поскольку элементы хранятся в фиксированном массиве. Мы рассмотрим способ усовершенствования этих методов, позволяющий использовать их и в тех случаях, когда нельзя заранее предсказать размеры таблицы.

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

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

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

Хеш-функции

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

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

Вероятно, простейшей является ситуация, когда ключами являются числа с плавающей точкой из фиксированного диапазона. Например, если ключи - числа, большие 0 и меньшие 1, их можно просто умножить на M, округлить результат до меньшего целого числа и получить адрес в диапазоне между 0 и M - 1 ; такой пример показан на рис. 14.1 . Если ключи больше s и меньше t, их можно масштабировать, вычтя s и разделив на t-s , в результате чего они попадут в диапазон значений между 0 и 1, а затем умножить на M и получить адрес в таблице.

Рис. 14.1.

Для преобразования чисел с плавающей точкой в диапазоне между 0 и 1 в индексы таблицы, размер которой равен 97, выполняется умножение этих чисел на 97. В данном примере произошло три коллизии: для индексов, равных 17, 53 и 76. Хеш-значения определяются старшими разрядами ключа, младшие разряды не играют никакой роли. Одна из целей разработки хеш-функции - устранение такого дисбаланса, чтобы во время вычисления учитывался каждый разряд.

Если ключи являются w-разрядными целыми числами, их можно преобразовать в числа с плавающей точкой и разделить на 2 w для получения чисел с плавающей точкой в диапазоне между 0 и 1, а затем умножить на M, как в предыдущем абзаце. Если операции с плавающей точкой занимают много времени, а числа не столь велики, чтобы привести к переполнению, этот же результат может быть получен с помощью целочисленных арифметических операций: нужно ключ умножить на M, а затем выполнить сдвиг вправо на w разрядов для деления на 2 w (или, если умножение приводит к переполнению, выполнить сдвиг, а затем умножение). Такие методы бесполезны для хеширования, если только ключи не распределены по диапазону равномерно, поскольку хеш-значение определяется только ведущими цифрами ключа.

Более простой и эффективный метод для w-разрядных целых чисел - один из, пожалуй, наиболее часто используемых методов хеширования - выбор в качестве размера M таблицы простого числа и вычисление остатка от деления к на M, т.е. h(k) = k mod M для любого целочисленного ключа k. Такая функция называется модульной хеш-функцией. Ее очень просто вычислить (k % M в языке C++), и она эффективна для достижения равномерного распределения значений ключей между значениями, меньшими M. Небольшой пример показан на рис. 14.2 .

Рис. 14.2.

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

v % 97 (слева)

v % 100 (в центре) и

(int) (a * v) % 100 (справа),

где a = .618033 . Размеры таблицы для этих функций соответственно равны 97, 100 и 100. Значения выглядят случайными (поскольку случайны ключи). Вторая функция (v % 100 ) использует лишь две крайние правые цифры ключей и поэтому для неслучайных ключей может показывать низкую производительность.

Модульное хеширование применимо и к ключам с плавающей точкой. Если ключи принадлежат небольшому диапазону, можно масштабировать их в числа из диапазона между 0 и 1, 2 w для получения w-разрядных целочисленных значений, а затем использовать модульную хеш-функцию. Другой вариант - просто использовать в качестве операнда модульной хеш-функции двоичное представление ключа (если оно доступно).

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

Основная причина выбора в качестве размера M хеш-таблицы простого числа для модульного хеширования показана на рис. 14.3 . В этом примере символьных данных с 7-разрядным кодированием ключ трактуется как число с основанием 128 - по одной цифре для каждого символа в ключе. Слово now соответствует числу 1816567, которое может быть также записано как

поскольку в ASCII-коде символам n, o и w соответствуют числа 1568 = 110 , 1578 = 111 и 1678 = 119 . Выбор размера таблицы M = 64 для этого типа ключа неудачен, поскольку добавление к х значений, кратных 64 (или 128), не меняет значение х mod 64 - для любого ключа значением хеш-функции является значение последних 6 разрядов этого ключа. Безусловно, хорошая хеш-функция должна учитывать все разряды ключа, особенно для символьных ключей. Аналогичные ситуации могут возникать, когда M содержит множитель, являющийся степенью 2. Простейший способ избежать этого - выбрать в качестве M простое число.

Рис. 14.3.

В каждой строке этой таблицы приведены: 3-буквенное слово, представление этого слова в ASCII-коде как 21-битовое число в восьмеричной и десятичной формах и стандартные модульные хеш-функции для размеров таблиц 64 и 31 (два крайних справа столбца). Размер таблицы 64 приводит к нежелательным результатам, поскольку для получения хеш-значения используются только самые правые разряды ключа, а буквы в словах обычного языка распределены неравномерно. Например, всем словам, оканчивающимся на букву у, соответствует хеш-значение 57. И, напротив, простое значение 31 вызывает меньше коллизий в таблице более чем вдвое меньшего размера.

Модульное хеширование очень просто реализовать, за исключением того, что размер таблицы должен быть простым числом. Для некоторых приложений можно довольствоваться небольшим известным простым числом или же поискать в списке известных простых чисел такое, которое близко к требуемому размеру таблицы. Например, числа равные 2 t - 1, являются простыми при t = 2, 3, 5, 7, 13, 17, 19 и 31 (и ни при каких других значениях t < 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

Рис. 14.4.

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

Другой вариант обработки целочисленных ключей - объединение мультипликативного и модульного методов: нужно умножить ключ на константу в диапазоне между 0 и 1, а затем выполнить деление по модулю M. Другими словами, необходимо использовать функцию . Между значениями , M и эффективным основанием системы счисления ключа существует взаимосвязь, которая теоретически могла бы привести к аномальному поведению, но если использовать произвольное значение a, в реальном приложении вряд ли возникнет какая-либо проблема. Часто в качестве a выбирают значение ф = 0,618033... (золотое сечение).

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

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

В 7-разрядном ASCII-коде этому слову соответствует 84-разрядное число \begin{align*} 97 \cdot 128^{11} &+ 118 \cdot 128^{10} + 101 \cdot 128^{9} + 114 \cdot 128^{8} + 121 \cdot 128^{7}\\ &+ 108 \cdot 128^{6} + 111 \cdot 128^{5} + 110 \cdot 128^{4} + 103 \cdot 128^{3}\\ &+ 107 \cdot 128^{2} + 101 \cdot 128^{1} + 121 \cdot 128^{0}, \end{align*},

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

Чтобы вычислить модульную хеш-функцию для длинных ключей, они преобразуются фрагмент за фрагментом. Можно воспользоваться арифметическими свойствами функции модуля и использовать алгоритм Горнера (см. раздел 4.9 "Абстрактные типы данных"). Этот метод основан на еще одном способе записи чисел, соответствующих ключам. Для рассматриваемого примера запишем следующее выражение: \begin{align*} ((((((((((97 \cdot 128^{11} &+ 118) \cdot 128^{10} + 101) \cdot 128^{9} + 114) \cdot 128^{8} + 121) \cdot 128^{7}\\ &+ 108) \cdot 128^{6} + 111) \cdot 128^{5} + 110) \cdot 128^{4} + 103) \cdot 128^{3}\\ &+ 107) \cdot 128^{2} + 101) \cdot 128^{1} + 121. \end{align*}

То есть десятичное число, соответствующее символьной кодировке строки, можно вычислить при просмотре ее слева направо, умножая накопленное значение на 128, а затем добавляя кодовое значение следующего символа. В случае длинной строки этот способ вычисления в конце концов приведет к числу, большему того, которое вообще можно представить в компьютере. Однако это число и не нужно, поскольку требуется только (небольшой) остаток от его деления на M. Результат можно получить, даже не сохраняя большое накопленное значение, т.к. в любой момент вычисления можно отбросить число, кратное M - при каждом выполнении умножения и сложения нужно хранить только остаток от деления по модулю M. Результат будет таким же, как если бы у нас имелась возможность вычислить длинное число, а затем выполнять деление (см. упражнение 14.10). Это наблюдение ведет к непосредственному арифметическому способу вычисления модульных хеш-функций для длинных строк - см. программу 14.1. В этой программе используется еще одно, последнее ухищрение: вместо основания 128 в ней используется простое число 127. Причина этого изменения рассматривается в следующем абзаце.

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

Программа 14.1. Хеш-функция для строковых ключей

M = 96 и a = 128 (вверху),

M = 97 и a = 128 (в центре) и

M = 96 и a = 127 (внизу)

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

В программе 14.1 показан один из способов сделать это: использование простого основания вместо степени 2 и целого числа, соответствующего ASCII-представлению строки. На рис. 14.5 рис. 14.5 показано, как это изменение улучшает распределение для типичных строковых ключей. Теоретически хеш-значения, созданные программой 14.1, могут давать плохие результаты для размеров таблицы, которые кратны 127 (хотя на практике это, скорее всего, будет почти незаметно); для создания рандомизированного алгоритма можно было бы выбрать значение множителя наугад. Еще более эффективный подход - использование случайных значений коэффициентов в вычислении и различных случайных значений для каждой цифры ключа. Такой подход дает рандомизированный алгоритм, называемый универсальным хешированием (universal hashing).

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

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

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

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

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

История

Дональд Кнут приписывает первую систематическую идею хеширования сотруднику IBM Ханса Петера Луна, предложил хеш в январе 1953 года.

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

Первой значительной работой, которая была связана с поиском в больших файлах, была статья Уэсли Питерсона в IBM Journal of Research and Development 1957 года в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Через шесть лет была опубликована работа Вернера Бухгольца, в которой в значительной степени исследовались хэш-функции. В течение нескольких следующих лет хеширования широко использовалось, однако не было опубликовано ни одной значительной работы.

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

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

Описание

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

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

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

Виды хеш-функций

Хорошая хеш-функция должна удовлетворять двум свойствам:

Быстро исчисляться;
Минимизировать количество коллизий

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

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

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

Хэш-функции на основе деления

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

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

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

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

Мультипликативная схема хеширования

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

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

Среди преимуществ этих двух методов стоит отметить, что они выгодно используют то, что реальные ключи неслучайны. Например, в том случае, если ключи представляют собой арифметическую прогрессию (допустим последовательность названий «имья1», «имя2», «имья3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенную арифметическую прогрессию различных хеш-значений, уменьшает количество коллизий по сравнению со случайной ситуацией.

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

Хеширования строк переменной длины

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

Хеширования Пирсона (англ. Pearson hashing) — алгоритм, предложенный Питером Пирсоном (англ. Peter Pearson) для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хэш-кода для строки произвольной длины. На вход функция получает слово, состоящее из символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.

Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок

h: = 0 For each c in W loop index:= h xor ch:= T End loop Return h

Среди преимуществ алгоритма следует отметить:

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

В качестве альтернативного способа хеширования ключей, состоящие из символов (), можно предложить вычисления

Применение хэш-функций

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

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

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

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

Данные требования зависят друг от друга:

Оборотная функция неустойчива к коллизиям первого и второго рода.
Функция, неустойчивая к коллизиям первого рода, неустойчивая к коллизиям второго рода; обратное неверно.

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

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

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

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

Геометрическое хеширования

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

Ускорение поиска данных

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