Jak ocenia się wydajność wyszukiwania elementu po kluczu w HashMap przy kolizjach?

W HashMap wyszukiwanie elementu po kluczu odbywa się średnio w czasie O(1), ale przy kolizjach skuteczność zależy od metody obsługi tych kolizji.

Wcześniej kolizje obsługiwano za pomocą łańcuchów (list powiązanych), a w najgorszym przypadku (gdy wszystkie klucze trafiają do tego samego kosza) wyszukiwanie stawało się O(n).

Od Java 8, jeśli liczba elementów w jednym koszu przekracza określony próg, lista powiązana jest przekształcana w zrównoważone drzewo (np. drzewo czerwono-czarne). To poprawia najgorszy przypadek wyszukiwania do O(log n) dla tego kosza.

Zatem:

• Przy niewielkiej liczbie kolizji wyszukiwanie pozostaje bliskie O(1).
• Przy dużej liczbie kolizji w jednym koszu, wyszukiwanie będzie O(log n).

To ulepszenie znacznie zwiększa wydajność HashMap w niekorzystnych scenariuszach.