Хеш-таблиця

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Хеш-таблиця — структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і здійснювати три операції: операцію додавання нової пари, операцію пошуку і операцію видалення за ключем.

Вступ[ред.ред. код]

Існує два основних варіанта хеш-таблиць: з ланцюжками і з відкритою адресацією. Хеш-таблиця містить в собі деякий масив H, елементи якого є пари (хеш-таблиця з відкритою адресацією) або списки пар (хеш-таблиця з ланцюжками).

Виконання операцій в хеш-таблиці починається з обчислення хеш-функції від ключа. Отримане хеш-значення i = \mbox{hash}(key) відіграє роль індексу в масиві H. Після цього операція (додавання, видалення, пошук) перенаправляється об'єктові, який зберігається у відповідній комірці масиву H[i].

Ситуація, коли для різних ключів отримується одне й те саме хеш-значення, називається колізією. Такі події непоодинокі — наприклад, при додаванні в хеш-таблицю розміром 365 комірок, усього лише 23-х елементів, ймовірність колізії вже перевищує 50 відсотків (якщо кожний елемент може з однаковою ймовірністю потрапити в будь-яку комірку)  — див. парадокс днів народження. Через це механізм розв'язання колізій — важлива складова будь-якої хеш-таблиці.

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

Властивості хеш-таблиці[ред.ред. код]

Важлива властивість хеш-таблиць полягає в тому, що при деяких розумних припущеннях, всі три операції (пошук, вставлення, видалення елементів) зазвичай виконується за час O(1). Але при цьому не гарантується, що час виконання окремої операції малий. Це пов'язано з тим, що при досягненні деякого значення коефіцієнта заповнення необхідно здійснювати перебудову індексу хеш-таблиці: збільшити розміри масиву H і заново додати в порожню хеш-таблицю всі пари.

Розв'язання колізій[ред.ред. код]

Існує декілька способів розв'язання колізій.

Метод ланцюжків[ред.ред. код]

Розв'язання колізій за допомогою ланцюжків.

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

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

При припущенні, що кожний елемент може потрапити в будь-яку позицію таблиці H з однаковою ймовірністю і незалежно від того, куди потрапив будь-який елемент, пересічний час роботи операції пошуку елемента складає Θ(1 + α), де α — коефіцієнт заповнення таблиці.

Відкрита адресація[ред.ред. код]

Приклад розв'язку колізій в хеш-таблиці з відкритою адресацією та лінійним перебором (інтервал = 1). Зауважте, «Ted Baker» має унікальне хеш-значення, але все одно утворює колізію з «Sandra Dee», яка перед цим створила колізію з «John Smith».

В стратегії, названій відкритою адресацією, всі записи зберігаються в самому масиві H. Коли додається новий запис, масив перевіряється в певному порядку доки не буде знайдена вільна комірка куди й вставиться елемент. У випадку пошуку елемента, масив сканується в тій самій послідовності доки потрібний запис або порожня комірка не буде знайдена, друге означає відсутність елемента.[1] Назва «відкрита адресація» показує, що розташування («адреса») елемента не визначається його хеш-значенням. Цей метод також називають закритим хешуванням.

В загальному випадку, послідовність в якій переглядаються комірки хеш-таблиці залежить тільки від ключа елемента, тобто це послідовність h0(x), h1(x), …, hn-1(x), де x — ключ елемента, а hi(x) — довільна функція, яка зіставляє кожен ключ комірки з хеш-таблицею. Перший елемент послідовності, зазвичай, дорівнює значенню деякої хеш-функції від ключа, а інші обчислюються від нього одним з наведених нижче способів. Для успішної роботи алгоритму пошуку, послідовність перебору має бути такою, щоб всі комірки хеш-таблиці виявились переглянутими рівно по одному разу.

Алгоритм пошуку переглядає всі комірку хеш-таблиці в тому самому порядку, що і при вставці, доки не знайдеться або елемент з шуканим ключем, або вільна комірка (що означає відсутність елемента в хеш-таблиці).

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

Нижче наведені деякі розповсюджені варіанти переборів. Одразу зауважимо, що нумерація елементів послідовності спроб і комірок хеш-таблиці при переборі ведеться від нуля, а N — розмір хеш-таблиці.

  • Лінійний перебір: комірки хеш-таблиці послідовно переглядаються з деяким фіксованим інтервалом k між комірками (зазвичай, k = 1), тобто i-й елемент послідовності — це комірка з номером (hash(x) + ik) mod N. Для того, щоб всі комірки виявились перебраними по одному разу, необхідно, щоб k було взаємно-простим з розміром хеш-таблиці.
  • Квадратичний перебір: інтервал між комірками з кожним кроком збільшується на константу. Якщо розмір хеш-таблиці дорівнює ступеню двійки (N = 2p), тоді одним з прикладів послідовності, за якою кожний елемент буде перебраний по одному разу є:
    hash(x) mod N, (hash(x) + 1) mod N, (hash(x) + 3) mod N, (hash(x) + 6) mod N, …
  • Подвійне хешування: інтервал між комірками фіксований, як при лінійному переборі, але, на відміну від нього, розмір інтервалу обчислюється другою, допоміжною хеш-функцією, тобто може бути різним для різним ключів. Значення цієї хеш-функції мають бути ненульовими і взаємно простими з розміром хеш-таблиці, що найпростіше всього зробити, якщо взяти просте число в якості розміру, і вимагати, щоб допоміжна хеш-функція приймала значення від 1 до N — 1.

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

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

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

Графік порівнює пересічну кількість втрат потрібних для пошуку елемента в таблиці методом ланцюжків і лінійним перебором. Коли таблиця завантажена більше ніж на 80%, ефективність лінійного перебору значно падає.

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

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

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

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

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

Виноски[ред.ред. код]

  1. Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. с. 456–461, pp. 472. ISBN 0-13-199746-7.