Хеш-таблицы также известны под другими названиями: «ассоциативные массивы» , «словари», «отображения», «хешкарты» или просто хеши».

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

Теперь важный момент для PHP. В PHP нет отдельного типа hash map. Все ассоциативные массивы – это и есть хеш-таблицы. Вот буквально:

$user = [
    'id' => 42,
    'email' => '[email protected]',
    'role' => 'admin',
];

Это не массив в смысле C или Python list. Это хеш-таблица, внутри движка Zend Engine. Даже если ключи выглядят как числа, PHP все равно думает в терминах hash table.

Как это работает внутри, если по-человечески. PHP берет ключ. Если это строка, считает хеш (алгоритм сложный, но суть не в нем). Если это число – оно почти напрямую идет как индекс. Потом по этому хешу PHP быстро находит нужную ячейку и достает значение. Поэтому:

echo $user['email'];

Но тут появляется тонкий момент – коллизии. Коллизия это когда два разных ключа дают одинаковый хеш. Такое бывает всегда, это математика, не баг. PHP решает это цепочками: в одной ячейке может лежать несколько элементов, и тогда уже идет короткий линейный поиск. Из-за этого в худшем случае хеш-таблица может скатиться к O(n). В реальности – почти никогда, если ты не воюешь с движком специально.

Почему хеш-таблицы так любят в алгоритмах. Потому что они убивают вложенные циклы. Типичная история из задачек:

Есть массив, надо понять, встречалось ли число раньше.

Без хеша:
идешь циклом, внутри еще циклом – O(n²), боль и страдания.

С хеш-таблицей:

$seen = [];

foreach ($arr as $value) {
    if (isset($seen[$value])) {
        // уже было
    }
    $seen[$value] = true;
}

И все. Один проход, O(n). Красота.

Кстати, isset тут не случайно. В PHP isset($hash[$key]) быстрее и безопаснее, чем array_key_exists, если тебе не важно различать null и отсутствие ключа. Это мелочь, но на больших объемах приятно.

Хеш-таблица оптимизирована под поиск по ключу, а не по значению.

Коротко: потому что хеш-таблица умеет быстро отвечать на вопрос был ли такой ключ, но не умеет быстро отвечать на вопрос было ли такое значение.

$seen[$value] = true;

Говорим PHP: вот ключ. Запомни его. Значение тут вообще вторично, это просто флажок. Можно писать true, 1, 'yes', пофиг.

А теперь смотри на альтернативу, которая кажется логичной новичку:

$seen[] = $value;

Что тут происходит. Ты складываешь значения подряд. Чтобы проверить, было ли число раньше, тебе придется делать:

in_array($value, $seen);

А in_array это линейный поиск. PHP идет по всему массиву и сравнивает каждый элемент. Это O(n). И если ты так делаешь внутри цикла, внезапно у тебя снова O(n²). Мы только что все испортили.