3. Дайте визначення такої структури даних як «хеш-таблиця» і наведіть класифікацію, приклади.

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

Існує два основних варіанти хеш-таблиць: з ланцюжками і відкритої адресацією.

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

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

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

Ситуація, коли для різних ключів виходить одне і те ж хеш-значення, називається колізією (collision).

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

Властивості хеш таблиці

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

Читати фонетично

4. Опишіть способи реалізації хеш-функції (перетворення ключа в індекс).

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

Метод ділення

Хеш код вираховується діленням ключа по модуль ділення значення ключа на розмірність Самої таблиці.

Приклад 100/3=33->2⁵-2⁶->(37)

Метод добутку

Ключ множиться на деяку константу із діапазона від 0 до 1 потім виділяються дробова частини, яка множиться на розмірність хеш – таблиці)

Метод універсального хеширування

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

5. Опишіть способи вирішення колізії в хеш-таблицях з відкритою адресацією.

Коллизии осложняют использование хеш-таблиц, так как нарушают однозначность соответствия между хеш-кодами и данными. Тем не менее, существуют специальные методики для преодоления возникающих сложностей:

Открытая адресация: В отличие от хеширования с цепочками, при открытой адресации никаких списков нет, а все записи хранятся в самой хеш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NULL.

Дилення множення

Множенян (сначала множиться)

Универсальна (декилька фукций)

Линийне квадретне, идеальнее.

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

Пряма адресація

У масиві H зберігаються списки пар. Колізії просто приводять до того, що з'являються списки довжиною більше одного елемента.

Середній час виконання операцій у хеш-таблиці з прямою адресацією одно коефіцієнту заповнення.

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

А) ідеальне хешування

Б) лінійне хешування

В) подвійне хешування

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

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