Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Хеш-таблицы PHP: Ассоциативные массивы

Ассоциативный массив — абстрактный тип данных (АТД), с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. Например, в других языках это:

  • Ruby — Hash
  • Lua — Table
  • Python — Dictionary
  • JavaScript — Object
  • Elixir/Java — Map

Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров.

Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.

Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри, будет много терминов. Эта информация крайне важна для любых разработчиков. Она снимает магичность с происходящего, даёт понимание эффективности, ценой которой приходится платить за удобства.

Хеширование

Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).

Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).

Самый простой способ хешировать данные на PHP — использовать функцию crc32:

<?php

// Любые данные которые мы хотим хешировать
$checksum = crc32('The quick brown fox jumped over the lazy dog.');

// Для одних и тех же данных хеш всегда одинаковый!
print_r($checksum); // => 2191738434

С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.

После того как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:

<?php

// $key — это ключ в ассоциативном массиве, который мы хешируем
$index = crc32($key) % 1000; // по модулю
print_r($index); // => 434

хеширование

За кулисами

Рассмотрим процесс добавления нового значения в ассоциативный массив. Программист пишет:

<?php

$data = [];
$data['key'] = 'value';

Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:

<?php

// Для простоты показано на PHP, хотя в реальности всё это происходит на более низком уровне.

// Создание ассоциативного массива приводит к инициализации
// индексированного массива внутри интерпретатора.
$internal = [];

// Во время присвоения значения `$data['key'] = 'value'`
// интерпретатор выполняет несколько действий:

// 1. Хеширует ключ. Результатом хеширования становится число.
$hash = crc32('key');
// 2. Число, полученное на предыдущем шаге преобразуется в индекс массива.
$index = $hash % 1000;
// В значение внутреннего индексированного массива, по найденному индексу,
// записывается ещё один массив, первым элементом которого становится ключ `'key'`,
// а вторым значение `'value'`.
$internal[$index] = ['key', 'value'];

Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже — там, где мы поговорим про коллизии.

Теперь посмотрим на чтение:

<?php

$data = [];
$data['key'] = 'value';
print_r($data['key']);
  1. Интерпретатор хеширует ключ. Результатом хеширования становится число.
  2. Это число используется как индекс внутреннего массива для поиска значения.
  3. Если индекс существует, то извлекается значение, которое находилось внутри, и возвращается наружу.

Коллизии

Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей — бесконечно. В свою очередь, результат любой хеш-функции — строка фиксированной длины, а значит множество всех выходных значений — конечно.

Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (когда для разных значений получается один и тот же хеш). Такую ситуацию принято называть коллизией. Способов разрешения коллизий несколько, и каждому из них соответствует свой тип хеш-таблицы.

<?php
// Пример коллизии

// Две разных строчки возвращают одинаковый хеш!
crc32('aaaaa0.462031558722291'); // 1938556049
crc32('aaaaa0.0585754039730588'); // 1938556049

Коллизии не так редки, как может показаться. Убедиться в этом можно, изучив парадокс дней рождений.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы
профессия
Занимайтесь созданием сайтов, веб-приложений, сервисов и их интеграцией с внутренними бизнес-системами на бекенд-языке PHP
10 месяцев
с нуля
Старт 21 ноября

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»