Jak je určena doba přístupu k prvku ve struktuře dat HashMap?

Doba přístupu k prvku ve struktuře dat HashMap v Javě se obvykle považuje za konstantní — O(1). Toho je dosaženo použitím hash funkce, která převádí klíč na index pole, kde je hodnota uložena.

Nicméně v praxi může doba přístupu vzrůst až na O(n) v nejhorším případě, pokud dochází k mnoha kolizím (různé klíče se stejným hashem), a prvky jsou uloženy v spojovém seznamu nebo stromu uvnitř jedné buňky.

Od Java 8 je pro snížení doby přístupu při kolizích spojový seznam transformován na vyvážený strom (TreeMap), což snižuje dobu hledání na O(log n) v takových případech.

Celkově je průměrná doba přístupu blízko O(1), ale v nejhorších případech může být O(log n) nebo O(n).