How is the data structure of a hash table implemented, for example, in HashMap?

A hash table in HashMap is implemented as an array of buckets, where each bucket contains a linked list or a tree (in newer versions of Java) of elements with the same hash code. The key is transformed into a hash code using a hash function, which determines the bucket index.

When adding an element, the hash code of the key is computed, a bucket is selected, and the element is added there. In case of collisions (same index), elements are stored in a list or a tree within the bucket.

This allows providing an average access time to an element of about O(1). When there are many collisions, the structure inside the bucket changes from a list to a balanced tree to improve performance to O(log n).

An example of a simplified structure in 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); // update 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;
  }
}