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