Ako sa určuje a hodnotí zložitosť pridania nového prvku do dátovej štruktúry HashMap?

Pridaní nového prvku do HashMap sa zvyčajne odhaduje ako amortizované O(1). To znamená, že priemerná operácia vkladania trvá konštantný čas bez ohľadu na veľkosť štruktúry.

HashMap používa hashovaciu funkciu na výpočet indexu vedra (bucket), kam sa prvok umiestni. Ak v vedre nie sú kolízie, prvok sa pridá rýchlo. Pri kolíziách (keď viacero kľúčov má rovnaký hash) sú prvky uložené v zozname alebo strome, čo môže v najhoršom prípade zvýšiť čas vkladania na O(n).

Okrem toho, keď sa dosiahne určitý faktor zaťaženia (load factor), dôjde k prehashovaniu (rehashing), čo dočasne zvýši čas vkladania.

Príklad v Jave (Android):

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // amortizované O(1)

Vo väčšine prípadov je pridanie nového prvku efektívne, ale v zriedkavých prípadoch môže byť drahšie kvôli kolíziám alebo prehashovaniu.