Ako sa určuje časová zložitosť operácie pridania prvku do hash tabuľky?

Časová zložitosť operácie pridania prvku do hash tabuľky sa zvyčajne považuje za amortizovanú O(1). To znamená, že v priemere sa pridanie vykonáva v konštantnom čase, pretože prvok je okamžite umiestnený do príslušného vedra (kádra) podľa hash. Avšak v najhoršom prípade, ak dôjde ku kolízii (viaceré prvky v tom istom vedre), alebo keď je potrebné rozšíriť tabuľku (rehash), operácia môže trvať O(n) času, kde n je počet prvkov v tabuľke. Vďaka dobrému hashovaniu a kontrole zaťaženia sú také prípady zriedkavé.