Можете ли објаснити унутрашњу структуру и рад HashMap у Јави?

HashMap u Javi je struktura podataka za skladištenje parova ključ-vrednost sa brzim pristupom putem ključa.

Unutrašnja struktura:

• HashMap koristi niz bačvi (bucket array).
• Za ključ se računa hash kod (hashCode), koji se zatim pretvara u indeks niza.
• U svakoj bačvi se čuvaju elementi sa istim indeksom, obično u obliku povezane liste ili stabla (sa Java 8, ako ima mnogo kolizija).

Rad:

• Pri ubacivanju objekta, indeks se računa na osnovu hasha ključa.
• Ako je bačva prazna, element se smešta tamo.
• Ako je bačva zauzeta, proverava se jednakost ključeva (equals) da bi se ažurirala vrednost ili dodao novi element.
• Pri pretraživanju po ključu, takođe se računa indeks, a zatim se pretražuju elementi u bačvi da bi se pronašla podudarnost.

Primer:

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

Na ovaj način, HashMap obezbeđuje prosečno vreme pristupa O(1), ali pri velikom broju kolizija može degradirati do O(n).