Что такое хеш-таблица (hashmap)?

Хеш-таблица (hashmap) — это структура данных, реализующая интерфейс ассоциативного массива (сопоставление ключей значениям). Она обеспечивает в среднем константное время O(1) для операций вставки, удаления и поиска.

Основной принцип работы:

1. Хеш-функция преобразует ключ в целочисленный индекс (хеш-код).
2. Этот индекс используется для доступа к "корзине" (bucket) во внутреннем массиве, где хранится пара ключ-значение.
3. Коллизии (когда разные ключи дают одинаковый индекс) разрешаются одним из методов:
   • Метод цепочек: Каждая корзина содержит связанный список (или другое хранилище) всех пар, попавших в неё.
   • Открытая адресация: При коллизии алгоритм ищет следующую свободную корзину по определённому алгоритму (линейное/квадратичное пробирование).

Пример в Dart:

// HashMap — реализация хеш-таблицы в Dart.
import 'dart:collection';

void main() {
  final map = HashMap<String, int>();
  map['Alice'] = 25; // Вставка
  map['Bob'] = 30;

  print(map['Alice']); // 25 - поиск по ключу
  print(map.containsKey('Bob')); // true - проверка наличия ключа
  map.remove('Alice'); // Удаление
}

Ключевые особенности в контексте Dart/Flutter:

• Встроенный тип Map (например, {}) часто использует хеш-таблицу для своей реализации.
• HashMap из dart:collection не гарантирует порядок итерации элементов.
• LinkedHashMap (стандартная реализация Map) сохраняет порядок вставки, используя комбинацию хеш-таблицы и связанного списка.
• Для корректной работы с пользовательскими объектами в качестве ключей необходимо переопределить методы hashCode и ==.