Технология разрешения коллизий которая предполагает хранение записей в самой хеш таблице

Обновлено: 05.07.2024

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

3. Ключевые термины

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

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

6. Метод деления

Исходными данными являются – некоторый целый ключ key и
размер таблицы m. Результатом данной функции является
остаток от деления этого ключа на размер таблицы. Общий
вид функции:
int h(int key, int m) return key % m; // Значения
>
Для m = 10 хеш-функция возвращает младшую цифру ключа.
6

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

8. Аддитивный метод

в котором ключом является символьная строка. В хеш-
функции строка преобразуется в целое суммированием всех
символов и возвращается остаток от деления на m (обычно
размер таблицы m = 256).
int h(char *key, int m) int s = 0;
while(*key)
s += *key++;
return s % m;
>
Коллизии возникают в строках, состоящих из одинакового
набора символов, например, abc и cab.
8

Данный метод можно несколько модифицировать, получая
результат, суммируя только первый и последний символы
строки-ключа.
int h(char *key, int m) int len = strlen(key), s = 0;
if(len < 2) // Если длина ключа равна 0 или 1,
s = key[0]; // возвратить key[0]
else
s = key[0] + key[len–1];
return s % m;
>
В этом случае коллизии будут возникать только в строках,
например, abc и amc.
9

10. Метод середины квадрата

в котором ключ возводится в квадрат (умножается сам на себя) и
в качестве индекса используются несколько средних цифр
полученного значения.
Например, ключом является целое 32-битное число, а хешфункция возвращает средние 10 бит его квадрата:
int h(int key) key *= key;
key >>= 11; // Отбрасываем 11 младших бит
return key % 1024; // Возвращаем 10 младших бит
>
10

11. Мультипликативный метод

В мультипликативном методе дополнительно используется
случайное действительное число r из интервала [0,1), тогда
дробная часть произведения r*key будет находиться в
интервале [0,1]. Если это произведение умножить на размер
таблицы m, то целая часть полученного произведения даст
значение в диапазоне от 0 до m–1.
int h(int key, int m) double r = key * rnd();
r = r – (int)r; // Выделили дробную часть
return r * m;
>
11

12. Две классические схемы

– хеширование методом цепочек (со списками),
или так называемое многомерное хеширование
– chaining with separate lists (открытое
хеширование);
– хеширование методом открытой адресации с
линейным опробыванием – linear probe open
addressing (закрытое хеширование).
12

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

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

16. Пример реализации метода прямой адресации

Исходными данными являются 7 записей (для
простоты информационная часть состоит из
целых чисел) объявленного структурного типа:
struct zap int key; // Ключ
int info; // Информация
> data;
, , , , , , ;
размер хеш-таблицы m = 10. Выберем хешфункцию i = h(data) = data.key%10; т.е. остаток от
деления на 10 – iÎ[0,9].
16

На основании исходных данных последовательно заполняем
хеш-таблицу.
Хеширование первых пяти ключей дает различные индексы
(хеш-адреса):
i = 59 % 10 = 9; i = 70 % 10 = 0;
i = 96 % 10 = 6; i = 81 % 10 = 1;
i = 13 % 10 = 3.
17

18. Реализация метода цепочек для предыдущего примера

Реализация метода цепочек для
предыдущего примера
Объявляем структурный тип для элемента
однонаправленного списка:
struct zap int key; // Ключ
int info; // Информация
zap *Next; // Указатель на следующий
элемент в списке
> data;
На основании исходных данных последовательно
заполняем хеш-таблицу, добавляя новый элемент
в конец списка, если место уже занято.
18

Хеширование первых пяти ключей, как и в предыдущем
случае, дает различные индексы (хеш-адреса): 9, 0, 6, 1, и 3.
При возникновении коллизии новый элемент добавляется в
конец списка. Поэтому элемент с ключом 41 помещается после
элемента с ключом 81, а элемент с ключом 79 – после
элемента с ключом 59.
19

20. Хеш-таблица

Идеальной хеш-функцией является такая hash-
функция, которая для любых двух
неодинаковых ключей дает неодинаковые
адреса.
21

22. Рассмотрим пример реализации несовершенной хеш-функции на языке TurboPascal.

Рассмотрим пример реализации несовершенной хешфункции на языке TurboPascal.
function hash (key : string[4]): integer;
var
f: longint;
begin
f:=ord (key[1]) - ord (key[2]) + ord (key[3]) -ord (key[4]);

