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

Question

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

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

Ответ

HashMap (хэш-таблица, словарь) — это структура данных, которая хранит пары «ключ-значение» и обеспечивает эффективное добавление, удаление и поиск элементов. В основе лежит хэш-функция, которая вычисляет индекс (хэш) для ключа, определяя позицию значения в внутреннем массиве (бакете).

Основные характеристики:

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

Реализация в PHP: В PHP роль HashMap выполняет встроенный тип array.

// Создание ассоциативного массива (HashMap)
$userMap = [
    'id' => 101,
    'name' => 'Анна',
    'email' => 'anna@example.com'
];

// Доступ по ключу за O(1) в среднем
echo $userMap['name']; // Анна

// Добавление новой пары
$userMap['role'] = 'admin';

// Проверка существования ключа
if (array_key_exists('email', $userMap)) {
    echo 'Email существует';
}

// Итерация по парам ключ-значение
foreach ($userMap as $key => $value) {
    echo "$key: $valuen";
}

Коллизии и их разрешение: Когда разные ключи дают одинаковый хэш (коллизия), используются методы:

Метод цепочек: Элементы с одинаковым хэшем хранятся в связном списке внутри одного бакета.
Открытая адресация: Поиск следующего свободного бакета по определённому алгоритму (линейное/квадратичное пробирование).

В PHP разработчику не нужно управлять коллизиями вручную — этим занимается движок Zend Engine.

Ответ 18+ 🔞

Давай разберём эту штуку, которая у всех на слуху, но которую многие понимают как божий окат. HashMap, она же хэш-таблица, она же словарь. Представь себе шкаф с кучей ящиков, но не абы каких, а умных. Ты кричишь: «Дай мне носки!» — и шкаф, ёпта, моментально открывает именно тот ящик, где носки лежат. Не перерывает все, а сразу в цель. Вот это и есть HashMap — пары «ключ-значение».

Суть, если по-простому:

Работает в среднем за O(1). Это значит, что чтобы найти значение, ей похуй, десять элементов у тебя или десять тысяч — скорость почти одинаковая. Пиздец как быстро. В худшем случае, если там всё наколбасилось (это коллизии), может и до O(n) скатиться, но это редкость.
Ключи — уникальные, блядь. Не может быть двух одинаковых. Если попробуешь записать по существующему ключу — старое значение просто накроется медным тазом, его затрут.
Порядок элементов в классической теории — хуй с горы, как легли, так и лежат. Но PHP — хитрая жопа, и его массивы (array) — это упорядоченные хэш-таблицы, их особенность такая.

Как это выглядит в PHP (а здесь это проще простого): В PHP тебе даже париться не надо, встроенный array — он и есть тот самый HashMap, готовый к бою.

// Создаём ассоциативный массив — это и есть наша таблица
$userMap = [
    'id' => 101,
    'name' => 'Анна',
    'email' => 'anna@example.com'
];

// Достаём значение по ключу — мгновенно, O(1), ёба!
echo $userMap['name']; // Выведет: Анна

// Подкидываем новую пару ключ-значение
$userMap['role'] = 'admin';

// Проверяем, не мутит ли ключ какой — существует ли он
if (array_key_exists('email', $userMap)) {
    echo 'Email существует, всё чики-пуки.';
}

// Пробегаемся по всей этой красоте
foreach ($userMap as $key => $value) {
    echo "$key: $valuen";
}

А теперь про коллизии, без которых никуда: Коллизия — это когда два разных ключа, по иронии судьбы, получают одинаковый хэш. Представь, два человека приходят на вечеринку, а им выдают один и тот же бейджик. Ёперный театр! Чтобы таких драк не было, есть два основных подхода:

Метод цепочек. В один ящик (бакет) просто суётся связный список всех элементов, у которых хэш совпал. Открыл ящик — а там цепочка записей, среди которой уже ищешь нужный ключ.
Открытая адресация. Если ящик занят, начинается поиск следующего свободного по какому-то алгоритму (типа «шаг вперёд» или «квадратичный прыжок»).

Самое охуенное, что в PHP тебе вообще не нужно об этом думать. Всю эту магию с коллизиями, бакетами и хэшами берёт на себя движок Zend Engine. Ты просто работаешь с массивом, а он там внутри всё оптимизирует, чтобы не бздеть. Доверия, конечно, ебать ноль, но работает-то ведь!