Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <ul><li>Ruby - Hash</li>

3 <li>Lua - Table</li>

4 <li>Python - Dictionary</li>

5 <li>JavaScript - Object</li>

6 <li>Elixir/Java - Map</li>

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

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

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

10 <h2>Хеширование</h2>

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

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

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

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

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

16 <h3>За кулисами</h3>

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

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

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

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

21 <ol><li>Интерпретатор хеширует ключ. Результатом хеширования становится число.</li>

22 <li>Это число используется как индекс внутреннего массива для поиска значения.</li>

23 <li>Если индекс существует, то извлекается значение, которое находилось внутри, и возвращается наружу.</li>

24 </ol><h2>Коллизии</h2>

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

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

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