f:=f+255*2;
адресом хеш-таблицы (a=1)>
f:=(f*10000) div (255*4);
хеш-таблицы (a=10 000)>
hash:=f
end;
22

23. Разновидности методов разрешение коллизий

24. Разрешение коллизий при добавлении элементов методом цепочек

25. Разрешение коллизий при добавлении элементов методами открытой адресации

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

Линейное опробование сводится к последовательному
27
перебору элементов таблицы с некоторым
фиксированным шагом
a=h(key) + c*i ,
где i номер попытки разрешить коллизию. При шаге
равном единице происходит последовательный перебор
всех элементов после текущего.
Квадратичное опробование отличается от линейного тем,
что шаг перебора элементов не линейно зависит от
номера попытки найти свободный элемент
a = h(key2) + c*i + d*i 2
Благодаря нелинейности такой адресации уменьшается
число проб при большом числе ключей-синонимов.
Однако даже относительно небольшое число проб может
быстро привести к выходу за адресное пространство
небольшой таблицы вследствие квадратичной
зависимости адреса от номера попытки.

Еще одна разновидность метода открытой адресации, которая
называется двойным хешированием, основана на нелинейной
адресации, достигаемой за счет суммирования значений
основной и дополнительной хеш-функций
a=h1(key) + i*h2(key).
Опишем алгоритмы вставки и поиска для метода линейное
опробование.
Вставка
i=0
a = h(key) + i*c
Если t(a) = свободно, то t(a) = key, записать элемент, стоп
элемент добавлен
i = i + 1, перейти к шагу 2
Поиск
i=0
a = h(key) + i*c
Если t(a) = key, то стоп элемент найден
Если t(a) = свободно, то стоп элемент не найден
i = i + 1, перейти к шагу 2
28

Вставка
i=0
a = h(key) + i*c
Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать элемент, стоп
элемент добавлен
i = i + 1, перейти к шагу 2
Удаление
i=0
a = h(key) + i*c
Если t(a) = key, то t(a) =удалено, стоп элемент удален
Если t(a) = свободно, то стоп элемент не найден
i = i + 1, перейти к шагу 2
Поиск
i=0
a = h(key) + i*c
Если t(a) = key, то стоп элемент найден
Если t(a) = свободно, то стоп элемент не найден
i = i + 1, перейти к шагу 2
29

30. Циклический переход к началу таблицы

Рассмотрим данный способ на примере метода
линейного опробования. При вычислении адреса
очередного элемента можно ограничить адрес, взяв
в качестве такового остаток от целочисленного
деления адреса на длину таблицы n.
Вставка
i=0
a = (h(key) + c*i) mod n
Если t(a) = свободно или t(a) = удалено, то t(a) = key,
записать элемент, стоп элемент добавлен
i = i + 1, перейти к шагу 2
31

Вставка
i=0
a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
Если t(a) = свободно или t(a) = удалено, то t(a) = key, записать
элемент, стоп элемент добавлен
i = i + 1, перейти к шагу 2
a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
32

33. Алгоритм вставки

Вставка
i=0
a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
Если t(a) = свободно или t(a) = удалено, то t(a) = key,
записать элемент, стоп элемент добавлен
Если i > m , то стоп требуется рехеширование
i = i + 1, перейти к шагу 2
В данном алгоритме номер итерации сравнивается с
пороговым числом m. Следует заметить, что
алгоритмы вставки, поиска и удаления должны
использовать идентичное образование адреса
очередной записи.
33

Удаление
i=0
a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
Если t(a) = key, то t(a) =удалено, стоп элемент удален
Если t(a) = свободно или i>m, то стоп элемент не найден
i = i + 1, перейти к шагу 2
Поиск
i=0
a = ((h(key) + c*i) div n + (h(key) + c*i) mod n) mod n
Если t(a) = key, то стоп элемент найден
Если t(a) = свободно или i>m, то стоп элемент не найден
i = i + 1, перейти к шагу 2
34

35. Распределение коллизий в адресном пространстве таблицы

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

Пример
Ключ 10 символов, 1-й большая латинская буква
2-10 малые латинские буквы
var i:integer; s:string[10];
begin
s[1]:=chr(random(90-65)+65);
for i:=2 to 10 do s[i]:=chr(random(122-97)+97);
end
Генерация ключа из m символов c кодами в
диапазоне от n1 до n2 (диапазон непрерывный)
for i:=1 to m do str[i]:=chr(random(n2-n1)+n1);
36

