Можете ли да обясните вътрешната структура и работа на HashMap в езика Java?

HashMap в Java е структура от данни за съхраняване на двойки ключ-стойност с бърз достъп чрез ключ.

Вътрешна структура:

• HashMap използва масив от кофи (bucket array).
• За ключа се изчислява хеш код (hashCode), който след това се преобразува в индекс на масива.
• Във всяка кофа се съхраняват елементи с един и същ индекс, обикновено под формата на свързан списък или дърво (с Java 8, ако има много колизии).

Работа:

• При добавяне на обект, индексът се изчислява по хеша на ключа.
• Ако кофата е празна, елементът се поставя там.
• Ако кофата е заета, се проверява равенството на ключовете (equals), за да се актуализира стойността или да се добави нов елемент.
• При търсене по ключ, също се изчислява индексът и се преглеждат елементите в кофата, за да се намери съвпадение.

Пример:

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

По този начин HashMap осигурява амортизирано време за достъп O(1), но при много колизии може да се деградира до O(n).