Hoe wordt de efficiëntie van het zoeken van een element op sleutel in een HashMap bij collisions beoordeeld?

In HashMap wordt het zoeken van een element op basis van de sleutel gemiddeld in O(1) tijd uitgevoerd, maar bij collisions hangt de efficiëntie af van de manier waarop deze worden afgehandeld.

Vroeger werden collisions afgehandeld met behulp van ketens (gelinkte lijsten), en in het ergste geval (wanneer alle sleutels in één bak terechtkomen) werd het zoeken O(n).

Vanaf Java 8 wordt, als het aantal elementen in één bak een bepaalde drempel overschrijdt, de gekoppelde lijst omgezet in een gebalanceerde boom (bijvoorbeeld een rood-zwart boom). Dit verbetert het ergste geval van zoeken naar O(log n) voor die bak.

Dus:

• Bij weinig collisions blijft het zoeken dicht bij O(1).
• Bij veel collisions in één bak wordt het zoeken O(log n).

Deze verbetering verhoogt de prestaties van HashMap aanzienlijk in ongunstige scenario’s.