Лекции и практики (1). Курс лекций и материалы для практических занятий
 Скачать 1.01 Mb.
|
Методы хешированияМногочисленные эксперименты с реальными данными выявили удовле- творительную работу двух основных типов хеш-функций. Один из них основан на делении, другой – на умножении. Все рассуждения ведутся в предположе- нии, что хеш-функция h(K): 0h(K)N для всех ключей K, где N – размер памя- ти (количество ячеек). Метод деления использует остаток от деления на М: h(K)= К mod M. (5.1) Если М – чётное число, то при чётных К значение h(K) будет чётным, и наобо- рот, что даёт значительные смещения значений функции для близких значений К. Нельзя брать М кратным основанию системы счисления машины, а также кратным 3. Вообще Мдолжно удовлетворять условию: М rk a , где k и a – небольшие числа, а r – "основание системы счисления" для боль- шинства используемых литер (как правило, 128 или 256), т.к. остаток от деле- ния на такое число оказывается обычно простой суперпозицией цифр ключа. Чаще всего в качестве М берут простое число, например, вполне удовлетвори- тельные результаты даёт М= 1009. Мультипликативный метод также легко реализовать. В соответствии с ним хеш-функция определяется так: h(K) A M wK mod 1 , (5.2) где w – размер машинного слова (обычно, 231); А – целое число простое по от- ношению к w; а M – некоторая степень основания системы счисления ЭВМ (2m). Таким образом, в качестве значения функции берутся Mправых значащих цифр дробной части произведения значения ключа и константы A/w. Преиму- щество второго метода перед первым обусловлено тем, что произведение обычно вычисляется быстрее, чем деление. При использовании любых методов хеширования для размещения запи- сей должен быть выделен участок памяти размером N. Для того чтобы полу- ченное в результате значение h(K) не вышло за границы отведённого участка памяти, окончательно адрес записи вычисляется так: А(К) = h(K) mod N. (5.3) Разрешение коллизийСлучай, когда для двух и более ключей выдаётся одинаковый адрес, называется коллизией. Наличие коллизий снижает эффективность хеширова- ния. Разрешение коллизий достигается путём рехеширования – специального алгоритма, который используется каждый раз при размещении новой записи или при поиске существующей, если возникла коллизия. В системах баз данных рехеширование выполняется одним из следующих способов: Открытая адресация: новая запись размещается вслед за последней запи- сью на данной странице или на следующей, если страница заполнена. (Для последней страницы памяти следующей является первая страница). Поиск записи осуществляется также последовательно, откуда следует, что записи нельзя удалять физически (с освобождением памяти), иначе цепочка рехе- шированных записей прервётся, и часть записей может быть "потеряна". Использование коллизионных страниц: новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в области переполнения). Для ускорения поиска рехешированных записей может использоваться свя- занная область переполнения, для которой на странице хранится ссылка на коллизионную страницу. Нулевое значение такой ссылки говорит об отсут- ствии коллизий для данных, размещённых на этой странице. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страни- цах) применяется другая функция хеширования. Примечание: значения ключа хеширования не обязательно должны быть уникальными. В реальных базах данных в качестве адреса записи может выступать адрес блока (стра- ницы памяти), в котором размещается несколько записей, возможно, с одинаковым значением ключа. Коллизией в этом случае является ситуация переполнения блока, адрес которого получен в результате применения функции хеширования к значению ключа новой записи. Тогда система выполнит для этой записи рехеширование. |