Чому хеш-таблиця забезпечує швидкий доступ до даних?

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

Як це відбувається:

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

Тобто замість перебору всіх елементів (O(n)) виконується лише одне обчислення і одне звернення до пам'яті (O(1) у середньому).

Приклад:

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

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