Aká je časová zložitosť operácií nad prvkami v HashMap, a HashMap garantuje uvedenú zložitosť pri výbere prvku?

Časová zložitosť základných operácií (get, put, remove, containsKey) v HashMap je v priemere O(1).

Toto sa dosahuje použitím hash tabuľky, kde sú prvky uložené v bunkách (kbelíkoch), určených hash kódom kľúča. V ideálnom prípade každý kbelík obsahuje len jeden prvok.

Avšak, v najhoršom prípade, keď všetky kľúče majú rovnaký hash kód alebo dochádza k mnohým kolíziám, sa prvky dostanú do toho istého kbelíka. V takom prípade sa kbelík môže zmeniť na prepojený zoznam (do Java 8) alebo strom (Java 8 a vyššie, ak počet prvkov v kbelíku presiahne určitý prah). Operácie na takom kbelíku majú časovú zložitosť O(n), kde n je počet prvkov v ňom.

HashMap nezaručuje konštantnú časovú zložitosť O(1) pri načítaní prvku. Zaručuje len priemernú časovú zložitosť O(1). V najhoršom prípade môže byť zložitosť O(n).

Faktory ovplyvňujúce časovú zložitosť:

• Kvalita hash funkcie: Dobrá hash funkcia rovnomerne rozdeľuje kľúče po kbelíkoch, minimalizujúc kolízie.
• load factor (koeficient zaťaženia): Určuje, ako veľmi môže byť hash tabuľka zaplnená, než dôjde k jej zväčšeniu (rehash). Vysoký load factor môže zvýšiť pravdepodobnosť kolízií.
• Počiatočná kapacita: Veľmi malá počiatočná kapacita pri veľkom počte prvkov spôsobí časté rehash operácie, čo je náročná operácia.