Коллекции, часть 4: Ассоциативные массивы

Другие части: массивы, итераторы, множества, списки, деревья

Один из самых распространённых и важных типов коллекций называется по-английски map, или карта. Нормального русского эквивалента почему-то нет. Словом "карта" никто не пользуется, где-то используют мерзкую кальку "мапа", а если по-правильному, по-академически, то это ассоциативный массив – слишком неудобное название.

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

Короче говоря, внешне это выглядит как массив, смещения которого заданы произвольно – любые числа (не обязательно непрерывно и по порядку), а также символы, строки, и другие типы. Например:

Классический массив

a[0] = 10;
a[1] = 25;
a[2] = 30;

Ассоциативный массив

а[0] = 10;
a['1'] = 25;
а['banana'] = 30;

Все эти произвольным образом заданные смещения уже не могут считаться смещениями: вы можете отсчитать 2 элемента от начала массива, но вы не можете отсчитать "banana" элементов от начала массива. Вместо этого между "banana" и элементом массива нужно построить ассоциацию. "Под капотом" такая коллекция состоит из двух массивов: массив ключей, и массив значений, которые соответствуют ключам:

keys = [0, '1', 'banana'];
values = [10, 25, 30];

Это всего лишь два отдельных классических массива, но коллекция отображает элементы одного массива на элементы другого массива, тем самым получая ассоциативную связь в виде пар ключ => значение:

0 => 10
'1' => 25
'banana' => 30

Теперь коллекция знает, как по ключу "banana" найти элемент: сначала она перебирает массив ключей и смотрит, по какому смещению найдётся "banana". Это смещение 2, значит элемент находится в массиве значений также по смещению 2. Это 30.

Такие типы коллекций используются очень широко и часто в виде гибридов c другими типами. Например, в языке PHP все массивы являются ассоциативными, даже если имеют обычные числовые смещения. В JavaScript в большинстве случаев нет разницы между ассоциативным массивом и объектом, то есть можно обратиться к свойству объекта стандартно:

obj.banana = 5;

Или через синтаксис массива:

obj['banana'] = 5;

Кроме того, коллекция может предоставлять интерфейс c методами типа set и get:

collection.set('banana', 30);
a = collection.get('banana');

Для пользователя в любом случае всё просто и удобно. Он может добавить любую пару ключ => значение, не думая о том, как там всё работает.

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

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

Подборка материалов про коллекции: