Яка складність доступу до елемента в хеш-таблиці?

Середня часова складність доступу (пошуку) до елемента в хеш-таблиці - O(1), тобто постійний час.

Чому O(1):

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

У найгіршому випадку: Якщо всі елементи дали однаковий хеш (максимальні колізії), усі вони опиняться в одному кошику, і пошук перетвориться на O(n) - потрібно пройти весь ланцюжок.

Підсумок:

• Середня складність: O(1)
• Найгірша складність: O(n)
• Амортизовано (на практиці): O(1) при хорошій хеш-функції та збалансованій таблиці.