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

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

Создание ассоциативных массивов

Конструктор хэш-массива представляет собой список значений, заключенный в круглые скобки. Однако в отличии от конструктора массива скаляров, элементы списка имеют в нем не самостоятельное значение, представляют «связанные» пары. В паре первое значение являются ключом, а второе – тем значением, которое можно получить с помощью ассоциированного с ним ключа:
(key1, value1, key2,value2, keyN, valueN)
ВНИМАНИЕ В конструкторе ассоциативного массива должно содержаться четное число элементов. В противном случае во время выполнения будет сгенерировано сообщение об ошибке.
Задание пар значений в конструкторе единым списком, в котором все элементы разделены запятой, не очень удобно, так как в длинном списке достаточно трудно выделить соответствующие пары ключ/значение. Для визуального выделения в списке пары ключ/значение их можно «соединить», используя синоним символа операции запятая — последовательность символов =>. (В скобках заметим, что в Perl запятая является операцией, которая в скалярном контексте просто вычисляет последовательность выражений, разделенных запятыми, и возвращает значение последнего вычисленного выражения, а в списковом контексте возвращает список вычисленных значений.) Таким образом, конструктор ассоциативного массива может выглядеть и так:
(keyl => valuel, key2 => value2, ... , keyN => valueN)
Для хранения ассоциативных массивов используются переменные, имена которых начинаются с префикса %. Такие переменные часто называют хэш-переменными.
Создать ассоциативный массив можно двумя способами: операцией присваивания хэш-переменной конструктора ассоциативного массива:
%hash = ("Матросов", "217-000-001",
         "Чаунин", "218-001-001");
или заданием значений, соответствующих определенным ключам, с помощью следующей синтаксической конструкции:
$hash{"Матросов"} = "717-000-001";
Если способ создания хэш-массива с помощью конструктора достаточно прозрачен, то второй способ требует некоторых разъяснений. Первое — в левой части оператора присваивания стоит ссылка на элемент хэш-массива. Здесь, как и в случае с обращением к элементу массива скаляров, префикс % в имени хэш-массива заменен на префикс скаляра $ (ведь элемент хэш-массива является скаляром), а ключ задается в фигурных скобках. Второе — когда интерпретатор встречает в левой части оператора присваивания ссылку на элемент хэш-массива. который ранее не был создан, то он автоматически создает его и присваивает значение элементу с заданным ключом. Если хэш-массив уже существует, то либо создается новый элемент, если в массиве нет элемента с указанным ключом, либо значение элемента с указанным ключом заменяется на значение выражения в правой части оператора присваивания.
Такую же конструкцию следует использовать и для получения значения существующего элемента массива:
print $hash{"Матросов"};
Если при получении значения будет задан несуществующий ключ и при запуске интерпретатора использовался ключ -w, то интерпретатор выдаст предупреждающие сообщение об использовании неинициализированного значения в выражении.
Для добавления нового элемента в ассоциативный массив или изменения значения уже существующего элемента следует в операции присваивания в левой части использовать ссылку по ключу на соответствующий элемент:
$hash{"Матросов"} = "188-000-009"; # Изменение
                                   # существующего элемента
$hash("редактор"} = "199-000-009"; # Добавление нового
                                   # элемента
