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

Хеш таблица в Java (например, HashMap) е структура от данни, която съхранява двойки ключ-стойност и осигурява бърз достъп чрез ключ.

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

• Основата е масив от кофи (кошници).
• Всяка кофичка съдържа или null, или свързан списък (или дърво, ако има много елементи) от елементи с еднакъв хеш код по модул на размера на масива.

Механизъм на работа:

1. При добавяне на елемент се изчислява хеш кодът на ключа и се определя индексът на кофичката.
2. Ако кофичката е празна, елементът се поставя там.
3. Ако е заета, се търси в свързания списък (или дърво) дали ключът вече съществува:
   • Ако е намерен, стойността се актуализира.
   • Ако не, елементът се добавя към списъка.
4. Когато достигне определен праг на запълване, се извършва разширяване на масива (rehash), за да се запази производителността.

Този подход осигурява средна сложност на операциите по вмъкване, търсене и изтриване, близка до O(1).

Пример за използване:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // бърз достъп по ключ