Cum se determină complexitatea temporală a operației de adăugare a unui element într-un tabel hash?

Complexitatea temporară a operației de adăugare a unui element într-un tabel hash este în general considerată amortizată O(1). Aceasta înseamnă că, în medie, adăugarea se face în timp constant, deoarece elementul este plasat imediat în coșul corespunzător conform hash-ului. Cu toate acestea, în cel mai rău caz, dacă are loc o coliziune (mai mulți elemente în același coș), sau când este necesară extinderea tabelului (rehash), operația poate dura O(n) timp, unde n este numărul de elemente din tabel. Dar, datorită unui hash bun și controlului încărcării tabelului, astfel de cazuri sunt rare.