Kuidas määratakse aja kulu uute elementide sisestamisel hash-tabelisse?

Hash-tabelisse elemendi sisestamise ajakulu hinnatakse tavaliselt amortiseeritud O(1) tasemele, mis tähendab, et sisestamine võtab keskmiselt konstantse aja.

Seda saavutatakse:

• Kiire hash-funktsiooni arvutamisega indeksi määramiseks.
• Kiire juurdepääsuga massiivi rakule.

Kuid halvimates tingimustes (näiteks kokkupõrgete korral, kui mitu võtit langevad samasse korvi) võib sisestamine degrada kuni O(n)-ni, kui kasutatakse seotud nimekirja kokkupõrgete salvestamiseks.

Kaasaegsed rakendused (näiteks Java HashMap) kui kokkupõrgete arv on suur, lähevad tasakaalustatud puudele, mis vähendab halvimat juhtumit O(log n)-ni.

Seega sõltub ajakulu hash-funktsiooni tõhususest, kokkupõrgete arvust ja andmestruktuurist, mida kasutatakse kokkupõrgete lahendamiseks.