16. Хеширование. Постановка задачи, коэффициент заполнения таблицы.
Хеширование - преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.
Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
В главе 4 подробно обсуждалась следующая основная проблема: если задан набор элементов, характеризующихся ключом (который определяет отношение порядка), то как организовать этот набор, чтобы извлечение элемента с заданным ключом требовало наименьших усилий? Ясно, что в конечном счете доступ к каждому элементу в памяти компьютера осуществляется указанием его адреса в памяти. Поэтому вышеуказанная проблема по сути сводится к нахождению подходящего отображения Н ключей (К) в адреса (А):
Н: К-->А
В главе 4 это отображение реализовалось с помощью различных алгоритмов поиска в списках и деревьях на основе разных способов организации данных. Здесь мы опишем еще один подход, простой по сути и во многих случаях очень эффективный. Затем мы обсудим и некоторые его недостатки.
В этом методе данные организуются с помощью массива. Поэтому Н является отображением, преобразующим ключи в индексы массива, откуда и происходит название преобразование ключей, нередко используемое для этого метода. Заметим, что здесь на не понадобятся процедуры динамического размещения; массив является одной из фундаментальных, статических структур. Метод преобразования ключей часто используют в тех задачах, где с примерно равным успехом можно применить и деревья.
Число хранимых элементов, делённое на
размер массива
(число
возможных значений хеш-функции),
называется коэффициентом заполнения
хеш-таблицы (load factor) и является важным
параметром, от которого зависит среднее
время выполнения операций.
17. Хеш-функция: требования к ней, коллизии и синонимы. Основная теорема.
Фундаментальная трудность при использовании преобразования ключей заключается в том, что множество возможных значений ключей гораздо больше, чем множество доступных адресов в памяти (индексов массива). К примеру, возьмем имена длиной до 16букв в качестве ключей, идентифицирующих отдельных людей во множестве из тысячи человек. Здесь есть 26^16 возможных значений ключей, которые нужно отобразить на 103 возможных индексов. Очевидно, что функция Н отображает несколько значений аргументов в одно значение индекса. Если задан ключ к, то первый шаг операции поиска состоит в вычислении соответствующего индекса h = H(k), а второй - очевидно, обязательный - шаг состоит в проверке того, что действительно ли элемент с ключом к соответствует элементу массива (таблицы) Т с индексом h, то есть выполняется ли равенство Т[Н(к)].кеу = к. Мы сразу сталкиваемся с двумя вопросами:
1. Какую функцию Н надо взять?
2. Что делать, если Н не смогла вычислить адрес искомого элемента?
Ответ на второй вопрос состоит в том, чтобы использовать метод, который даст альтернативную позицию, скажем индекс h и если там по-прежнему нет искомого элемента, то третий индекс h", и т. д. (Такие попытки обозначаются ниже как пробы (probe) - прим. перев.) Ситуацию, когда в вычисленной позиции находится элемент, отличный от искомого, называют коллизией; задача порождения альтернативных индексов называется разрешением коллизий. Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не имеющую коллизий. Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины, коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных будет бесконечно — и любые два набора данных из этого множества образуют коллизию, а эти наборы данных будут называться синонимами.
Рассмотрим в качестве примера хеш-функцию H(x)=x mod 19, определенную на множестве целых чисел. Её область значений состоит из 19, а область определения — бесконечна. Так как множество прообразов заведомо больше множества значений, коллизии обязаны существовать.
Построим коллизию для этой хеш-функции для входного значения 38, хеш-сумма которого равна нулю. Так как функция H(x)— периодическая с периодом 19, то для любого входного значения y, значение y + 19 будет иметь ту же хеш-сумму, что и y. В частности, для входного значения 38 той же хеш-суммой будут обладать входные значения 57, 76, и т. д. Таким образом, пары входных значений (38,57), (38,76) образуют коллизии хеш-функции H(x)