Na čo vplývajú kolízie v HashMap?

Kolízie v HashMap ovplyvňujú výkon operácií get, put a remove.

Pri veľkom počte kolízií sú prvky s rovnakými hash kódmi uložené vo forme prepojenej zoznamu alebo stromu v rámci jedného koša.

Takto to ovplyvňuje výkon:

Operácie s košmi: Vyhľadávanie prvku v koši s veľkým počtom kolízií sa z ideálneho O(1) mení na O(n) pre prepojené zoznamy a O(log n) pre stromy (po Java 8, keď je v koši dostatok prvkov), kde n je počet prvkov v danom koši.
Zvýšenie priemerného času prístupu: Ak nie sú kolízie rovnomerne rozložené, niektoré koše sa preplnia, čo zvyšuje priemerný čas potrebný na prístup k prvku.
Strata výhod hashovania: Pri veľmi veľkom počte kolízií, keď väčšina prvkov padne do niekoľkých košov, sa HashMap môže zhoršiť na výkon podobný prepojenému zoznamu alebo stromu pri vyhľadávaní.

Kvalita práce HashMap veľmi závisí od kvality hash funkcie kľúčov: čím lepšie sú hash kódy rozložené, tým menej kolízií bude a tým vyšší výkon.

Koeficienty load factor a initial capacity tiež ovplyvňujú frekvenciu prebudovania tabuľky (rehashing) a tým aj pravdepodobnosť výskytu kolízií a ich vplyv na výkon. Vysoký load factor môže viesť k častejším kolíziám, nízky zase k plytvaniu pamäťou.