Хэш таблицы

В PHP все массивы это упорядоченные словари (т.е они представляют собой упорядоченный список пар вида ключ-значение), где ассоциирование ключа значению реализовано на основе hashtable.

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

Хеширование (или хэширование, англ. Hashing ) – это преобразование входного массива данных определённого типа и произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом, хеш-таблицей или дайджестом сообщения (англ. message digest ).

Проблема возникает, когда хэширующая функция возвращает одинаковые хэши для разных ключей, то есть возникает коллизия (то, что это действительно происходит легко убедится – количество возможных ключей бесконечно велико, в то время как количество хэшей ограничено размером типа integer).

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

Хеш-таблица – это структура данных, реализующая интерфейс ассоциативного массива, то есть она позволяет хранить пары вида "ключ - значение" и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Хеш-таблица является массивом, формируемым в определённом порядке хеш-функцией.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$data = [];
$data['key'] = 'value';
print_r($data['key']);

Интерпретатор хеширует ключ. Результатом хеширования становится число. Это число используется как индекс внутреннего массива для поиска значения. Если индекс существует, то извлекается значение, которое находилось внутри, и возвращается наружу.