Що таке хеш-таблиця?

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

#Як це працює

1. Кожен ключ проходить через хеш-функцію, яка перетворює його на число - хеш.
2. Цей хеш вказує, в яку "комірку" (індекс) таблиці записати значення.
3. При пошуку того самого ключа хеш-функція обчислює той самий індекс, і елемент швидко знаходиться.

#Проблема колізій

Іноді різні ключі дають однаковий хеш - це колізія. Вирішується:

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

#Переваги

• швидкий доступ до даних - O(1) у середньому;
• просте додавання і видалення.

#Приклад

У Python це словник (dict), у Java - HashMap, у C++ - unordered_map.

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