Kako se određuje vremenska složenost operacije umetanja elementa u HashMap?

Vremenska složenost operacije umetanja elementa u HashMap u Javi je u proseku O(1), odnosno konstantno vreme. To se postiže korišćenjem hash funkcije za brzo određivanje pozicije.

Međutim, u najgorem slučaju, ako dođe do kolizije i svi elementi padnu u isti korpu (bucket), umetanje može degradirati do O(n), gde je n broj elemenata u toj korpi.

Od Java 8, pri velikom broju kolizija, korpa se pretvara iz povezane liste u uravnoteženo drvo (TreeMap), što poboljšava najgori slučaj na O(log n).

Primer:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42); // prosečno O(1) umetanje