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

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

Чому O(1):

1. Хеш-функція швидко обчислює індекс.
2. Елемент одразу поміщається в потрібну комірку (bucket).
3. Немає потреби перебирати інші елементи.

Але в найгіршому випадку:

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

Підсумок:

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