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

При добавлении элемента вычисляется хеш-код ключа, выбирается бакет, и элемент добавляется туда. При коллизиях (одинаковом индексе) элементы хранятся в списке или дереве внутри бакета.

Это позволяет обеспечивать среднее время доступа к элементу около O(1). При большом количестве коллизий структура внутри бакета меняется с списка на сбалансированное дерево, чтобы улучшить производительность до O(log n).

Пример упрощённой структуры на Dart (Flutter):

class HashMap<K, V> {
  List<List<MapEntry<K, V>>> buckets;

  HashMap(int size) : buckets = List.generate(size, (_) => []);

  int _hash(K key) => key.hashCode % buckets.length;

  void put(K key, V value) {
    var index = _hash(key);
    for (var entry in buckets[index]) {
      if (entry.key == key) {
        entry = MapEntry(key, value); // обновление значения
        return;
      }
    }
    buckets[index].add(MapEntry(key, value));
  }

  V? get(K key) {
    var index = _hash(key);
    for (var entry in buckets[index]) {
      if (entry.key == key) return entry.value;
    }
    return null;
  }
}

Каким образом реализована структура данных хеш-таблица, например, в HashMap?