Wat is de complexiteit van het zoeken van een element op sleutel in een HashMap?

Gemiddelde complexiteit is O(1), in het slechtste geval is het O(n).

• Gemiddelde geval (O(1)): Met een goede hashfunctie en een uniforme verdeling van elementen over de buckets, komt zoeken neer op het berekenen van de hash van de sleutel en directe toegang tot de bijbehorende bucket in de array. Binnen de bucket, als er geen collisions zijn, wordt het element in constante tijd gevonden.
• Slechtste geval (O(n)): Treedt op wanneer alle elementen in dezelfde bucket worden gehasht. In dat geval wordt zoeken een lineaire zoektocht in een gekoppelde lijst (of in een gebalanceerde boom in Java 8+ voor buckets met veel elementen, maar zelfs het doorlopen van de boom kan O(log n) kosten, wat bij veel collisions nog steeds naar O(n) neigt).

Vanaf Java 8 wordt voor buckets met meer dan een bepaalde drempel (TREEIFY_THRESHOLD, standaard 8) elementen de gekoppelde lijst omgezet in een gebalanceerde boom (Rode-zwart boom). Dit verbetert de slechtste geval zoekprestaties binnen één bucket naar O(log n), maar als alle sleutels dezelfde hash hebben, kan de algemene zoekactie nog steeds dicht bij O(n) liggen.