Адресация данных с использованием методов перемешивания (хеширования)

Адресация данных с использованием методов перемешивания (синонимы — методы хеширования, рассеянной памяти, случай­ного доступа) в настоящее время является наиболее распростра­ненным вариантом построения адресных функций, использу­ющих в качестве аргумента значение ключа записи. Известная всем аббревиатура RAM, приводимая всюду при указании характери­стик памяти персональных ЭВМ, означает Random Access Memory — память случайного доступа. Заметим, что название метода вполне удачно (от англ. hash — путаница, мешанина) и весьма точно характеризует идею метода.

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

224

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

Следовательно, необходимо разработать специальную функцию, рационально распределяющую память и удовлетворяющую неко­торым требованиям.

Рассмотрим требования, предъявляемые к хеш-функциям.

Пусть требуется адресовать if записей. При этом условии хеш-функция h должна:

1) иметь не более М разных значений и удовлетворять следу­
ющему условию

О < h(k) < М - 1

для любого к из К, т. е. для всего множества значений ключа К, должно однозначно определяться значение адреса h по ключу к;

2) равномерно распределять записи реального файла в преде­лах выделенного участка памяти;

3) быть легко вычислима.

Наиболее используемыми методами /«-адресации являются ме­тоды срединных квадратов и методы, основанные на делении и умножении. Заметим, что эти же методы используются всегда, когда нужно получить псевдослучайные числа (ПСЧ) (см. под-разд. 20.1).

Метод срединных квадратов (авторы Дж. фон Нейман и Н. Мет­рополии 1946). Сущность метода определяется операцией выде­ления п средних цифр из числа, полученного возведением в квад­рат ключа записи.

Пример. Рассмотрим пример из подразд. 17.1. Пусть ключ — совокуп­ность полей {HP; ДВ}:

К_х = 0001001; К\ = 0000001002001; Л, = 00100; К₂ = 0008001; К\ = 0000064016001; А₂ = 06401; К_ъ = 0911002; К] = 0829924644004; А₃ = 92464;

Ki = 0203125; Kj= 0041259765625; А, = 25976.

В этом случае:

A⁽&_H = A_lk_m = A,- 0,18300.

Л<й_н=18;^)_н=П71ит.д., где £_масш — коэффициент масштабирования.

225

Метод, основанный на делении. Расчетная формула метода име­ет вид:

А = h(k) = k(modm),

т. е. адрес записи вычисляется путем деления по модулю т ее клю­ча.

Решающее значение имеет выбор числа т (на это обратил внимание еще автор этого и других конгруэнтных методов Д. Ле-мер):

1) если т — четное число, то значение h(k) всегда будет чет­ным при четном значении к и нечетным при нечетном числе к;

2) если т равно степени основания системы счисления, то h(k) зависит только от самых правых разрядов к и не зависит от других;

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

На практике рекомендуется в качестве т выбирать простое чис­ло, близкое к размеру участка памяти.

Метод, основанный на умножении. Расчетная формула метода имеет вид:

А_ош = h(k) = f(k)M,

где f(k) — хеш-функция, дающая псевдослучайный адрес в ин­тервале [0; 1]; М — размер участка памяти, выделенный для хра­нения информации.

Пример. Пусть ключ — совокупность полей {HP; ДВ} (см. пример в подразд. 17.1).

Тогда коэффициент масштабирования к_тт = 0001001, к_тах = 999 366-М= 18 300.

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

• полученная с помощью хеширования последовательность рас­положения в памяти хранимых записей не совпадает с последова­тельностью, определяемой первичным ключом;

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

Различают следующие методы разрешения коллизий:

1) открытой адресации:
. линейное опробование;

• двойное хеширование;

2) метод цепочек.

226

Линейное опробование. Сущность метода проста — организуется циклическая последовательность адресов следующего вида:

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

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

Этому методу свойствен один принципиальный (методический) недостаток — возможность так называемого «вторичного скучива-ния», под которым понимают возможность новых коллизий.

Попытка исключить недостаток вызвала к жизни другой метод — двойное хеширование.

Двойное хеширование. Идея метода такая же, как у предыдуще­го, но смещение адреса осуществляется не на единицу, а на пере­менную величину

D=f(A(J)),

где/— хеш-функция (как правило, отличная от К).

Считывание проводится так же, как и при линейном опробо­вании.

Метод цепочек. Идея метода состоит в том, что организуют М линейных списков: по одному на каждый возможный хеш-адрес. Вся память разбивается на две части — основную область и об­ласть перемешивания (на практике на область перемешивания выделяют 20 —30 % основной области). Область перемешивания и предназначена для хранения линейных списков.

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

Если нет, переходят (по указателю) к следующему и далее до конца списка.

227

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

Несмотря на присущее такой адресации нерациональное (из­быточное) использование памяти, описанным образом адресу­ются данные практически во всех современных персональных ЭВМ, характеристики которых позволяют некоторый перерасход ресур­са памяти для разрешения коллизий и исключения сбоев в разме­щении и поиске данных.

РАЗДЕЛ III

⇐ Предыдущая34353637383940414243Следующая ⇒

Поделиться: