Jak se určuje doba práce při kolizích v HashMap?

V Java je průměrná doba operací (například get, put) v HashMap díky hashování klíčů O(1). Nicméně při kolizích (kdy různé klíče mají stejný hash) jsou prvky uloženy ve stejném koši (bucket).

Dříve, v Java (do verze 8), při kolizích byly prvky v koši uloženy jako spojový seznam, což zhoršovalo dobu přístupu na O(n) v nejhorším případě, pokud všechny prvky spadly do jednoho koše.

Od Java 8, když je dosažen určitý práh prvků v koši (obvykle 8), je spojový seznam převeden na vyvážené stromové struktury (například červené-černé stromy). To zlepšuje dobu přístupu na O(log n) v nejhorším případě.

Tedy, při přítomnosti kolizí se mění doba práce HashMap:

• Málo kolizí — doba blízko O(1)
• Hodně kolizí — doba se může zhoršit na O(log n) díky stromu

Příklad:

Map<String, String> map = new HashMap<>();
map.put("key1", "value1");
map.put("key2", "value2");
String val = map.get("key1");

Pokud "key1" a "key2" mají stejný hash, spadnou do stejného koše a hledání probíhá přes strukturu uvnitř koše.