Как се определя времевата сложност на операцията по добавяне на елемент към хеш таблица?

Временната сложност на операцията за добавяне на елемент в хеш таблица обикновено се счита за амортизирана O(1). Това означава, че средно добавянето става за постоянен време, тъй като елементът веднага се поставя в съответната кофа според хеша. Въпреки това, в най-лошия случай, ако се случи колизия (няколко елемента попадат в една и съща кофа), или когато е необходимо разширяване на таблицата (rehash), операцията може да отнеме O(n) време, където n е броят на елементите в таблицата. Но благодарение на доброто хеширане и контрол на натоварването на таблицата, такива случаи са редки.