Хеширование (hashing) использует аналогичный подход, отображая элементы в хеш‑таблице (hash table). Алгоритм хеширования использует некоторую функцию, которая определяет вероятное положение элемента в таблице на основе значения искомого элемента.
Например, предположим, что требуется запомнить несколько записей, каждая из которых имеет уникальный ключ со значением от 1 до 100. Для этого можно создать массив со 100 ячейками и проинициализировать каждую ячейку нулевым ключом. Чтобы добавить в массив новую запись, данные из нее просто копируются в соответствующую ячейку массива. Чтобы добавить запись с ключом 37, данные из нее просто копируются в 37 позицию в массиве. Чтобы найти запись с определенным ключом, просто выбирается соответствующая ячейка массива. Для удаления записи ключу соответствующей ячейки массива просто присваивается нулевое значение. Используя эту схему, можно добавить, найти и удалить элемент из массива за один шаг.
К сожалению, в реальных приложениях значения ключа не всегда находятся в небольшом диапазоне. Обычно диапазон возможных значений ключа достаточно велик. База данных сотрудников может использовать в качестве ключа идентификационный номер социального страхования. Теоретически можно было бы создать массив, каждая ячейка которого соответствовала одному из возможных девятизначных чисел; но на практике для этого не хватит памяти или дискового пространства. Если для хранения одной записи требуется 1 килобайт памяти, то такой массив занял бы 1 терабайт (миллион мегабайт) памяти. Даже если можно было бы выделить такой объем памяти, такая схема была бы очень неэкономной. Если штат вашей компании меньше 10 миллионов сотрудников, то более 99 процентов массива будут пусты.
=======281
Чтобы справиться с этой проблемой, схемы хеширования отображают потенциально большое число возможных ключей на достаточно компактную хеш‑таблицу. Если в вашей компании работает 700 сотрудников, вы можете создать хеш‑таблицу с 1000 ячеек. Схема хеширования устанавливает соответствие между 700 записями о сотрудниках и 1000 позициями в таблице. Например, можно располагать записи в таблице в соответствии с тремя первыми цифрами идентификационного номера в системе социального страхования. При этом запись о сотруднике с номером социального страхования 123‑45‑6789 будет находиться в 123 ячейке таблицы.
Очевидно, что поскольку существует больше возможных значений ключа, чем ячеек в таблице, то некоторые значения ключей могут соответствовать одним и тем же ячейкам таблицы. Например, оба значения 123‑45‑6789 и 12399‑9999 отображаются на одну и ту же ячейку таблицы 123. Если существует миллиард возможных номеров системы социального страхования, и таблица имеет 1000 ячеек, то в среднем каждая ячейка будет соответствовать миллиону записей.
Чтобы избежать этой потенциальной проблемы, схема хеширования должна включать в себя алгоритм разрешения конфликтов (collision resolution policy), который определяет последовательность действий в случае, если ключ соответствует позиции в таблице, которая уже занята другой записью. В следующих разделах описываются несколько различных методов разрешения конфликтов.
Все обсуждаемые здесь методы используют для разрешения конфликтов примерно одинаковый подход. Они вначале устанавливают соответствие между ключом записи и положением в хеш‑таблице. Если эта ячейка уже занята, они отображают ключ на какую‑либо другую ячейку таблицы. Если она также уже занята, то процесс повторяется снова о тех пор, пока в конце концов алгоритм не найдет пустую ячейку в таблице. Последовательность проверяемых при поиске или вставке элемента в хеш‑таблицу позиций называется [RV16] тестовой последовательностью (probe sequence).
В итоге, для реализации хеширования необходимы три вещи:
· Структура данных (хеш‑таблица) для хранения данных;
· Функция хеширования, устанавливающая соответствие между значением ключа и положением в таблице;
· Алгоритм разрешения конфликтов, определяющий последовательность действий, если несколько ключей соответствуют одной ячейке таблицы.
В следующих разделах описаны некоторые структуры данных, которые можно использовать для хеширования. Каждая из них имеет соответствующую функцию хеширования и один или более алгоритмов разрешения конфликтов. Так же, как и в большинстве компьютерных алгоритмов, каждый из этих методов имеет свои преимущества и недостатки. В последнем разделе описаны преимущества и недостатки разных методов, чтобы помочь вам выбрать наилучший для данной ситуации метод хеширования.
Один из методов разрешения конфликтов заключается в хранении записей, которые занимают одинаковое положение в таблице, в связных списках. Чтобы добавить в таблицу новую запись, при помощи функции хеширования выбирается связный список, который должен его содержать. Затем запись добавляется в этот список.
На рис. 11.1 показан пример связывания хеш‑таблицы, которая содержит 10 ячеек. Функция хеширования отображает ключ K на ячейку K Mod 10 в массиве. Каждая ячейка массива содержит указатель на первый элемент связного списка. При вставке элемента в таблицу он помещается в соответствующий список.
======282
@Рис. 11.1. Связывание
Чтобы создать хеш‑таблицу в Visual Basic, используйте оператор ReDim для размещения сигнальных меток начала списков. Если вы хотите создать в хеш‑таблице NumLists связных списков, задайте размер массива ListTops при помощи оператора ReDim ListTops(0 To NumLists - 1). Первоначально все списки пусты, поэтому указатель NextCell каждой метки должен иметь значение Nothing. Если вы используете для изменения массива меток оператор ReDim, то Visual Basic автоматически инициализирует указатели NextCell значением Nothing.
Чтобы найти в хеш‑таблице элемент с ключом K, нужно вычислить K Mod NumLists, получив индекс метки связного списка, который может содержать искомый элемент. Затем нужно просмотреть список до тех пор, пока искомый элемент не будет найден или процедура не дойдет до конца списка.
Global Const HASH_FOUND = 0
Global Const HASH_NOT_FOUND = 1
Global Const HASH_INSERTED = 2
Private Function LocateItemUnsorted(Value As Long) As Integer
Dim cell As ChainCell
' Получить вершину связного списка.
Set cell = m_ListTops(Value Mod NumLists).NextCell
Do While Not (cell Is Nothing)
If cell.Value = Value Then Exit Do
Set cell = cell.NextCell
Loop
If cell Is Nothing Then
LocateItemUnsorted = HASH_NOT_FOUND
Else
LocateItemUnsorted = HASH_FOUND
End If
End Function
Функции для вставки и удаления элементов из связных списков аналогичны функциям, описанным во 2 главе.
========283
Одно из преимуществ этого метода состоит в том, что при его использовании хеш‑таблицы никогда не переполняются. При этом вставка и поиск элементов всегда выполняется очень просто, даже если элементов в таблице очень много. Для некоторых методов хеширования, описанных ниже, производительность значительно падает, если таблица почти заполнена.
Из хеш‑таблицы, которая использует связывание, также просто удалять элементы, при этом элемент просто удаляется из соответствующего связного списка. В некоторых других схемах хеширования удалить элемент непросто или невозможно.
Один из недостатков связывания состоит в том, что если число связных списков недостаточно велико, то размер списков может стать большим, при этом для вставки или поиска элемента необходимо будет проверить большое число элементов списка. Если хеш‑таблица содержит 10 связных списков и к ней добавляется 1000 элементов, то средняя длина связного списка будет равна 100. Чтобы найти элемент в таблице, придется проверить порядка 100 ячеек.
Можно немного ускорить поиск, если использовать упорядоченные списки. Тогда можно использовать для поиска элементов в упорядоченных связных списках методы, описанные в 10 главе. Это позволяет прекратить поиск, если во время его выполнения встретится элемент со значением, большим искомого. В среднем потребуется проверить только половину связного списка, чтобы найти элемент или определить, что его нет в списке.
Private Function LocateItemSorted(Value As Long) As Integer
Dim cell As ChainCell
' Получить вершину связного списка.
Set cell = m_ListTops(Value Mod NumLists).NextCell
Do While Not (cell Is Nothing)
If cell.Value >= Value Then Exit Do
Set cell = cell.NextCell
Loop
If cell Is Nothing Then
LocateItemSorted = HASH_NOT_FOUND
ElseIf cell.Value = Value Then
LocateItemSorted = HASH_FOUND
Else
LocateItemSorted = HASH_NOT_FOUND
End If
End Function
Использование упорядоченных списков позволяет ускорить поиск, но не снимает настоящую проблему, связанную с переполнения таблицы. Лучшим, но более трудоемким решением будет создание хеш‑таблицы большего размера и повторное хеширование элементов в новой таблице так, чтобы связные списки в ней имели меньший размер. Это может занять довольно много времени, особенно если списки записаны на диске или каком‑либо другом медленном устройстве, а не в памяти.
========284
В программе Chain реализована хеш‑таблица со связыванием. Введите число списков в поле области Table Creation (Создание таблицы) на форме и установите флажок Sort Lists (Упорядоченные списки), если вы хотите, чтобы программа использовала упорядоченные списки. Затем нажмите на кнопку Create Table (Создать таблицу). Затем вы можете ввести новые значения и снова нажать на кнопку Create Table, чтобы создать новую хеш‑таблицу.
Так как интересно изучать хеш‑таблицы, содержащие большое число значений, то программа Chain позволяет заполнять таблицу случайными элементами. Введите число элементов, которые вы хотите создать и максимальное значение элементов в области Random Items (Случайные элементы), затем нажмите на кнопку Create Items (Создать элементы), и программа добавит в хеш‑таблицу случайно созданные элементы.
И, наконец, введите значение в области Search (Поиск). Если вы нажмете на кнопку Add (Добавить), то программа вставит элемент в хеш‑таблицу, если он еще не находится в ней. Если вы нажмете на кнопку Find (Найти), то программа выполнит поиск элемента в таблице.