0 added
0 removed
Original
2026-01-01
Modified
2026-02-26
1
<p><strong>Ассоциативный</strong>массив - абстрактный тип данных, с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. В JavaScript массив можно хранить в объекте (Object), в других языках:</p>
1
<p><strong>Ассоциативный</strong>массив - абстрактный тип данных, с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. В JavaScript массив можно хранить в объекте (Object), в других языках:</p>
2
<ul><li>Ruby - Hash</li>
2
<ul><li>Ruby - Hash</li>
3
<li>Lua - Table</li>
3
<li>Lua - Table</li>
4
<li>Python - Dictionary</li>
4
<li>Python - Dictionary</li>
5
<li>Elixir/Java - Map</li>
5
<li>Elixir/Java - Map</li>
6
</ul><p>Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. Фактически все предыдущие уроки по объектам в JavaScript были посвящены тому, как использовать объекты в качестве ассоциативных массивов.</p>
6
</ul><p>Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. Фактически все предыдущие уроки по объектам в JavaScript были посвящены тому, как использовать объекты в качестве ассоциативных массивов.</p>
7
<p>Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных - хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.</p>
7
<p>Ассоциативный массив, в отличие от обычного массива (называемого индексированным, так как значения в нем расположены по индексам), нельзя положить в память "как есть". У него нет индексов, которые бы могли определить порядок и простой способ добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных - хеш-таблицу. Она позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует две вещи: индексированный массив и функцию для хеширования ключей. Обратите внимание, что хеш-таблица это не просто способ размещать данные в памяти, она включает в себя логику.</p>
8
<p><em>Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри. Эта информация крайне важна для разработчиков, которые хотят по-настоящему разбираться в том, что они делают. Она снимает "магичность" с происходящего внутри языка и дает понимание цены, которую приходится платить за удобство использования объектов.</em></p>
8
<p><em>Ниже пойдет речь про то, как ассоциативные массивы бывают устроены внутри. Эта информация крайне важна для разработчиков, которые хотят по-настоящему разбираться в том, что они делают. Она снимает "магичность" с происходящего внутри языка и дает понимание цены, которую приходится платить за удобство использования объектов.</em></p>
9
<p>Итак, что примерно происходит, когда мы выполняем код:</p>
9
<p>Итак, что примерно происходит, когда мы выполняем код:</p>
10
<h2>Хеширование</h2>
10
<h2>Хеширование</h2>
11
<p>Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).</p>
11
<p>Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия: найти хеш (хешировать ключ) и привести его к индексу (например, через остаток от деления).</p>
12
<p>Хеширование - операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).</p>
12
<p>Хеширование - операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).</p>
13
<p>С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git<em>0481e0692e2501192d67d7da506c6e70ba41e913</em>не что иное, как хеш, полученный в результате хеширования данных коммита.</p>
13
<p>С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git<em>0481e0692e2501192d67d7da506c6e70ba41e913</em>не что иное, как хеш, полученный в результате хеширования данных коммита.</p>
14
<p>После того, как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:</p>
14
<p>После того, как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:</p>
15
<h3>За кулисами</h3>
15
<h3>За кулисами</h3>
16
<p>Рассмотрим процесс добавления нового значения в ассоциативный массив (напоминаем, что в JavaScript он представлен типом данных Object). Программист пишет:</p>
16
<p>Рассмотрим процесс добавления нового значения в ассоциативный массив (напоминаем, что в JavaScript он представлен типом данных Object). Программист пишет:</p>
17
<p>Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:</p>
17
<p>Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:</p>
18
<p>Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже, там где мы поговорим про коллизии.</p>
18
<p>Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже, там где мы поговорим про коллизии.</p>
19
<p>Теперь посмотрим на чтение:</p>
19
<p>Теперь посмотрим на чтение:</p>
20
<h2>Коллизии</h2>
20
<h2>Коллизии</h2>
21
<p>Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей - бесконечно. В свою очередь, результат работы хеш-функции - строка фиксированной длины, а значит множество всех выходных значений - конечно.</p>
21
<p>Ключом в ассоциативном массиве может быть абсолютно любая строка (любой длины и содержания). Другими словами, множество всех возможных ключей - бесконечно. В свою очередь, результат работы хеш-функции - строка фиксированной длины, а значит множество всех выходных значений - конечно.</p>
22
<p>Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (где под одним хешем лежит несколько разных значений - как если бы под одним индексом в массиве лежало два разных элемента). Такую ситуацию принято называть коллизией. Есть несколько<a>способов разрешения коллизий</a>(открытая адресация, метод цепочек), и каждому из них соответствует свой тип хеш-таблицы.</p>
22
<p>Из этого факта следует, что не для всех входных данных найдётся уникальный хеш. На каком-то этапе возможно появление дублей (где под одним хешем лежит несколько разных значений - как если бы под одним индексом в массиве лежало два разных элемента). Такую ситуацию принято называть коллизией. Есть несколько<a>способов разрешения коллизий</a>(открытая адресация, метод цепочек), и каждому из них соответствует свой тип хеш-таблицы.</p>
23
<p>Простейший способ разрешения коллизий, открытая адресация, предполагает последовательное перемещение по слотам хеш-таблицы в поисках первого свободного слота, куда значение будет записано. В примере выше, для второго значения будет проверен хеш 1938556050, затем, если он занят, 1938556051, и т.д. до первого незанятого хеша.</p>
23
<p>Простейший способ разрешения коллизий, открытая адресация, предполагает последовательное перемещение по слотам хеш-таблицы в поисках первого свободного слота, куда значение будет записано. В примере выше, для второго значения будет проверен хеш 1938556050, затем, если он занят, 1938556051, и т.д. до первого незанятого хеша.</p>
24
<p>Коллизии не так редки, как может показаться. Убедиться в этом можно, изучив<a>парадокс дней рождения</a>.</p>
24
<p>Коллизии не так редки, как может показаться. Убедиться в этом можно, изучив<a>парадокс дней рождения</a>.</p>