Můžete vysvětlit, jak je implementována datová struktura HashMap a jak zajišťuje rychlý přístup k prvkům?

HashMap je datová struktura, která ukládá páry klíč-hodnota a zajišťuje rychlý přístup k hodnotám pomocí klíče. Je založena na poli bucketů, do kterého jsou prvky umístěny na základě hash kódu klíče.

Při přidávání páru se vypočítá hash kód klíče a podle něj se určí index bucketu (obvykle pomocí operace modulo s velikostí pole). Pokud je v bucketu již nějaké prvky (kolize), jsou uloženy ve formě spojového seznamu nebo stromu (v novějších verzích Java).

Při hledání prvku podle klíče se provádí:

• Výpočet hash kódu klíče
• Určení bucketu
• Vyhledávání v bucketu pomocí metody equals mezi prvky se stejným hash kódem

To zajišťuje průměrnou složitost přístupu O(1), ale v nejhorším případě (mnoho kolizí) může degradovat na O(n). Aby se tomu předešlo, velikost pole se zvětšuje při dosažení určitého zatížení (load factor).