Jaká je časová složitost operací nad prvky v HashMap, a HashMap garantuje-li uvedenou složitost při výběru prvku?

Časová složitost základních operací (get, put, remove, containsKey) v HashMap je v průměru O(1).

Toho se dosahuje použitím hashtable, kde jsou prvky uloženy v buňkách (kbelících), určených hash kódem klíče. V ideálním případě každý kbelík obsahuje pouze jeden prvek.

Nicméně, v nejhorším případě, kdy všechny klíče mají stejný hash kód, nebo dochází k mnoha kolizím, se prvky dostanou do stejného kbelíku. V takovém případě se kbelík může změnit na spojový seznam (do Java 8) nebo strom (Java 8 a výše, pokud počet prvků v kbelíku přesáhne určitý práh). Operace na takovém kbelíku mají časovou složitost O(n), kde n je počet prvků v kbelíku.

HashMap nezaručuje konstantní časovou složitost O(1) při načítání prvku. Zaručuje pouze průměrnou časovou složitost O(1). V nejhorším případě může být složitost O(n).

Faktory ovlivňující časovou složitost:

• Kvalita hash funkce: Dobrá hash funkce rovnoměrně rozděluje klíče do kbelíků, minimalizuje kolize.
• load factor (koeficient zatížení): Určuje, jak moc může být hash tabulka zaplněná, než dojde k jejímu zvětšení (rehash). Vysoký load factor může zvýšit pravděpodobnost kolizí.
• Počáteční kapacita: Příliš malá počáteční kapacita při velkém počtu prvků způsobí časté rehashování, což je náročná operace.