Hogyan értékeljük a hash-tábla olvasási műveleteinek hatékonyságát?

A hash-tábla olvasási műveleteinek hatékonyságát általában az elemhez való hozzáférés átlagos időkomplexitásával értékelik — ez O(1)-hez közelít, azaz állandó idő.

Ez a kulcs hash-függvényének kiszámításával érhető el, amely meghatározza az indexet a tömbben, ahol az érték tárolódik. Jó hash-függvény és alacsony ütközési arány esetén a keresés nagyon gyors.

Azonban a legrosszabb esetben, amikor sok ütközés van, az olvasási műveletek O(n)-re romolhatnak, ha minden elem ugyanabba a kosárba (bucket) kerül.

Az hatékonyság értékeléséhez általában a következőket nézik:

• Átlagos hozzáférési idő (amortizált)
• Ütközések száma
• A táblázat töltöttségi aránya (load factor)

Példa: C++-ban a std::unordered_map átlagos hozzáférési ideje O(1), de magas töltöttség esetén lassulhat.