Ar galite paaiškinti HashMap vidinę struktūrą ir veikimą Java kalboje?

Java HashMap yra duomenų struktūra, skirta saugoti raktų-reikšmių poras ir užtikrinti greitą prieigą per raktą.

Vidinė struktūra:

• HashMap naudoja kibirų masyvą (bucket array).
• Raktui apskaičiuojamas hashCode, kuris vėliau paverčiamas į masyvo indeksą.
• Kiekviename kibire saugomi elementai su tuo pačiu indeksu, dažniausiai kaip susietas sąrašas arba medis (su Java 8, jei yra daug kolizijų).

Veikimas:

• Pridedant objektą, indeksas apskaičiuojamas pagal rakto hash'ą.
• Jei kibiras tuščias, elementas ten įdedamas.
• Jei kibiras užimtas, tikrinama, ar raktai yra lygūs (equals), kad atnaujinti reikšmę arba pridėti naują elementą.
• Paieška pagal raktą taip pat apskaičiuoja indeksą ir peržiūri elementus kibire, kad rastų atitikmenį.

Pavyzdys:

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

Taip HashMap užtikrina vidutinį prieigos laiką O(1), tačiau esant daug kolizijų, gali degraduoti iki O(n).