W jakich warunkach operacje w HashMap mają złożoność czasową proporcjonalną do rozmiaru kolekcji?

Operacje w HashMap (np. get, put) zazwyczaj mają amortyzowaną złożoność czasową O(1). Jednak w niektórych przypadkach złożoność może wzrosnąć do O(n), gdzie n to rozmiar kolekcji. Dzieje się tak, jeśli:

• Wszystkie klucze trafiają do jednego kosza (bucket) z powodu złej funkcji haszującej, co prowadzi do długiej listy lub drzewa w jednej komórce.
• Kolizje są nierównomiernie rozłożone, a struktura danych wewnątrz kosza się degraduje.

W Java 8 i nowszych, jeśli w jednym koszu jest zbyt wiele elementów, HashMap zamienia listę powiązaną na zrównoważone drzewo (TreeNode), co zmniejsza najgorszy przypadek do O(log n), ale nie do O(1).

W związku z tym operacje stają się proporcjonalne do rozmiaru kolekcji przy silnych kolizjach i złym rozkładzie funkcji haszujących.