Как работает hash map?

Как работает Hash Map

Hash Map — это структура данных, которая реализует интерфейс Map и использует хеширование для быстрого поиска, вставки и удаления элементов.

Принцип работы

Hash Map работает на основе функции хеширования и массива бакетов:

1. Хеширование ключа — функция hash() преобразует любой ключ в числовой индекс
2. Определение позиции — индекс модифицируется по размеру массива: index = hash(key) % arraySize
3. Разрешение коллизий — при совпадении хешей элементы хранятся в списке (chaining) или ищется новая позицию (open addressing)

Сложность операций

• Поиск (get): O(1) в среднем, O(n) в худшем случае (все элементы в одном бакете)
• Вставка (put): O(1) в среднем, O(n) в худшем случае
• Удаление (remove): O(1) в среднем, O(n) в худшем случае

Пример на Dart

void main() {
  final map = HashMap<String, int>();
  map['яблоко'] = 5;
  map['банан'] = 3;
  map['апельсин'] = 8;
  print(map['яблоко']);
  if (map.containsKey('банан')) {
    print('Банан найден');
  }
  map.forEach((key, value) {
    print('$key: $value');
  });
  map.remove('апельсин');
}

Что происходит под капотом

1. Инициализация — создаётся массив определённого размера (обычно степень 2, например 16)
2. Load Factor — коэффициент загруженности (обычно 0.75). При превышении — массив расширяется вдвое
3. Перехеширование — при расширении все элементы перехешируются и перемещаются в новые позиции
4. Коллизии — если два разных ключа получают одинаковый хеш, используется chaining

Оптимизация

• Хорошие хеш-функции — уменьшают количество коллизий
• Правильный размер — слишком мало — много коллизий, слишком много — пустые ячейки
• Immutable ключи — мутирующиеся ключи нарушают корректность работы

HashMap vs LinkedHashMap vs TreeMap

• HashMap — быстрый (O(1)), порядок не гарантирован
• LinkedHashMap — сохраняет порядок вставки, немного медленнее
• TreeMap — отсортированный (O(log n)), медленнее всех

Hash Map — это один из самых важных компонентов для понимания структур данных. В Flutter и Dart используется регулярно для оптимизации поиска и кеширования данных.