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

Сжатие порядкового индексирования с помощью хеш-функции

Ясно, что создание массива из миллиарда элементов для хранения информации о тысяче сотрудников неприемлемо. При этом нам очень хочется иметь высокую производительность и скорость доступа к информации о каждом конкретном сотруднике за постоянное время, не зависящее от числа элементов в структуре данных. Как вариант, можно использовать для номерации записей сотрудников не весь номер социального страхования целиком, а лишь его последние 4 цифры. Таким образом, вместо массива, простирающегося от элемента номер 000-00-0000 до 999-99-9999-го элемента, мы получим массив с диапазоном элементов от 0000 до 9999. На рисунке 8 показан такой "урезанный" массив.

Рисунок 8. Урезанный массив

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

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

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

H(x) = последние 4 цифры числа x

На вход H подается любой 9-значный номер социального страхования. На выходе мы имеем четырехзначное число, которое состоит из последних 4 цифр входного числа. В математических терминах, H осуществляет отображение (maps) множества 9-значных номеров социального страхования на множество 4-значных чисел, как показано на рис. 9.

Рисунок 9. Иллюстрация действия хеш-функции

Рисунок 9 демонстрирует, помимо прочего, явления, присущие всем хеш-функциям, называемые коллизиями (collisions). Коллизия - это явление, когда хеш-функция отображает 2 разных элемента из более широкого множества в один и тот же элемент более узкого множества. В нашем случае все номера социального страхования, оканчивающиеся на 0000, отобразятся хеш-функцией в 0000. Т.е. значением хеш-функции для 000-00-0000, 113-14-0000, 933-66-0000 и многих других номеров будет одно и то же число - 0000.

Возвращаясь назад к содержанию нашего примера, рассмотрим, что случится, если мы попытаемся добавить запись о новом сотруднике, номер которого 123-00-0191. Очевидно, что при этом у нас возникнут проблемы, поскольку в массиве уже существует сотрудник в ячейке с номером 0191 (Jisun Lee).

Математическое примечание Хеш-функция в более строгих математических терминах может быть определена как функция f : A -> B (А и B - конечные множества). Поскольку мы имеем, что |A| > |B|, то очевидно, что f не является взаимно-однозначной функцией. Следовательно, будут иметь место коллизии.

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

Избегание и разрешение коллизий

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

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

Примечание Тщательный анализ хеш-функции требует некоторых знаний из области математической статистики, что выходит за рамки этой статьи. Главным образом требуется, чтобы вероятность выбора каждого конкретного значения из области значений хеш-функции для хеш-таблицы с k ячейками равнялась 1/k. (Если вы почти ничего не поняли - не очень смущайтесь!)

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

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

1. Когда новый элемент добавляется в хеш-таблицу, используем хеш-функцию, чтобы определить, в какое место таблицы следует записать этот элемент.
2. Проверяем, существует ли элемент в позиции, найденной на шаге 1 с помощью хеш-функции. Если позиция свободна, помещаем туда элемент, в противном случае идем на шаг 3.
3. Пусть номер позиции, выданный хеш-функцией - i. Тогда мы проверяем, занята ли позиция с номером i + 1. Если и она занята, то проверяем позицию i + 2 и так далее до тех пор, пока не найдем свободную ячейку.

Рассмотрим пример, когда мы поместили в таблицу записи о следующих 4 сотрудниках: Alice (333-33-1234), Bob (444-44-1234), Cal (555-55-1237), Danny (000-00-1235) и Edward (111-00-1235). После занесения этих данных в хеш-таблицу последняя будет выглядеть, как показано на рис. 10.

Рисунок 10. Хеш-таблица с 4 сотрудниками с похожими номерами

Номер социального страхования Алисы хешируется в значение 1234 и ее запись помещается в 1234-й элемент массива. Далее, номер Боба тоже хешируется в 1234, однако ячейка 1234 уже занята записью Алисы, таким образом Боб занимает следующую свободную ячейку - 1235. После Боба мы добавляем запись Кэла, хеш-функция выдает для его номера социального страхования значение 1237. Поскольку в ячейке 1237 никого нет, запись Кэла помещается в нее. Следующий - Дэнни. Его номер отображается хеш-функцией в 1235. Поскольку позиция 1235 занята, проверяется ячейка с номером 1236. Т.к. ячейка 1236 вакантна, Дэнни записывается в нее. В конце добавляется запись Эдварда, его номер социального страхования также хешируется в 1235. Поскольку 1235 занята, проверяется 1236. Она также занята, проверяем 1237. Эта ячейка занята Кэлом, и мы проверяем 1238, которая оказывается свободной. Итак, запись Эдварда добавляется в ячейку 1238.

Из-за коллизий возникают проблемы и при поиске в хеш-таблице. Например, представим, что нам нужно найти в хеш-таблице из предыдущего примера информацию об Эдварде. Мы берем номер социального страхования Эдварда 111-00-1235, хешируем его, получаем 1235 и начинаем поиск. В ячейке 1235 мы находим Боба, а не Эдварда. Таким образом, нам нужно теперь проверить ячейку 1236, но там Дэнни. Наш линейный поиск будет продолжаться либо до тех пор, пока мы не найдем Эдварда, либо когда мы дойдем до пустой ячейки. Последнее будет означать, что в хеш-таблице не существует сотрудника с номером социального страхования 111-00-1235.

Несмотря на то, что линейная последовательность проб - простая процедура, она является не лучшим способом разрешения коллизий, поскольку ведет к образованию кластеров (clustering). Поясним это понятие. Представим, что первые 10 сотрудников, которых мы добавили в хеш-таблицу, все имеют номер социального страхования, заканчивающийся на одни и те же 4 цифры, скажем, 3344. Тогда будут заняты 10 последовательных ячеек массива от 3344 до 3353. При попытке поиска данных любого из этих 10 сотрудников будет происходить процесс линейной последовательности проб. Более того, добавление сотрудников, для которых значение хеш-функции лежит в интервале от 3345 до 3353 приведет к дальнейшему разрастанию кластера. Для быстрого поиска, конечно же, лучше иметь равномерное распределение данных в хэш-таблице, а не кластеризованное в окрестности некоторых точек.

Более сложной является квадратичная последовательность проб (quadratic probing), которая начинает проверять ячейки на квадратичном расстоянии друг от друга. То есть в случае, если ячейка s занята, то вместо проверки ячейки s + 1, а за ней s + 2 и т.д., как в линейной последовательности проб, сначала проверяется ячейка (s + 1)2, затем (s - 1)2, потом (s + 2)2, затем (s - 2)2, после этого (s + 3)2 и так далее. Однако даже квадратичный вариант может привести к образованию кластеров.

В следующем разделе мы рассмотрим третий метод разрешения коллизий, называемый повторным хешированием (rehasing). Этот метод используется классом Hashtable из .NET Framework.