Хешування
Найпростішим прикладом хеш-функції може бути залишок від розподілу на підібране просте число значення, що міститься в хеш-полі.
Хешування відрізняється від індексування тим, що у файлі може бути будь-яка кількість індексів, але тільки одна структура хешування.
Очевидний і недолік хешування в наведеному вище прикладі. Справа в тому, що фізична послідовність записів всередині файлу, що зберігається, майже завжди відрізняється від послідовності ключового поля, а також будь-якої іншої логічно заданої послідовності. До того ж між послідовно розміщеними записами можуть бути проміжки невизначеної протяжності.
Розглянемо як приклад алгоритм хешування з урахуванням ключового поля, який вирішує проблему колізій. Алгоритм полягає в тому, що при використанні хешування запис міститься в першу вільну ділянку блоку, номер якого є функцією значення первинного ключа запису. Наявність вільних ділянок встановлюється за допомогою булевої змінної, яка є обов'язковим полем кожного запису. Якщо блоці немає вільних ділянок, запис поміщається у спеціальний блок, званий блоком переповнення.
Отже, нехай як функція хешуванняhвикористовується залишок від поділу на 13. Наприклад, застосування цієї функції до цілих чисел у полі первинного ключа дає:h(39)= 0;h(62)= 10;h(5)=5. Ця функція хешування дозволяє отримати значення в діапазоні від 0 до 12, ідентифікуючи цим 13 блоків. Нехай кожен блок можна помістити 8 записів. Тоді, якщо файл містить 72 записи, простір, виділений для зберігання, буде на дві третини заповнено даними.
Щоб включити до файлу новий запис, потрібно за допомогою лінійного пошуку в блоці, номер якого визначаєтьсязначенням h, знайти запис із дійсним значенням поля НЕТЗАПИСИ. Після цього на місце знайденого запису треба помістити новий. Якщо при спробі помістити новий запис у файл виявляється, що в знайденому блоці немає запису з НЕТЗАПИСИ=TRUE, кажуть, що блок переповнений. Дещо пізніше буде описана реакція на переповнення.
Для видалення запису з файлу треба, використовуючи метод лінійного пошуку, спробувати виявити його в блоці, номер якого дорівнює h (значення первинного ключа). Якщо запис буде знайдено, потрібно встановити НЕТЗАПИСИ =TRUE; якщо ні, то очевидно, що блок переповнений і необхідно продовжити пошук. Перед тим, як заповнити файл записами, необхідно встановити НЕТЗАПИСИ =TRUEдля всіх записів всіх блоків.
Якщо потрібно модифікувати запис, потрібно знайти цей запис і замінити старе значення на нове. Жодних інших змін не потрібно.
Для боротьби з переповненням можуть бути використані три методи: пов'язаних у ланцюг блоків; пов'язаних у ланцюг записів та прогресуючого переповнення.
Метод блоків, пов'язаних у ланцюгполягає в наступному. Коли блок переповнюється, в ньому розміщується покажчик, що посилається на новостворений блок, призначений виключно для записів, що не помістилися до першого блоку. Бажано цей новостворений блок розмістити в тому ж циліндрі. Якщо новостворений блок, у свою чергу, переповнений, в ньому розміщується покажчик, що посилається на ще один новостворений блок, і т.д. В результаті буде сформовано пов'язаний список блоків, для всіх записів якого значення функції хешування однаково.
Якщо необхідно включити у файл новий запис, а в блоці призначеному для цього місця немає, цей запис поміщається в перший блок переповнення, в якому є вільнемісце. Після цього треба ще включити цей запис у пов'язаний список записів з тим самим значенням функції хешування. Такий метод отримав назву методузаписів, пов'язаних у ланцюг.
Метод прогресуючого переповненнябагато в чому схожий на другий метод. Єдина відмінність полягає в тому, що записи в блоках переповнення не поєднуються у зв'язані списки. У тому випадку, якщо в блоці, номер якого визначається значенням функції хешування, немає місця, запис поміщається в перший вільний простір блоку переповнення. Цей блок містить записи з різними значеннями функції хешування.
Для пошуку запису потрібно спочатку організувати доступ до основного блоку. Якщо шуканого запису там немає, необхідно, використовуючи метод лінійного пошуку, переглядати блоки переповнення доти, доки запис не буде виявлено. У цьому випадку будуть проглядатися навіть записи, які мають інші значення функції хешування. Зазначимо, що другий метод має більш високу швидкодію, ніж третій, оскільки обмежує пошук тільки записами з тим самим значенням функції хешування, що й шуканий запис. Але третій метод вимагає пам'яті менше, ніж другий, оскільки немає необхідності зберігати покажчики. З іншого боку, третій метод простіше у реалізації.
Вибір функції хешування здійснюється у певному сенсі довільно. Для вибору "хорошої" функції хешування необхідно знати, по-перше, приблизна кількість записів у файлі і, по-друге, скільки записів можна поміщати в блок. Ця інформація буде використовуватися для підрахунку числа блоків у файлі, на основі якого можна визначити діапазон зміни значень функції хешування. Якщо для файлу буде відведено замало блоків, то ефективність доступу буде зменшуватися в міру переповненняцих блоків. Якщо, навпаки, для розміщення файлу буде передбачено багато блоків, то переповнення блоків відбуватиметься рідко і, отже, доступ буде здійснюватися швидко. Значна частина пам'яті у разі залишиться не зайнятої даними. Прагнемо до золотої середини, тобто. вважати, що приблизно дві третини блоків мають бути зайняті даними.
Функція хешування повинна бути обрана таким чином, щоб максимально задовольняти наступні умови:
Кожне її значення має бути цілим з інтервалу 0.. число блоків у файлі 1
Вона має бути зручною обчислення, тобто. визначення значення функції хешування має відбуватися швидко
Для безлічі реально значень первинного ключа, що реально з'являються, всі значення функції хешування повинні бути рівноймовірні.
Якщо h( ) повністю задовольняє останній умові, то кажуть, що h перемішує значення ключа. Перемішування дозволяє досягти того, щоб усі блоки містили приблизно однакову кількість записів. Якщо умова перемішування не виконується, то частина блоків може переповнюватися, тоді як інші блоки міститимуть лише невелику кількість записів, і в результаті ефективність доступу може виявитися нижчою, ніж при перемішуванні.
Зауважимо, що будь-якому ключу (не лише числовому) можна зіставити чисельне значення. Наприклад, літери можна інтерпретувати як цілі числа діапазоні 0…33, тобто. А = 0, Б = 1 тощо. Тоді числове значення БВ53 дорівнюватиме (1*33*33 + 2*33)*100 +53.
Крім згаданого вже поділу на просте число можна як значення функції хешування використовувати кілька цифр значення ключа. Можна також брати зі значення ключа два (або більше) підмножини цифр, формувати з цифр кожного підмножини число тавикористовувати суму цих чисел як значення функції хешування. Функції хешування такого типу складніші для обчислення, ніж функція використовує кілька цифр ключа, але водночас забезпечує краще перемішування. Крім того, значення такої функції можуть бути обчислені швидше ніж значення функції, для побудови якої використовується розподіл на просте число.
Коли програма знаходить у файлі потрібне значення ключа, кажуть, що отримано відповідь. У процесі груповий обробки потрібно знайти кілька значень ключа, тобто. отримати кілька відповідей. Введемо коефіцієнт активності як відношення числа відповідей до записів у файлі БД.
Типовим прикладом, у якому коефіцієнт активності близький до одиниці, є обчислення зарплати під час обробки платіжних відомостей: кожна (чи майже кожна) запис у файлі обробляється.
Вважатимемо, що має місце довільний доступ, коли потрібно знайти лише один запис файлу. І тут коефіцієнт активності близький до нуля.