37. Генерация ключа из m символов c кодами в диапазоне от n1 до n4 (диапазон имеет разрыв от n2 до n3)

for i:=1 to m do
begin
x:=random((n4 - n3) + (n2 n1));
if x<=(n2 - n1) then str[i]:=chr(x + n1)
else str[i]:=chr(x + n1 + n3 n2)
end;
37

38. Пример: длина ключа 7 символов

39. Известные Хэш-функции

1. CRC16, CRC32, CRC64 - эти Хэш-функции очень просты и применяются
только для проверки целостности данных. Например, при передачи данных по
сети. При этом цифра после CRC - это не более, чем количество бит в выходном
блоке. Самым известным из них является CRC32, размер Хэш-кода которого
составляет всего 4 байта.
Примечание: Данная функция свертки состоит всего из одной операции XOR,
которая последовательно выполняется ко всем входным блокам исходного
текста. Поэтому ее обычно применяют только для проверки целостности
данных.
2. MD5 - в свое время эта Хэш-функция была очень популярна для хранения
паролей и прочих целей безопасности. Размер выходного блока составляет
128 бит. В принципе, применяется и до сих пор, однако стоит знать, что
стойкость этого алгоритма уже не столько хороша, т.к. мощность
компьютеров выросла.
3. SHA-1, SHA-2 - самым известным и поддерживаемым многими системами
является стандарт SHA-1 (160 бит). Однако, постепенно идет переход на SHA-2
(от 224 бит до 512), так как стойкость первого алгоритма постепенно
снижается, как и у MD5.
На самом деле, в РФ существует и применяется собственный криптостойкий
39
алгоритм ГОСТ Р 34.11-2012

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

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

Отдельная цепочка

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

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

Отдельное сцепление со связанными списками

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

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

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

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

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

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

Отдельное сцепление со списком заголовочных ячеек

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

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

Отдельное сцепление с другими структурами

Вместо списка можно использовать любую другую структуру данных, которая поддерживает требуемые операции. Например, используя самобалансирующееся двоичное дерево поиска, теоретическое время наихудшего случая операций с обычной хэш-таблицей (вставка, удаление, поиск) может быть уменьшено до O(log n), а не O(n). Однако это вносит дополнительную сложность в реализацию и может привести к еще худшей производительности для небольших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше, чем время, необходимое для выполнения линейного поиска по всем элементам списка. Реальным примером хэш-таблицы, которая использует самобалансирующееся двоичное дерево поиска для сегментов, является класс HashMap в Java 8.

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

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

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

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

Хорошо известные последовательности проб включают в себя:

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

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

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

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

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

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

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

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

Объединенное хэширование

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

Кукушечное хэширование

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

Hopscotch хэширование

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

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

Хэширование Робина Гуда

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

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

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

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

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

Мотивация использовать хеш-таблицы

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

Контейнер \ операция	insert	remove	find
Array	O(N)	O(N)	O(N)
List	O(1)	O(1)	O(N)
Sorted array	O(N)	O(N)	O(logN)
Бинарное дерево поиска	O(logN)	O(logN)	O(logN)
Хеш-таблица	O(1)	O(1)	O(1)

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

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

Понятие хеш-таблицы

Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.

Теперь стало понятно, почему же это именно хеш-таблица.

Проблема коллизии

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

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

Решения проблемы коллизии методом двойного хеширования

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

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

Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

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

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

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

Помня о данной проблеме построим наш класс.

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

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

Но к чему слова, код все разъяснит:

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

Цель лекции: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++.

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

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

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

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

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

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

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

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

Хеш-таблицы должны соответствовать следующим свойствам.

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

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

Методы разрешения коллизий

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

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

Метод цепочек. Технология сцепления элементов состоит в том, что элементы множества , которым соответствует одно и то же хеш- значение , связываются в цепочку- список . В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш- значение ключа равно i ; если таких элементов в множестве нет, в позиции i записан NULL . На рис. 38.1 демонстрируется реализация метода цепочек при разрешении коллизий . На ключ 002 претендуют два значения, которые организуются в линейный список .

Рис. 38.1. Разрешение коллизий при помощи цепочек

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

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

При предположении, что каждый элемент может попасть в любую позицию таблицы с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее время работы операции поиска элемента составляет O(1+k) , где k – коэффициент заполнения таблицы.

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

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

Рис. 38.2. Разрешение коллизий при помощи открытой адресации

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

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

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

Читайте также: