Jak se hodnotí efektivita hledání prvku podle klíče v HashMap při kolizích?

V HashMap je hledání prvku podle klíče průměrně trvá čas O(1), ale při kolizích závisí efektivita na způsobu jejich řešení.

Dříve se kolize řešily pomocí řetězců (spojených seznamů), a v nejhorším případě (když všechny klíče spadnou do jednoho koše) bylo hledání O(n).

Od Java 8, pokud počet prvků v jednom koši přesáhne určitý práh, spojový seznam se převede na vyvážené stromové struktury (například červené-černé stromy). To zlepšuje nejhorší případ hledání na O(log n) pro tento koš.

Takže:

• Při malém počtu kolizí zůstává hledání blízko O(1).
• Při velkém počtu kolizí v jednom koši bude hledání O(log n).

Toto vylepšení výrazně zvyšuje výkon HashMap v nepříznivých scénářích.