Hash tables

У більшості комп'ютерних мов множинні дані та картографічні структури реалізуються за допомогою хеш-таблиць. Обидві мови Python та Go постачаються з попередньо реалізованими словниками та картами хеш-таблиць, тоді як C++ та Java включають їх до своїх стандартних бібліотек.

• Хеш-таблиці зберігають дані, пов'язуючи ключі зі значеннями у невпорядкованому наборі.

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

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

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

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

Хешування

В обчисленнях хешування - це метод, за допомогою якого ключові значення масиву можуть бути перетворені в послідовність індексів. Щоб отримати набір допустимих значень, слід використовувати оператор по модулю. Розглянемо 20-байтну хеш-таблицю, в якій потрібно зберігати наступні значення. Елементи відформатовані у вигляді (ключі та значення).

Основні процедури

Ось основні фундаментальні операції хеш-таблиці:

• Пошук елемента в хеш-таблиці.
• Функція Вставка в хеш-таблицю використовується для вставки елемента в хеш-таблицю.
• Видалити видаляє запис з хеш-таблиці.

Зіткнення хешів

Колізія хешування відбувається, коли хеш-функція видає однаковий індекс для декількох ключів.

Ми можемо вирішити цю проблему одним із наступних способів:

1. Вирішення колізій за допомогою ланцюжка; або
2. Відкрита адресація.

Вирішення колізій за допомогою ланцюжків

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

Якщо j представляє слот для декількох елементів, він містить посилання на заголовок списку. Якщо жодного елемента немає, j містить NIL.

Відкрите звернення

Відкрита адресація, на відміну від ланцюгової, не зберігає декілька компонентів в одному слоті. Кожен слот або заповнюється одним ключем, або залишається порожнім.

У відкритому зверненні використовуються такі стратегії:

• Лінійне зондування

При лінійному зондуванні колізії вирішуються шляхом дослідження наступного слоту.

h(k, i) = (h′(k) + i) mod m

де i = 0, 1,...

h'(k) - нова хеш-функція

Якщо в h(k, 0) є зіткнення, то розглядається h(k, 1). Таким чином, кількість i лінійно збільшується.

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

• Квадратичне зондування

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

h (k, i) = (h(k) + c1 i + c2 i2) mod m

де c1 та c2 - додатні сталі,

i = 0, 1,...

• Подвійне хешування

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

h (k, i) = (h1 (k) + ih2 (k)) mod m

Постійна зміна розміру амортизованого часу

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

• Виділено більшу таблицю;
• Попередня таблиця очищується по одному запису;
• І додається до нової таблиці.

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