Hogyan értékeljük egy elem beszúrási műveletének hatékonyságát különböző körülmények között?

Az elem hozzáadásának hatékonysága egy hash-táblába több tényezőtől függ:

1. A tömb terhelési tényezője (load factor) — az elemek száma és a tömb mérete közötti arány. Alacsony terhelésnél az beszúrás általában amortizált O(1) idő alatt történik.

2. A hash függvény minősége — az kulcsok egyenletes eloszlása minimalizálja az ütközéseket.

3. Ütközések kezelése:

   • Láncolás esetén (chaining) a beszúrás egy láncolt lista vagy más tároló hozzáadását jelenti a vödörben. Átlagosan O(1), de a legrosszabb esetben O(n), ha minden elem ugyanabba a vödörbe kerül.
   • Nyitott címzésnél (lineáris keresés, kvadratikus keresés) a beszúrás szabad hely keresését igényli, ami magas terhelésnél növeli az időt.

4. Rehashing — amikor eléri a terhelési küszöböt, a táblát bővítik, ami az elemek újraelosztását igényli, és ideiglenesen növeli a beszúrási időt.

Röviden: jó hash függvénnyel és mérsékelt terheléssel a beszúrás amortizált O(1), magas terhelés vagy rossz hash függvény esetén az idő O(n)-re romolhat.