Хеш-таблицы, HashTables (part-1)

Ну что, отпуск окончен, теперь с новыми силами пришла пора приступить к статьям :) Здесь речь пойдёт именно о структуре данных. То есть пока мы не будем вдаваться во внутренности php (например под капотом языка массивы реализованы именно с помощью хеш-таблиц).

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

Пока звучит сложно, но сейчас попробуем разобраться ;) Для начала определимся с тем, что такое хеширование.

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

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

❗️ Например, на картинке выше мы видим, что хеш-функция сопоставила ключ John Smith с индексом 873, а далее в хеш-таблицу под этим индексом было записано значение, а если быть точным, то комплексный объект, содержащий исходный ключ и значение (в нашем случае номер телефона).

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

$key = 'John Doe';
$index = crc32($key) % 1000; // по модулю
print_r($index); // => 434

📌 В данном примере мы используем так называемое "адресное пространство", которое задаёт размеры нашей хеш-таблицы. Так как мы получаем остаток от деления на 1000, то все значения нашего индекса будут лежать в диапазоне от 0 до 999. Возникает вопрос "может ли случиться так, что для разных ключей будет рассчитан один и тот же индекс?" — может, но это не значит, что значения затрутся. Структура таблицы станет чуть сложнее, незначительно вырастет вычислительная сложность, но подробнее об этом в следующем посте ;)

❗️ Главное, что ваша хеш-функция должна:

1. Быстро вычислять хеш (индекс), в разных источниках можно встретить понятие "адрес", это одно и то же;
2. Всегда возвращать один и тот же адрес для одного и того же ключа;
3. Использует все адресное пространство с одинаковой вероятностью;

❓ Зачем так всё усложнять?

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

#middle #algorithm #source