Kaip vertinama elemento įterpimo į žemės ūkio lentelę efektyvumas įvairiomis sąlygomis?

Hash lentelės elementų įterpimo efektyvumas priklauso nuo kelių veiksnių:

1. Užpildymo koeficientas (load factor) — santykis tarp elementų skaičiaus ir masyvo dydžio. Esant žemam užpildymui, įterpimas dažniausiai vyksta amortizuotu laiku O(1).

2. Hash funkcijos kokybė — vienodas raktų paskirstymas minimalizuoja susidūrimus.

3. Susidūrimų valdymas:

   • Su grandinėlėmis (chaining), įterpimas reiškia pridėjimą prie susietojo sąrašo ar kito konteinerio į dėžutę. Vidutiniškai O(1), bet blogiausiu atveju O(n), jei visi elementai patenka į tą pačią dėžutę.
   • Su atvira adresacija (linear probing, quadratic probing), įterpimas gali reikalauti ieškoti laisvos vietos, kas padidina laiką esant dideliam užpildymui.

4. Rehash — pasiekus užpildymo ribą, lentelė išplečiama, kas reikalauja elementų perdėliojimo ir laikinai padidina įterpimo laiką.

Apibendrinant: su gera hash funkcija ir saikingu užpildymu, įterpimas yra amortizuotas O(1). Esant dideliam užpildymui ar blogai hash funkcijai, laikas gali blogėti iki O(n).