Kas saaksite selgitada HashMapi sisemist struktuuri ja toimimist Java keeles?

Java HashMap on andmestruktuur, mis salvestab paare võti-väärtus ja tagab kiire juurdepääsu võti kaudu.

Sisemine struktuur:

• HashMap kasutab ämbripõhist massiivi (bucket array).
• Võtme hashCode arvutatakse ja seejärel muudetakse massiivi indeksiks.
• Igas ämbris hoitakse elemente sama indeksi alt, tavaliselt seotud nimekirja või puu kujul (Java 8 puhul, kui on palju kokkupõrkeid).

Tööpõhimõte:

• Objekti lisamisel arvutatakse indeks võti hashCode põhjal.
• Kui ämber on tühi, asetatakse element sinna.
• Kui ämber on hõivatud, kontrollitakse võrdlust võtmete (equals) vahel, et uuendada väärtust või lisada uus element.
• Võtme järgi otsides arvutatakse samuti indeks ja läbi vaadatakse ämbrisse kuuluvad elemendid, et leida sobivus.

Näide:

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

Nii tagab HashMap keskmise ligipääsuaja O(1), kuid paljude kokkupõrgete korral võib see degradaaduda O(n)-ks.