СОВЕТ При задании ключа в конструкторе ассоциативного массива или при обращении к соответствующему элементу по ключу не обязательно заключать его в кавычки, если ключ представлен последовательностью латинских символов и цифр. В этом случае интерпретатор будет рассматривать его как простое слово и автоматически заключать в одинарные кавычки. Поэтому, например, следующие два способа обращения к элементу с ключом user синтаксически допустимы и приведут к одинаковому результату: $hash{"user"} и $hash{user}.
ВНИМАНИЕ При изменении значения элемента ассоциативного массива следует внимательно задавать значение ключа. Если ключ будет отличаться от ключа существующего элемента, то операция присваивания приведет к добавлению в ассоциативный массив нового элемента без какого-либо предупреждающего сообщения интерпретатора.
Переменную хэш-массива, в отличие от скалярной переменной и переменной массива скаляров, нельзя подставлять в строки, ограниченные двойными кавычками. Однако элемент ассоциативного массива, так как он представляет собой скаляр, можно подставлять в указанные строки. Следующий оператор:
print "Телефон редактора: $hash{"редактор"}\n";
напечатает строку:
Телефон редактора: 217-000-009
Все правила, предусмотренные операцией подстановки значения скалярной переменной, распространяются и на элементы массива.
Как и в случае с массивами скаляров, можно создавать фрагменты хэш-массивов, если указать в фигурных скобках после идентификатора хэш-массива список ключей, а префикс % заменить на префикс массива скаляров @. Однако фрагмент хэш-массива сам не является хэш-массивом, а представляет массив скаляров соответствующих значений хэш-массива — поэтому-то и используется префикс @ массива скаляров:
@hasn{"Чаунин", "редактор"}; # Фрагмент хэша
В конструкции, определяющей фрагмент хэш-массива, можно использовать операцию «диапазон», но при этом следует учитывать, что в возвращаемый список значений будут внесены неопределенные значения undef, соответствующие не существующим ключам хэша. В этом случае при включенном режиме отображения предупреждающих сообщений интерпретатора будет получено соответствующее сообщение. Например, результатом выполнения следующего фрагмента:
%ar = (a=>l, c=>3, d=>4); 
@а = @аr{"а".."с"};
print "@а";
будет вывод:
Use of uninitialized value in join or string at temp.pl line 3.
1  3
Предупреждающее сообщение получено из оператора печати print. Обратите внимание, что между двумя выведенными значениями элементов фрагмента хэш-массива напечатано два пробела, а не один, так как на самом деле массив @а состоит из трех элементов, причем значение второго элемента равно undef.

Стандартные функции обработки ассоциативных массивов

