Геш-таблиця (hash table, hash map) — структура даних, що дозволяє зберігати пари (ключ, значення) і здійснювати три операції за ключем:
- додавання нової пари
- пошук
- видалення
Геш-таблиця працює швидше за список де O(n), і представляє собою масив з геш-функцією
У масива на 1 000 000 000 ключів – будуть використовуватися не всі комірки, і ми маємо стиснути цей діапазон функцією
Ключ (string) -> hesh code map (int) -> comprasion map (int в малому діапазоні) hash function
dog = god – сума кодів цифр в ANSI однакова – виходить колізія
Колізію усувають методами:
- Відкрита адресація – дублюючі ключі додаємо вкінці таблиці, в найгіршому варіанті перебравши усі елементи отримуємо O(n)
- Метод ланцюжків – додаються в однозв’язний список кожного елементу за постійну одиницю часу O(1 + розмір списку)