Способы размещения данных в памяти, основанные на преобразовании ключа записи в ее адрес, обеспечивают прямой доступ к данным по значению ключа. Адрес хранения записи в этом случае определяется с помощью некоторой процедуры, выполняемой над ключом записи или над кодом записи. Время обращения к любой записи при таком способе хранения не зависит от места расположения записи в памяти.
Способ размещения по вычисляемому адресу используется для размещения данных как в основной памяти – таблицы с прямым доступом, так и при хранении данных на ВЗУ – файлы с прямым доступом.
Для вычисления адресов используются различные процедуры, выполняющие линейные или нелинейные преобразования ключа записи или ее кода. В результате преобразования может определяться физический адрес записи, индекс элемента массива, содержащего запись, номер записи в файле.
Функция, выполняющая процедуру над ключом и генерирующая адрес записи, называется функцией преобразования. В литературе по обработке данных такие функции часто называют рандомизирующими функциями (от англ. random access – произвольный доступ). Основное требование, предъявляемое к функции преобразования, состоит в том, что она должна генерировать уникальный адрес для каждой записи.
При выборе функции преобразования оценивается характер данных.
В тех случаях, когда все записи информационного массива имеют
-фиксированную длину,
-уникальные последовательные значения ключа,
-диапазон возможных значений ключа не превышает диапазона адресов доступной памяти,
можно подобрать линейную функцию, обеспечивающую однозначность преобразования ключа в адрес хранения записи с этим ключом.
Пусть, например, необходимо разместить в ОП 50 записей фиксированной длины, ключи которых принимают значения от 0201 до 0250. Диапазон значений ключа – 50. Для хранения записей используем структуру массива. Объявим массив на 50 элементов. Таким образом выделим для хранения записей адреса с1 по 50.
В этом случае для вычисления адресов (индексов массива) можно использовать следующее преобразование:
ai = ki - p
Здесь ki - значение ключа записи; ai – адрес записи, т.е. индекс элемента массива, в котором размещена запись с ключом ki; Р – некоторое положительное число.
Выберем Р = 200. Тогда запись с ключами К=0211 и К=0241 будут занимать соответственно 11 и 41 позиции в массиве. Таким образом, для размещения и последующего обращения к любой записи потребуется значение ее ключа пересчитать в индекс массива, после чего к любой записи возможет прямой доступ из программы.
Реальные данные не всегда удовлетворяют перечисленным условиям, и линейные функции преобразования оказываются непригодными. Так, например, если значения ключа не последовательны и имеют большой разброс значений, то при использовании линейной функции многие ячейки памяти останутся незанятыми. Для вычисления адресов в этих случаях используют более сложные функции преобразования. В большинстве случаев для вычисления адресов оказываются пригодными функции хеширования или хеш-функции. Это название происходит от англ. глагола to hash (нарезать, крошить, делать месиво). Хеш-функция хеширует, т.е. крошит на мелкие кусочки и определенным образом их перемешивает последовательность цифр или битов, определяющих значение ключа записи или ее кода. В результате получается адрес ячейки памяти, где будет размещена эта запись.
Рассмотрим, как работает функция хеширования, преобразующая ключ по методу свертки. Эта функция разбивает ключ на несколько частей, которые затем суммируются таким образом, чтобы сформировалось число в требуемом диапазоне (в диапазоне допустимых значений адресов). Пусть, например, записи имеют восьмиразрядные ключи К1=97434658 и К2=31269857, которые необходимо преобразовать в трехразрядные адреса. Эту задачу можно решить, выполнив следующие операции:
h (97434658) = 974 + 346 + 58 = 378
h (31269857) = 312 + 698 + 57 = 067
Здесь символ h означает, что обработку ключа выполняет хеш-функция. Для того чтобы вычисляемые адреса были трехразрядными, сложение производится по модулю 1000. Результатом сложения по mod 1000 является остаток от деления суммы на 1000.
Функция хеширования должна удовлетворять следующим требованиям:
- вычисляемые адреса должны быть уникальными;
- функция должна обеспечивать однозначное преобразование ключа записи в ее адрес (данному ключу всегда должен соответствовать один и тот же адрес);
- необходимо, чтобы полученные адреса возможно более равномерно распределялись по памяти;
- хеш-функция не должна быть слишком сложной, т.к. время, необходимое для преобразования, добавляется ко времени выполнения операций ведения, поиска или обработки.
Хорошей считается такая хеш-функция, которая быстро генерирует уникальные и достаточно равномерно распределенные адреса.
Известны различные хеш-функции, каждая из которых дает хорошие результаты при конкретном распределении значений ключа. Но даже самая лучшая хеш-функция не исключает возможность получения одинаковых адресов для разных значений ключа. Почти неизбежны ситуации, когда различные записи получают один и тот же адрес. Такая ситуация называется коллизией.
Рассмотрим, как одна из наиболее распространенных функций хеширования, основанная на методе деления, приводит к возникновению коллизий.
Эта функция имеет следующий вид:
h (K) = K mod m + 1.
Здесь m – делитель. Для вычисления h(K) ключ записи К делится на m и остаток от деления, равный K mod m, увеличивается на 1.
Выберем m = 101 и выполним преобразования h (K) над ключами 2000, 2001, …, 2017. Получатся адреса 82, 83, , 99. Теперь рассчитаем адреса записей для ключей 3313,.3314, …, 3330. Получим те же самые адреса, т.е. возникает коллизия.
Существуют различные методы разрешения коллизий.
При использовании одного из них хеш-адрес, вступивший в коллизию, подвергается рехешированию, заключающемуся в определенном преобразовании этого адреса. Например, полученный адрес может быть умножен на константу, в результате чего будет получен новый адрес. Подобные преобразования могут выполняться неоднократно до тех пор, пока не будет сгенерирован адрес свободной ячейки памяти. При поиске записи будет выполняться та же последовательность преобразований.
Другой метод разрешения коллизий заключается в использовании сгенерированного адреса в качестве начальной точки для дальнейшего последовательного просмотра ячеек памяти. Начиная с этого адреса, производится поиск свободного места в памяти, куда размещается запись, вступившая в коллизию
На практике наиболее часто используется следующий прием, позволяющий разрешать коллизии. Адрес, генерируемый рандомизирующей процедурой, считается при этом адресом хранения не одной конкретной записи, а адресом областипамяти, или страницы памяти.