В языке определено небольшое множество стандартных встроенных функций для работы с ассоциативными массивами, реализующими операции удаления элементов массивов и получения информации о них.
Функцией delete можно удалить элемент или целый список элементов из хэш-массива. Для этого достаточно передать функции в качестве параметра элемент хэш-массива или его фрагмент:
delete($hash{"peдактоp"}); # Удаление элемента
delete(@hash{"Maтpocoв", "Чаунин"}); # Удаление фрагмента
При работе с хэш-массивами, в отличие от массивов скаляров, эта функция физически удаляет элемент с заданным ключом из хэш-массива, возвращая его значение. Если элемента с заданным ключом не существует, то функция возвращает неопределенное значение undef.
ВНИМАНИЕ. Удалить элемент хэш-массива можно только функцией delete.Присваивание элементу с заданным ключом неопределенного значения $hash{"clue"}= undef не удаляет элемент массива, а просто делает значение момента с ключом "clue" неопределенным undef. Его использование в качестве операнда какой-либо операции приведет к отображению сообщения об использовании неинициализированной переменной, если включен режим отображения предупреждающих сообщений интерпретатора.
Проверить, существует ли в хэш-массиве элемент с заданным ключом, позволяет функция exists, параметром которой должна быть ссылка на элемент с указанным ключом:
exists($hash("редактор"));
Она возвращает значение «истина» (число 1 или строка " 1"}, если элемент с таким ключом существует, и «ложь» в противном случае (пустая строка "").
Примеры применения функций delete( ) и exists( ) к ассоциативным массивам представлены ниже:
#!perl -w
%array = ( "first", 2, "third", 3, second,  2);
$array{"first"} = undef;
$key = "first";
# Печать будет выполнена, элемент инициализирован
print "Элемент '$key' существует\n" if exists $array{$key};
$key = "fourth";
# Печать не будет выполнена, элемент не инициализирован 
print "Элемент '$key' существует\n" if exists $array{$key}; $key = "second";
# Напечатает 2
print delete($array{$key}), "\n";
# Печать не будет выполнена, элемент не инициализирован 
print "Элемент  '$key' существует\n" if exists $array{$key}; $key = "fifth";
# Отобразится предупреждавшее сообщение 
print delete($array{$key}), "\n";
Организовать последовательный перебор всех пар ключ/значение ассоциативного массива можно функцией each, которая в списковом контексте возвращает пару ключ/значение, а в скалярном — только ключ. Когда достигнут последний элемент ассоциативного массива, последующее обращение к этой функции приведет к возврату в списковом контексте пустого списка, а в скалярном — неопределенного значения undef , которые трактуются в булевом контексте как «ложь». Следующий оператор цикла будет последовательно выводить пары ключ/значение массива
while (($key, $value) = each(%hash)) {
  print "$key => $value\n";
}
Результат выполнения этого цикла представлен ниже:
Чаунин => 218-001-001 
Матросов => 217-000-001
редактор => 217-000-009
Иногда необходимо знать множество ключей всех элементов ассоциативного массива или множество их значений. Для этих целей в языке предусмотрены две стандартные функции — keys и values, которые представляют в виде списка соответственно ключи и значения всех элементов ассоциативного массива. Например, следующие два оператора
print join(" ", keys(%hash)), "\n";
print join(" ", values($hash)), "\n";
отобразят на экране монитора ключи и значения всех элементов ранее определенного хэш-массива %hash
Чаунин Матросов редактор 
216-001-001 188-000-009 199-000-009
Для распечатки ключей и значений элементов ассоциативного массива была использована стандартная функция join, которая объединяет элементы списка в одну строку, вставляя между ними разделитель, определяемый первым параметром. Это одна из стандартных функций Perl для работы со списками. Если бы мы попытались распечатать ключи и значения элементов хэш-массива без обращения к этой функции, то результат получился бы плохо читаемым, так как и ключи, и значения были бы представлены строками, в которых они шли бы сплошным потоком, как показано ниже:
ЧаунинМатросовредактор 
218-001-001188-000-009199-000-009
Результат, аналогичный использованию функции join с пробелом в качестве разделителя между элементами списка, можно получить и другим способом. Для этого следует сохранить результаты выполнения функций keys и values в скалярных массивах и подставить их значения в строку вывода функцией print:
@keys = keys(%hash); 
@values = values (%hash);
print "@keys\n";
print "@values\n";
Обратим внимание читателя, что при получении ключей и значений элементов ассоциативного массива они располагаются в списке не в том порядке, как мы их задавали, например, элемент с ключом Чаунин идет первым в списке, хотя в конструкторе мы задавали его вторым. Дело в том, что при создании элементов ассоциативного массива они располагаются в памяти в порядке, удобном для их последующего извлечения. Этот процесс контролируется специальной хэш-функцией (отсюда и второе название этих массивов), что и приводит к сохранению элементов ассоциативного массива не в том порядке, как они задаются, Для упорядочивания ключей или значений элементов массива следует применить к полученному списку операцию сортировки, представленную стандартной функцией sort.
К хэш-массивам можно применять функцию reverse( ), в этом случае осуществляющую обращение хэш-массива, при котором значения становятся ключами, а ключи значениями:
#hash = (
         "Чаунин"   => "218-001-001"
         "Матросов" => "217-000-001"
         "редактор" => "217-000-009" 
        );
%reverse = reverse(%hash);
#%reverse = (
#	218-001-001 => "Чаунин"
#	217-000-001 => "Матросов"
#	217-000-009 => "редактор"
#	)
При обращении хэш-массива следует помнить, что если в нем несколько ключей имеют одно и то же значение, то в обращенном хаш-массиве мы получим один ключ, соответствующий значению указанных элементов исходного хэш-массива и ассоциированный с одним из ключей исходного хэш-массива (с каким именно — зависит от алгоритма хэширования и в общем случае непредсказуемо). Результатом выполнения фрагмента сценария:
%salary = (
           Воb   => 5000,
           Mike  => 6000,
           Steve => 50OO,
           John  => 5000,
           Paul  => 6000
);
%reverse = reverse(%salary); # Обращение хэша 
# Печать обращенного хэша 
foreach $i (keys %reverse ) {
  print $i." => ", $reverse{$i}, "\n"; 
}
будет следующий вывод обращенного исходного хэш-массива:
5000 => Воb 
6000 => Paul

Связанный список

