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

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";
}

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

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

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