В программировании ассоциативные связи являются одним из основных видов связей между информационными объектами наряду с наследованием (связями типа "предок-потомок") и агрегацией (связями типа "часть-целое"). Ассоциации позволяют устанавливать необходимые логические связи между сущностями по избранному программистом критерию. Ассоциативная связь подобна стрелке на схеме, направленной от одного объекта к другому. Часто ассоциации используются для нахождения по заданной величине соответствующего значения. В этом случае две части ассоциативной связи соответственно называют поисковым ключом (key) и значением (value), ассоциированным с этим ключом. На этом принципе основана классическая структура данных, называемая словарем (dictionary).

В языке Perl для выражения ассоциаций имеются ассоциативные массивы или хэш-таблицы, которые для краткости принято называть хэшами. Хэш (hash) представляет из себя набор ассоциативных связей. Ключом хэша может быть любая скалярная величина: строка, ссылка, целое или дробное число, автоматически преобразуемое в строку. Причем значения всех ключей в хэше уникальны, поскольку внутренняя организация хэша не допускает ключей с одинаковыми значениями. Ассоциированное с ключом значение может быть любой скалярной величиной. Хэши сочетают в себе ряд привлекательных качеств: гибкость, мощь, быстроту и удобство работы. Поэтому они весьма часто используются при программировании на Perl самых различных задач. С помощью хэшей можно моделировать понятия из математики, информатики, лингвистики и других областей знаний: множества, словари, фреймы, семантические сети, программные объекты и простые базы данных. Размер хэша в Perl ограничен только доступной программе памятью, поэтому хэши позволяют эффективно обрабатывать большие объемы данных, в которых требуется выполнять быстрый поиск. Примечательно то, что в других языках ассоциативные массивы реализованы в виде коллекций объектов в библиотечных модулях, а в языке Perl хэши встроены в ядро языка, что обеспечивает их максимально эффективную работу.

Хэши - переменные и литералы

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

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

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

Если в качестве ключа хэша используется переменная с неопределенным значением, то оно преобразуется в пустую строку, которая и станет поисковым ключом. Значения ключей в хэше уникальны, поэтому хэш часто используется для моделирования множества или простой базы данных с уникальным поисковым индексом. При добавлении нескольких элементов с одинаковыми ключами в хэше остается только последний добавленный:

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

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

И конечно, для заполнения хэша элементами вместо списочного литерала можно использовать массив, содержащий пары "ключ - значение":

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

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

При этом в список будут помещены все ассоциативные пары из хэша, и ключи станут нечетными элементами списка, а значения - четными. Порядок копирования в массив ассоциативных пар заранее не известен.

Элементы хэшей

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

Начинающие осваивать Perl могут думать про хэши, что это такие странные массивы ("ассоциативные"), у которых индексы могут быть не только числами, но и строками, и поэтому записываются эти необычные индексы не в квадратных скобках, а в фигурных (по-английски "curly braces" - "кучерявые скобки"). Вот примеры использования элементов хэша:

В некоторых программах можно встретить при записи элементов хэша строковые ключи, не заключенные в кавычки: это допускается, если ключ - одно слово, записанное по правилам написания идентификаторов, так называемое "голое слово" ("bare word").

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

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

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

Функции работы с хэшами

При обработке данных в хэше часто возникает необходимость проверить наличие в нем элемента с определенным ключом. Функция exists проверяет, содержится ли указанный ключ в хэше. Если ключ найден, она возвращает истинное значение ('1'), - и ложное значение (пустую строку), если такого ключа в хэше нет. При этом ассоциированное с ключом значение не проверяется и может быть любым, в том числе и неопределенным. Так можно проверить наличие ключа в хэше:

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

Проверка с помощью функции defined($hash{$key}) отличается от проверки значения элемента на истинность значения $hash{$key}, так как значение элемента может быть определено, но равно нулю или пустой строке, что тоже воспринимается как ложь.

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

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

Неопределенное значение, хранимое в элементе хэша, означает, что необходимый поисковый ключ присутствует, но с ним не ассоциировано никакого значения.

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

Если аргументом функции delete будет несуществующий элемент массива, то она просто вернет неопределенное значение, не вызвав ошибки при выполнении программы.

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

Возможно также использовать список ключей для доступа в цикле ко всем значениям хэша. Так можно напечатать частотный словарь из предыдущего примера:

Элементы хэша, как и другие скалярные величины, помещенные в обрамленную двойными кавычками строку, заменяются своими значениями. Кстати, можно переписать последний пример, добавив сортировку ключей для вывода слов в алфавитном порядке. А для организации цикла можно применить модификатор foreach, совмещающий очередной элемент списка с переменной по умолчанию $_:

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

Пустой хэш в скалярном контексте возвращает ложное значение (строку '0'), а непустой - истинное. Поэтому проверить, пуст ли хэш, можно еще проще - употребив имя хэша в скалярном контексте, что часто используется в конструкциях, проверяющих условие:

Встроенная функция values, дополняющая функцию keys, возвращает список всех значений элементов хэша в том же порядке, в каком функция keys возвращает ключи. С полученным списком можно поступать обычным образом: например, сохранить в массиве или обработать в цикле:

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

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

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

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

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

Нечетные элементы инвертированного списка становятся ключами, а четные - значениями хэша %hash_by_value.

Хэши и списки

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

Можно напечатать хэш по-другому, построчно и в более облагороженном виде, при помощи функции map, которая также выполняет роль итератора:

В этом примере на основании списка ключей, возвращенного функцией keys, функция map формирует список нужных строк, вставляя из хэша в каждую из них ключ и значение. Она возвращает сформированный список функции print, которая выводит его в выходной поток. Кстати, это типичный для Perl прием - обрабатывать данные при помощи цепочки функций, когда результат работы одной функции передается на обработку другой, как это принято делать с помощью конвейеров команд в операционных системах семейства Unix.

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

Здесь в блоке сравнения функции sort сопоставляется значения хэша, ассоциированные с очередными двумя ключами из списка, который предоставлен функцией keys.

Срезы хэшей

Подобно тому, как при работе с массивами срезы позволяют работать со списком элементов, в Perl есть возможность обращаться сразу с несколькими элементами хэша. Это делается с помощью среза хэша. Срез хэша (hash slice) - это список значений хэша, заданный перечнем соответствующих ключей. Он записывается в виде имени хэша с префиксом @ (так как срез - это список), за которым в фигурных скобках перечисляются ключи. Список ключей в срезе хэша можно задать перечислением скалярных значений, переменной-списком или списком, возвращенным функцией. Например, так:

Если в срезе хэша список ключей состоит из единственного ключа, срез все равно является списком, хотя и из одного значения. Сравните:

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

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

С помощью среза хэша и функций keys и values можно поменять в хэше местами ключи и значения, то есть сделать значения ключами, а ключи - значениями.

Специальные хэши

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

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

Хэши и контекст

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

В этой лекции завершается изучение основных типов данных в языке Perl: скаляров, списков и хэшей. В таблице 6.1 для сравнения приведены контексты и форматы обращения к скалярным переменным, элементам массивов и хэшей и их срезам.

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

Хэши - это, наверное, самая популярная структура данных при программировании на Perl. Без них не обходится ни одна серьезная программа, ведь их применение делает многие алгоритмы проще, а программу - понятнее. Материал этой лекции показывает, насколько удобно и просто пользоваться хэшами. Особенный интерес представляет возможность хранения в ассоциативных массивах ссылок на другие структуры данных: массивы, хэши, объекты, подпрограммы. Это позволяет создавать сложные динамические структуры данных, о чем будет сказано в лекции 11, посвященной ссылкам.