В качестве примера использования ассоциативного массива мы реализуем абстрактный тип данных — связанный список. Абстрактный тип данных представляет собой множество объектов вместе с набором допустимых над ними операций. Связанный список состоит из множества узлов. Каждый узел содержит некоторое значение и ссылку на следующий за ним узел. Последний узел содержит только значение элемента и не имеет ссылки на следующий, что обычно реализуется в виде пустой ссылки. Для окончательного задания связанного списка следует объявить переменную, указывающую на первый элемент списка, который называется заголовкам списка.
Для связанного списка определяются операции выбора, удаления и добавления узла, причем последняя операция выполняется относительно некоторого заданного в списке узла — обычно узел добавляется после некоторого узла.
Хэш-массив представляет собой тип данных, с помощью которого связанный список реализуется естественным образом: достаточно значения узлов использовать в качестве ключей элементов массива, а значению каждого элемента массива присвоить значение следующего за ним в списке узла. Таким образом, каждый узел списка представляется одним элементом кэш-массива, причем ключ элемента — это значение узла, а значение элемента — ссылка на следующий узел. Значением последнего узла будет пустая строка. Для того чтобы начать работать со списком, следует задать переменную, в которой хранится значение первого элемента связанного списка. Оно является ключом элемента ассоциативного массива, который представляет первый узел нашего связанного списка. Обычно эту переменную называют заголовком списка. Код листинга 3.2 реализует связанный список из пяти узлов.
Листинг 3.2. Реализация связанного списка
%linked_list = ( 
                 "А1" => "А2", 
                 "А2" => "А3",
                 "A3" => "А4",
                 "A4" => "А5",
                 "A5" => ""
               );
$header = "А1";
Напечатать все элементы связанного списка можно с помощью подпрограммы, код которой представлен в листинге 3.3. При вызове этой подпрограммы следует передать в нее в качестве параметра заголовок списка.
Листинг 3.3. Подпрограмма печати связанного списка
sub printLinkedList {
  # Получение заголовка 
  $item = shift; # используется массив @_
  # Печать значения первого узла 
  $i = 1; 
  print "Элемент $i: $item", "\n";
  # Печать значений узлов связанного списка,
  # пока не дойдем до пустой строки "" 
  while ($linked_list{$item}) { 
    ++$i;
    print "Элемент $i: $linked_list{$item}", "\n"; 
    $item = $linked_list{$item}; # ссылка на следующий узел
  }
}
Добавив в конец кода из листинга 3.2 оператор вызова подпрограммы печати содержимого связанного списка:
PrintLinkedList($header);
а также код самой подпрограммы printLinkedList, получим следующий вывод из нашего сценария
Элемент1: А1
Элемент2: A2
Элемент3: A3
Элемент4: A4
Элемент5: A5
Теперь обратимся к реализации операции добавления нового узла в связанный список. Для ее выполнения нам необходимо знать номер узла, после которого следует добавить узел, а также его значение. Эти величины должны быть переданы в подпрограмму добавления элемента. Ее код представлен в листинге 3.4.
Листинг 3.4. Подпрограмма добавления нового узла в связанный список
sub addNode {
  # Получение номера узла, после которого добавляем
  $number = shift;
  # Получение значения узла
  $element = shift;
  # Получение заголовка узла
  $item = shift;
  # Получение узла с номером $number 
  $i = 0;
  whi1e(++$i < $number) { 
    $item = $linked_list{$item}; # ссылка на следующий узел
  }
  # Запомнили указатель узла, после которого добавляем
  $temp = $linked_list{$item};
  # Добавили новый узел
  $linked_list{$element} = $temp; 
  # Изменили указатель в узле, после которого добавили.
  # на добавленный элемент 
  $linked_list{$item} = $element;
}
Добавим теперь в листинг 3.2 код разработанной подпрограммы добавления узла в связанный список вместе с операторами добавления после второго элемента списка узла со значением X и последующей печати нового содержимого списка:
addNode(2, "X", $header);
printLinkedList($header);
Результат выполнения нашего нового сценария представлен ниже:
Элемент 1:	А1
Элемент 2:	А2
Элемент 3:	X
Элемент 4:	A3
Элемент 5:	A4
Элемент 6:	А5

Следующая страница Содержание главы


Реклама