Матеріал з Вікіконспекти
При частому додаванні нових значень в хеш-таблицю може виникнути ситуація, коли хеш-таблиця стає повністю заповненою і потрібно перехешіровать її. При малих розмірах хеш-таблиці повне перехешірованія не викличе труднощів. При великих розмірах хеш-таблиці це вимагає великої кількості часу, також якщо значення надходять дуже часто, то потрібно часто перехешіровать таблицю або виділяти величезні обсяги пам'яті, які можуть і не знадобитися, а отже вони просто зарезервує даремно. Також в стандартній хеш-таблиці може статися колізія (два різних значення надходять в одну клітинку). Щоб вирішити ці проблеми, а також щоб не виділяти багато додаткової пам'яті можна використовувати розширюване хешування.
[Ред] Структура і алгоритм
Метод расширяемого хеширования (англ. Extendible hashing) полягає в тому, що хеш-таблиця представлена як каталог (англ. Directory), а кожна клітинка буде вказувати на ємність (англ. Bucket) яка має певну місткість (англ. Capacity). Сама хеш-таблиця буде мати глобальну глибину (англ. Global depth), а кожна з ємностей має локальну глибину (англ. Local depth). Глобальна глибина показує скільки останніх біт будуть використовуватися для того щоб визначити в яку ємність слід заносити значення. А з різниці локальної глибини і глобальної глибини можна зрозуміти скільки осередків каталогу посилаються на ємність. Це можна показати формулою де - глобальна глибина, - локальна глибина, а кількість посилань осередків. Для пошуку ємності використовується цифрове дерево.
Тепер розглянемо сам алгоритм якщо нам надійшло деяке значення:
- Переводимо значення в двійковий вигляд, дивимося на останні бітів і вирішуємо в яку ємність відправити значення.
- Якщо ємність має вільне місце, то поміщаємо туди значення без всяких турбот, якщо ж ємність куди слід покласти значення переповнена, то Дивіться на локальну глибину ємності:
- Якщо вона менше ніж глобальна глибина то значить на ємність є кілька покажчиків і нам досить перехешіровать її, розділивши при цьому на дві і занести значення в нові дві ємності збільшивши у цих ємностей локальну глибину на.
- Якщо ж локальна глибина дорівнювала глобальної то ми збільшуємо глобальну глибину на, подвоюючи при цьому кількість осередків, створено додаткове ознакування міста на ємності, а також збільшуємо кількість останніх біт за якими ми розподіляємо значення. Далі локальна глибина переповненій ємності стає менше і ми повторюємо попередній алгоритм тобто перехешіруем ємність, розділимо її на дві ємності і так далі.
[Ред] Приклад
Розглянемо алгоритм на прикладі.
Нехай у нас є якийсь каталог зі своїми покажчиками і ми хочемо додати значення (дивись малюнок №1) де - глобальна глибина, - локальні глибини ємностей, а місткість ємностей дорівнює.
Першим на вхід надходить значення. Уявімо його в двійковому вигляді:. Закінчення відповідає другому осередку значить дивимося на другу ємність. У ній є вільне місце і ми просто поміщаємо в неї (дивись малюнок №2). На цьому робота з закінчена.
Далі на вхід надходить значення. Уявімо його в двійковому вигляді:. Це значення закінчується на і має піти у першу ємність, але перша ємність повністю заповнена. Отже ми дивимося на локальну глибину першої ємності тобто на. а значить слідуючи вище описаного алгоритму ми повинні подвоїти кількість осередків каталогу, збільшити глобальну глибину, потім збільшити кількість останніх біт за якими ми розкидаємо значення на і перехешіровать першу ємність, розділивши її на дві, збільшивши локальну глибину і розмістивши значення за новими ємностей (дивись малюнок №3). На цьому робота з закінчена.
Останнім на вхід надходить значення. Уявімо його в двійковому вигляді:. Останні біта () відповідають третьої ємності, але вона також повністю заповнена як і в другому випадку, але її локальна глибина менше ніж глобальна глибина, а отже нам треба тільки перехешіровать ємність, розділивши її на дві, збільшивши локальну глибину і розмістивши значення за новими ємностей (дивись малюнок №4). На цьому робота з закінчена.
[Ред] Використання
Найчастіше розширюване хешування використовується в базах даних так як. Бази даних можуть бути вкрай великими і перехешірованія всієї бази даних займе тривалий час при цьому позбавляючи користувачів доступу до бази даних. А при використанні расширяемого хеширования перехешіровать доведеться тільки малі групи, що не сильно уповільнить роботу бази даних. Також розширюване хешування добре працює в умовах динамічно змінюваного набору записів в доглянутому файлі.