Статичне хеширування

План

1. Хеширування. Види хеширування.

2. Конфлікти. Методи для вирішення конфліктів.

3. Відкрита адресація.

4. Пов’язана та непов’язана область переповнення.

5. Багатократне хеширування.

6. Обмеження, які властиві методу хеширування.

Хешування (Hashing) – алгоритмічне перетворення значень деякого поля записів (первинного ключа або будь-якого іншого поля) в адреси їх розміщення на зовнішньому носієві.

При введенні даних СКБД обчислює адресу сторінки, на якій зберігатиметься запис, і заносить запис на цю сторінку. При виконанні запитів реалізуються аналогічні розрахунки адреси сторінки з подальшим читанням записів з цієї сторінки. Перевагою такого методу є швидкий прямий доступ до даних. При цьому час доступу практично не залежить від кількості записів, що зберігаються.

В хешированому файлі записи не обов’язково повинні заноситися в файл послідовно. Замість цього для обчислення адреси сторінки, на якій повинен знаходитися запис, використовується хеш-функція (hash function), параметрами якої є значення одного або декількох полів цього запису. Подібне поле називається полемхеширування (hash field), а якщо поле є також ключовим полем файлу, то воно називається хеш-ключом (hash key). Записи в хешированому файлі розподілені довільним чином по всьому припустимому для файлу простору. За цією причиною хешировані файли іноді називають файлами з довільним або прямим доступом (random file або direct file).

Хеш-функція обирається таким чином, щоб записи всередині файлу були розподілені найрівномірніше. Один з методів створення хеш-функції називається сверткою (folding) та оснований на виконанні деяких арифметичних дій над різними частинами поля хеширування. При цьому символьні рядки перетворюються в цілі числа з використанням деякого кодування (на основі розташування букв в алфавиті або кодів символів ASCII). Наприклад, можна перетворити в ціле число перші два символи поля табельного номеру співробітника (атрибут staffNo), а потім скласти отримане значення з цифрами цього номеру, які залишилися. Обчислена сума використовується в якості адреси дискової сторінки, на якій буде зберігатися даний запис. Найпопулярнішим є альтернативний метод оснований на хешуванні з використанням залишку від ділення. В цьому методі використовується функція MOD, якій передається значення поля. Функція ділить отриманне значення на деяке раніш задане ціле число, після чого залишок від ділення використовується в якості адреси на диску.

Недоліком більшості хеш-функцій є те, що вони не гарантують отримання унікальної адреси, оскільки кількість можливих значень поля хеширування може бути значно більшою за кількість адрес, припустимих для записів. Кожна обчислена хеш-функцією адреса відповідає деякій сторінці, або сегменту (bucket), з декількома комірками (слотами), які призначені для декількох записів. В межах одного сегменту записи розміщуються в слотах в порядку вступу. Тот випадок, коли одна й та ж адреса генерується для двох або більшої кількості записів, називається конфліктом або колізією (collision), a подібні записи - синонімами. В цій ситуації новий запис необхідно вставити в іншу позицію, оскільки місто з обчисленою для неї хеш-адресою вже зайняте. Вирішення конфліктів ускладнює супроводження хешируваних файлів та знижує загальну продуктивність їх роботи.

Для вирішення конфліктів можна використовувати наступні методи:

1. відкрита адресація;

2. непов’язана область переповнення;

3. пов’язана область переповнення;

4. багатократне хеширування.

Відкрита адресація

При виникненні конфлікту система виконує лінійний пошук першого припустимого слоту для вставки в нього нового запису. Після невдалого пошуку порожнього слоту в останньому сегменті пошук продовжується з першого сегменту. При відборі запису використовується такий же метод, який застосовувався при збереженні запису, за виключенням того, що запис в даному випадку розглядається як не існуючий, якщо до виявлення іскомого запису буде виявлений порожній слот.

На перший погляд може здатися, що цей підхід не дає більшого виграшу в продуктивності. Однак при найдетальнішому аналізі виявляється, що при використанні відкритої адресації конфлікти, які були усунені за допомогою першого вільного слоту, можуть визвати додаткові конфлікти з записами, які будуть мати хеш-значення, яке дорівнює адресі цього перед тим вільного слоту. Таким чином, кількість конфліктів буде збільшуватися, а продуктивність - зменшуватися. С іншого боку, якщо кількість конфліктів вдасться звести до мінімуму, то лінійний пошук в малій області переповнення буде виконуватися досить швидко.

Пов ’ язана область переповнення

Як й в попередньому методі, в цьому методі для вирішення конфліктов з записами, які не можуть бути розміщені в слоті з їх адресою хеширування, використовується область переповнення. Однак в даному методі кожному сегменту виділяється додаткове поле, яке іноді називається вказівником синоніму. Воно визначає наявність конфлікту та вказує сторінку в області переповнення, яка використовується для його вирішення. Якщо вказівник дорівнює нулю, то жодних конфліктів немає.

Для найшвидшого доступу до запису переповнення можна використовувати вказівник синоніму, який вказує на адресу слоту всередині області переповнення, а не на адресу сегменту. Записи всередині області переповнення також мають вказівники синоніму, які містять в області переповнення адреси наступного синоніму для такої ж адреси, тому всі синоніми однієї ж адреси можуть бути вилучені за допомогою ланцюжка вказівників.

Дата добавления: 2014-01-04