Jaka jest złożoność wyszukiwania elementu po kluczu w HashMap?

Średnia złożoność to O(1), w najgorszym przypadku — O(n).

• Przypadek średni (O(1)): Przy dobrej funkcji hash i równomiernym rozłożeniu elementów po koszach (buckets), wyszukiwanie sprowadza się do obliczenia hash klucza i bezpośredniego dostępu do odpowiedniego kosza w tablicy. Wewnątrz kosza, jeśli nie ma kolizji, element znajduje się w czasie stałym.
• Przypadek najgorszy (O(n)): Występuje, gdy wszystkie elementy są haszowane do tego samego kosza. W takim przypadku wyszukiwanie zamienia się w liniowe przeszukiwanie listy powiązanej (lub w zbalansowanym drzewie w Java 8+ dla koszy z dużą liczbą elementów, ale nawet przejście przez drzewo może zająć O(log n), co przy wielu kolizjach w jednym koszu nadal zbliża się do O(n)).

Od Java 8, dla koszy zawierających więcej niż określony próg (TREEIFY_THRESHOLD, domyślnie 8) elementów, lista powiązana jest przekształcana w zbalansowane drzewo (drzewo czerwono-czarne). To poprawia najgorszy przypadek wyszukiwania w obrębie jednego kosza do O(log n), ale jeśli wszystkie klucze mają ten sam hash, ogólne wyszukiwanie nadal może być bliskie O(n).