Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Хешовані файли






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

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

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

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

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

‒ незв'язана область переповнення;

‒ зв'язана область переповнення;

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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.