Milyen feltételek mellett van a HashMap műveletek időbeli komplexitása arányos a gyűjtemény méretével?

A HashMap műveletei (például, get, put) általában amortizált időbonyolultsággal O(1). Azonban bizonyos esetekben a bonyolultság O(n)-re nőhet, ahol n a gyűjtemény mérete. Ez akkor fordul elő, ha:

• Minden kulcs egy kosárba (bucket) kerül rossz hash függvény miatt, ami hosszú listához vagy fához vezet egy cellában.
• A kollíziók nem egyenletesen oszlanak el, és a belső adatstruktúra degradálódik.

Java 8-tól és újabb verzióktól kezdve, ha egy kosárban túl sok elem van, a HashMap a láncolt listát egy kiegyensúlyozott fára (TreeNode) alakítja, ami a legrosszabb esetben O(log n)-re csökkenti, de nem O(1)-re.

Ezért a műveletek a gyűjtemény méretéhez arányosan alakulnak, erős kollíziók és rossz hash-eloszlás esetén.