Môžete vysvetliť vnútornú štruktúru a fungovanie HashMap v jazyku Java?

HashMap v Jave je dátová štruktúra na ukladanie párov kľúč-hodnota s rýchlym prístupom cez kľúč.

Vnútorná štruktúra:

• HashMap používa pole vedier (bucket array).
• Pre kľúč sa vypočíta hash kód (hashCode), ktorý sa následne prevedie na index poľa.
• V každom vedre sa ukladajú prvky s rovnakým indexom, zvyčajne vo forme prepojenej zoznamu alebo stromu (s Java 8, ak je veľa kolízií).

Fungovanie:

• Pri vkladaní objektu sa vypočíta index na základe hashu kľúča.
• Ak je vedro prázdne, prvok sa tam umiestni.
• Ak je vedro obsadené, kontroluje sa rovnosť kľúčov (equals) na aktualizáciu hodnoty alebo pridanie nového prvku.
• Pri vyhľadávaní podľa kľúča sa tiež vypočíta index a prehľadávajú sa prvky v vedre, aby sa našla zhoda.

Príklad:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
int value = map.get("apple"); // 5

Týmto spôsobom HashMap zabezpečuje priemerný čas prístupu O(1), ale pri veľkom počte kolízií sa môže zhoršiť na O(n).