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

Question

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 29% Категория: Flutter Разработчик

Ответ

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

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

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

Пример в 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 и ==.

Ответ 18+ 🔞

А, хеш-таблица, ну это же классика, ёпта! Представь себе огромный шкаф с кучей ящиков, только вместо носков там твои данные лежат. Суть в том, чтобы не рыться во всём этом барахле, а сразу знать, в какой ящик залезть. Вот это и есть хеш-таблица, хитрая жопа, которая в среднем даёт тебе доступ к данным за константное время — O(1), что, в общем-то, овердохуища быстро.

Как эта штука работает, если по-простому:

Хеш-функция. Ты ей суёшь ключ (например, имя "Вася"), а она тебе выплёвывает номер ящика — хеш-код. В идеале, чтобы для каждого "Васи" ящик был свой, но жизнь, как всегда, не идеальна.
Массив корзин. Этот номер ящика — это индекс в обычном массиве. Ты прибегаешь к нужному ящику, а там уже лежит твоя пара "ключ-значение" (ну, "Вася" и его возраст, например).
Коллизии, ёбать копать. А вот тут начинается веселье. Что, если хеш-функция для "Васи" и "Пети" выдала один и тот же ящик? Это и есть коллизия. Чтобы не устраивать драку в одном ящике, есть два основных подхода:
- Метод цепочек. В ящике не одна пара, а целый список. Прибежал, нашёл нужный ящик, и дальше уже в этом списке ищешь своего "Васю". Как в коммуналке, блядь.
- Открытая адресация. Ну, ящик занят "Петей"? Ну и хуй с ним, пошёл искать соседний свободный. Ищешь до тех пор, пока не найдёшь пустой. Главное — чтобы алгоритм поиска был предсказуемым, а то потом сам не найдёшь, куда положил.

Вот тебе пример на Dart, чтобы не быть голословным:

// HashMap — это и есть наша хеш-табличка из стандартной библиотеки.
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) — тоже хеш-таблица, но она ещё и порядок вставки запоминает, как занудная тётка. Для этого там к хешу ещё и linked list прикручен.
Внимание, ядрёна вошь! Самый важный пункт. Если ты суёшь в такую таблицу в качестве ключа свой кастомный объект (не строку и не число), ты обязан переопределить у него методы hashCode и ==. А то получится пидарас шерстяной: два логически одинаковых объекта будут считаться разными, и ты никогда своего ключа не найдёшь. Это прям основа основ, без этого всё накрывается медным тазом.