Хеширование. Хешированные файлы

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

Принцип хеширования заключается в том, что для определения адреса записи в области хранения к значению ключевого поля этой записи применяется так называемая хеш-функция h(K). Она преобразует значение ключа K в адрес участка памяти (это называется свёрткой ключа). Новая запись будет размещаться по тому адресу, который выдаст хеш-функция для ключа этой записи. При поиске записи по значению ключа K хеш-функция выдаст адрес, указывающий на начало того участка памяти, в котором надо искать эту запись.

Хеш-функция h(K) должна обладать двумя основными свойствами:

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

K₁≈K₂⇒h(K₁)>>h(K₂) V K₂>>h(K₁)

1. для разных значений ключа выдавать разные адреса:

K₁≠K₂⇒h(K₁)≠h(K₂)

Второе требования является сложно выполнимым. Трудно подобрать такую хеш-функцию, которая для любого распределения значений ключа всегда выдавала бы разные адреса для разных значений. Для реальных функций хеширования допускается совпадение значений функции h(K) для различных ключей. Для разрешения неопределённости при совпадении адресов после вычисления h(K) используются специальные методы (см. раздел 4.5.3.2).

Недостаток методов подбора хеш-функций заключается в том, что количество данных и распределение значений ключа должны быть известны заранее. Также методы хеширования неудобны тем, что записи обычно неупорядочены по значению ключа, что приводит к дополнительным затратам, например, при выполнении сортировки. К преимуществам хеширования относится то, что ускоряется доступ к данным по значению ключа. Обращение к данным происходит за одну операцию ввода/вывода, т.к. значение ключа с помощью хеш-функции непосредственно преобразуется в адрес соответствующей записи (или адрес блока памяти, в котором хранится эта запись). При этом не нужно создавать никаких дополнительных структур (типа индекса) и тратить память на их хранение.

Методы хеширования

Многочисленные эксперименты с реальными данными выявили удовле-творительную работу двух основных типов хеш-функций. Один из них основан на делении, другой – на умножении. Все рассуждения ведутся в предположении, что хеш-функция h(K): 0 ≤ h(K) ≤ N для всех ключей K, где N – размер памяти (количество ячеек).

Метод деления использует остаток от деления на М:

h(K)= К mod M (4.1)

Если М – чётное число, то при чётных К значение h(K) будет чётным, и наоборот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще, М должно удовлетворять условию:

M ≠r^k±a,

где k и a – небольшие числа, а r – "основание системы счисления" для большинства используемых литер (как правило, 128 или 256), т.к. остаток от деления на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетворительные результаты даёт М = 1009.

Мультипликативный метод также легко реализовать. В соответствии с ним хеш-функция определяется так:

(4.2)

где w – размер машинного слова (обычно, 2³¹); А – целое число простое по отношению к w; а M – некоторая степень основания системы счисления ЭВМ (2^m). Таким образом, в качестве значения функции берутся M правых значащих цифр дробной части произведения значения ключа и константы A/w. Преимущество второго метода перед первым обусловлено тем, что произведение обычно вычисляется быстрее, чем деление.

При использовании любых методов хеширования для размещения записей должен быть выделен участок памяти размером N. Для того чтобы полученное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так:

А(К) = h(K) mod N (4.3)

Разрешение коллизий

Случай, когда для двух и более ключей выдаётся одинаковый адрес, называется коллизией. Наличие коллизий снижает эффективность хеширования.

Разрешение коллизий достигается путём рехеширования – специального алгоритма, который используется каждый раз при размещении новой записи или при поиске существующей, если возникла коллизия. В системах баз данных рехеширование выполняется одним из следующих способов:

1. Открытая адресация: новая запись размещается вслед за последней запи-сью на данной странице или на следующей, если страница заполнена. (Для последней страницы памяти следующей является первая страница). Поиск записи осуществляется также последовательно, откуда следует, что записи нельзя удалять физически (с освобождением памяти), иначе цепочка рехешированных записей прервётся, и часть записей может быть "потеряна".
2. Использование коллизионных страниц: новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в области переполнения). Для ускорения поиска рехешированных записей может использоваться связанная область переполнения, для которой на странице хранится ссылка на коллизионную страницу. Нулевое значение такой ссылки говорит об отсутствии коллизий для данных, размещённых на этой странице
3. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страни-цах) применяется другая функция хеширования.

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

Использование хеширования

Хеширование таблицы полезно в следующих случаях:

• В таблице есть уникальный ключ, и большинство запросов обращаются к записям по значению этого ключа, например:

SELECT FROM WHERE unique_key = ;

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

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

Хеширование не рекомендуется в следующих случаях:

• Нельзя сразу выделить столько памяти, сколько требуется таблице. Если потребуется выделять таблице дополнительную память, эта память будет отведена под коллизионные страницы, что сильно ухудшит производительность (это следует из формулы (4.3), по которой рассчитывается адрес записи)./li>
• Большинство запросов выбирают записи в некотором интервале значений ключа. Хеширование не даёт здесь преимуществ, т.к. записи обычно не упорядочены, и система использует последовательное чтение.

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

Кластеризация данных