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

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

Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

  • INSERT(ключ, значение)
  • FIND(ключ)
  • REMOVE(ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.

В паре (k, v) значение v называется значением, ассоциированным с ключом k. Семантика и названия вышеупомянутых операций в разных реализациях ассоциативного массива могут отличаться.

Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, информации о том, успешно ли была выполнена данная операция).

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

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня, таких, как Perl, PHP, Python, Ruby, Tcl, JavaScript[1] и др. Для языков, которые не имеют встроенных средств работы с ассоциативными массивами, существует множество реализаций в виде библиотек.

Содержание

Примеры

Простейшим примером ассоциативного массива является телефонный справочник. Ключом в данном случае является номер телефона, а значением — совокупность ФИО + адрес. Один номер телефона имеет одного владельца, но один человек может иметь несколько номеров.

Расширения ассоциативного массива

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

  • CLEAR — удалить все записи
  • EACH — «пробежаться» по всем хранимым парам
  • MIN — найти пару с минимальным значением ключа
  • MAX — найти пару с максимальным значением ключа

В последних двух случаях необходимо, чтобы на ключах была определена операция сравнения.

Реализации ассоциативного массива

Существует множество различных реализаций ассоциативного массива.

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

Наиболее популярны реализации, основанные на различных деревьях поиска. Так, например, в стандартной библиотеке STL языка С++ контейнер map реализован на основе красно-чёрного дерева. В языках Ruby, Tcl, Python используется один из вариантов хэш-таблицы. Есть и другие реализации.

У каждой реализации есть свои достоинства и недостатки. Важно, чтобы все три операции выполнялись как в среднем, так и в худшем случае за время O(\log n), где n — текущее количество хранимых пар. Для сбалансированных деревьев поиска (в том числе для красно-чёрных деревьев) это условие выполнено.

В реализациях, основанных на хэш-таблицах, среднее время оценивается как O(1), что лучше, чем в реализациях, основанных на деревьях поиска. Но при этом не гарантируется высокая скорость выполнения отдельной операции: время операции INSERT в худшем случае оценивается как O(n). Операция INSERT выполняется долго, когда коэффициент заполнения становится высоким и необходимо перестроить индекс хэш-таблицы.

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

Поддержка ассоциативных массивов в языках программирования

Библиотека STL языка C++

Здесь приведено простейшее консольное приложение, предоставляющее интерфейс телефонной книжки. Оно реализовано на основе контейнера map.

#include <iostream>
#include <string>
#include <map>
 
using namespace std;
 
int main()
  {
    string cmd, name, phone;
    map< string, string > book;
 
    while( cin >> cmd )
      {
        if ( cmd == "add" )
          {
            cin >> name >> phone;
            book[ name ] = phone;
            cout << "Added" << endl;
          }
        else if ( cmd == "find" )
          {
            cin >> name;
            map< string, string >::const_iterator ifind = book.find( name );
 
            if ( ifind != book.end() )
              cout << ifind->first << "'s phone is " << ifind->second << endl;
            else
              cout << name << " not found" << endl;
          }
        else if ( cmd == "del" )
          {
            cin >> name;
            book.erase( name );
            cout << "Deleted" << endl;
          }
        else if ( cmd == "view" )
          {
            map< string, string >::const_iterator i;
 
            for( i = book.begin(); i != book.end() ; ++i )
              cout << i->first << "\t " << i->second << endl;
          }
        else if ( cmd == "quit" )
          return 0;
        else
          cerr << "Bad command '" << cmd << "'" << endl;
    } // while( cin >> cmd )
 
    return 0;
  } // int main()

Java

В языке Java ассоциативный массив именуется картой(map) и имеет соответствующий интерфейс в стандартном Java API: java.util.Map Стандартный Java SDK включает в себя ряд реализаций этого интерфейса: HashMap, LinkedHashMap, ConcurrentHashMap, EnumMap, TreeMap и другие.

Map<String, String> map = new HashMap<String, String>();
map.put("a","apricot");
map.put("b","banana");
map.put("c","cherry");
String s = map.get("b");

Ruby

Класс Hash из стандартной библиотеки Ruby поддерживает операции [] (find), []= (insert), delete, each, keys, values, а также множество других.

Ниже приведён код с примерами выполнения отдельных операций.

# телефонная книга
phone_book = {'Ivan'=>'+74951234567', 'Anna'=>'+74951112233'}
phone_book['Ivan'] # равно '+74951234567'
phone_book['Peter'] = '+74952223344'  # добавили новую пару 
phone_book.delete('Anna') # удалили пару ('Anna', '+74951112233')
 
phone_book.each do |key, value| # выведем все записи
 puts "%20s %10s" % [key, value]
end
 
puts phone_book.values # вывести все номера телефонов

Ниже приведён код с реализацией консольного приложения «телефонная книжка».

require 'yaml'
book = {}
while line = STDIN.readline
  cmd, name, phone = line.split
  case cmd
  when 'insert'
    book[name] = phone
  when 'find'
    puts "#{name}'s phone is #{book[name]}"
  when 'del'
    book.delete(name)
  when 'view'
    book.each {|n,p| puts "#{n}\t #{p}" }
  when 'save'
    File.open(name,'w+'){|f| f.write(book.to_yaml)}
  when 'load'
    book = YAML.load_file(name)
  when 'quit'
    exit 0;
  else
    puts "Bad command '#{cmd}'";
  end
end

Python

Встроенный в Python тип ассоциативного массива называется словарём, элементами которого являются пары ключей и соответствующих им значений.

d1 = dict(a=10, b=20)
d2 = {'a': 10, 'b': 20}
d1[100] = 123
d2['c'] = 321
d1[100] = 1023

Здесь были показаны два способа написания литерала словаря и продемонстрировано, что ключом может быть объект любого неизменяемого (в нотации python) типа. Добавление нового объекта в словарь не требует предварительных проверок: если ранее ключу уже соответствовало некоторое значение, оно будет перезаписано (Подробнее см. Python Tutorial, Dictionaries (англ.)). Другие операции со словарем:

if 'a' in d1:    # проверка наличия ключа
    del d1['a']        # удаление ключа (и значения)
val = d1.get('a', 'default value')   # получение значения по ключу или значения 
                                     # по умолчанию в случае отсутствия ключа
val = d1.setdefault('a', 'default value')   # получение значения по ключу или значения 
                       # по умолчанию в случае отсутствия ключа (при этом
                       # значение записывается в словарь)
d1.keys()              # список ключей
d1.values()            # список значений
d1.items()             # список пар ключ-значение

На Python весьма просто можно написать свой класс, который будет вести себя подобно словарю. Для этого необходимо лишь определить в своем классе соответствующие методы (см. Python Reference Manual, Emulating container types (англ.)).

Расширить свойства встроенного типа словаря (dict) можно путем наследования класса, см. пример.

Perl

Ассоциативный массив (в Perl принято называть его хешем — англ. hash[2]) является встроенным типом данных. Хеш можно создавать поэлементно либо целиком, присвоив ему значения списка, в котором элементы записаны в виде пар «ключ — значение», внутри пары элементы могут разделяться как традиционным путём (например, запятой), так и при помощи оператора =>:

# Поэлементное присваивание
$hash{'horse'} = 'colt';
$hash{'sheep'} = 'lamb';
 
# Вывод количества ключей хеша. Напечатает 2
print scalar keys %hash;
 
# Присваивание списка
# Значения для ключей 'horse' и 'sheep' будут потеряны
%hash = (
    'cat' => 'kitten',
    'dog' => 'puppy',
    'cow' => 'calf',
);
 
print $hash{'cat'}; # Напечатает kitten
print keys %hash; # Вывод всех ключей. Напечатает catdogcow 
print values %hash; # Вывод всех значений. Напечатает kittenpuppycalf
print %hash; # Напечатает catkittencowcalfdogpuppy

Delphi

Delphi до 2007 версии не имело прямых средств работы с ассоциативными массивами. Однако, вы можете имитировать ассоциативные массивы, используя различного рода списковые классы для этого: TBucketList, TObjectBucketList, THashedStringList, TStringList (как и все другие потомки TStrings, а также Memo, ListBox и др.). Например:

procedure TForm1.Button1Click(Sender: TObject);
var
  i : Integer;
  s : string;
begin
  with TStringList.Create do //создание анонимного списка (без объявления в var-секции)
    try
{1}   Values['Sally Smart'] := '555-9999'; // - добавление новой записи
{2}   Values['John Doe'   ] := '555-1212'; // - добавление ещё одной записи
{3}   Values['Sally Smart'] := '111-9999'; // - замена значения у существующей записи
{4}   Values['John Doe'   ] := '';         // - удаление записи со сдвигом списка
 
      SaveToFile(  'restore.txt'); // - сохранения списка во внешний файл
      LoadFromFile('restore.txt'); // - восстановление списка из файла
 
      s := Text;  // - сохранения списка в строке (единым текстом c CR/LF-ами)
      Text := s;  // - восстановление списка из строки (единым текстом c CR/LF-ами)
 
   // очистка и наполнение списка из специальной строки с настраиваемыми разделителями
   // Delimiter, QuoteChar - тремя записями пар [строковый ключ=значение ключа]
      DelimitedText :=
      '"Sally Smart=555-9999" "John Doe=555-1212" "J. Random Hacker=553-1337"';
 
   // TStringList, как и все потомки TStrings наделены этими 4-мя свойствами (см. выше),
   // поэтому возможно их взаимодействие, в том числе с врапперами над Ассоциативными
   // массивами, хранящимися в системных списках: Memo-полях, ListBox'ах и т.д.:
 
      Assign(ListBox1.Items);  // - очистка и восстановление списка из ListBox1
      Memo1.Lines.Values['J. Random Hacker'] := '553-1337'; // - в Memo-поле
      AddStrings(Memo1.Lines); // - добавление строчек из списка Memo-поля
 
      Clear;                   // - просто очистка списка
 
   // доступ к значению и вывод его в message box
      ShowMessage(Values['Sally Smart']);
 
   // проход по ассоциативному массиву и доступ к ключам и значениям по индексу
      for i := 0 to Count - 1 do
        ShowMessage(Format('Number for %s: %s',[Names[i],ValueFromIndex[i]]));
    finally
      Free // автоуничтожение списка - Ассоциативного массива
    end;
end;

PL/SQL

СУБД Oracle начиная с версии 9.2.0 позволяет использовать в качестве ключей помимо binary_integer и pls_integer также и строки varchar2 с длиной до 32767:

DECLARE
      TYPE year_type IS TABLE OF NUMBER INDEX BY VARCHAR2(4000);
      year_sales year_type;
      tot_sales   NUMBER;
BEGIN
      year_sales('1990') := 34000;
      year_sales('1991') := 45000;
      year_sales('1992') := 43000;
 
      tot_sales := year_sales('1990') + year_sales('1991') +
year_sales('1992');
      DBMS_OUTPUT.put_line('Total sales: ' || tot_sales);
END;

PHP

$hash = array(
    'cat' => 'kitten',
    'dog' => 'puppy',
    'cow' => 'calf'
);
print $hash['cat']; # Напечатает kitten
print_r( array_keys($hash) ); # Вывод всех ключей. 
print_r( array_values($hash) ); # Вывод всех значений.
print_r($hash); # Напечатает Array(cat=>'kitten', dog=>'puppy', cow=>'calf');

PureBasic

В PureBasic начиная с версии 4.40 появилась встроенная поддержка ассоциативных массивов. Его называют картой (map). Пример обычного ассоциативного массива.

; Создали ассоциативный массив.
NewMap Country.s()
 
; Заполнение массива данными.
Country("GE") = "Germany"
Country("FR") = "France"
Country("UK") = "United Kingdom"
 
Debug Country("FR") ; Вывод результата "FR" в отладочное окно.
 
; Перебор всех элементов с отображением их значений в отладочном окне.
ForEach Country()
  Debug Country()
Next

Пример структурированного (каждым элементом является структура данных) ассоциативного массива.

  Structure Car ; Описание структуры.
    Weight.l
    Speed.l
    Price.l
  EndStructure
 
  NewMap Cars.Car() ; Создание структурированого ассоциативного массива.
 
  ; Заполнение массива данными.
  Cars("Ferrari F40")\Weight = 1000
  Cars()\Speed = 320
  Cars()\Price = 500000
 
  Cars("Lamborghini Gallardo")\Weight = 1200
  Cars()\Speed = 340
  Cars()\Price = 700000
 
  ; Перебор всех элеменов с отображением их значений в отладочном окне.
  ForEach Cars()
    Debug "Car name: "+MapKey(Cars()) ; Имя ключа текущего элемента массива.
    Debug "Weight: "+Str(Cars()\Weight)
  Next

JavaScript

В JavaScript понятие ассоциативного массива как такового отсутствует. Обычные массивы могут иметь только числовые индексы, потому для эмуляции ассоциативных массивов, ключами которых могут быть в том числе и строковые значения, используются объекты.

Конструкция вида myVar = { key1: value1, key2: value2, … } создает объект myVar с набором полей, каждое из которых имеет свой ключ и значение. В дальнейшем доступ к элементам этого объекта может выполняться как с использованием нотации объектов и полей (myVar.key1), так и в нотации массивов и ключей (myvar['key1']).

var hash = {
   cat : 'kitten',
   'my-dog' : 'puppy', // если ключ содержит символы, отличные от алфавитно-цифровых, он заключается в кавычки
   cow : 'calf'
};
 
document.write(hash.cat);
document.write(hash['my-dog']);
 
hash.parrot = 'Kesha'; // добавление элемента в хэш выполняется присванием нужного значения по (пока еще) не существующему ключу
document.write(hash.parrot);
 
delete hash.parrot;  // для удаление элемента используется оператор delete
delete hash['my-dog'];
hash['my-parrot'] = 'Kesha';
 
document.write(hash['my-parrot']);
 
for (var p in hash) document.write(p + ' name is ' + hash[p]); // для обхода элементов хэша в JavaScript есть специальный вид цикла for .. in

См. также

Ссылки

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

  • Контейнер map в STL

Примечания

  1. В JavaScript объекты поддерживают создание свойств с произвольным (строковым) ключом, таким образом, они реализуют также базовые свойства ассоциативного массива. См.: Объекты как ассоциативные массивы. Учебник JavaScript. Архивировано из первоисточника 23 декабря 2012. Проверено 20 декабря 2012.
  2. perldata - Perl data types  (англ.). Документация по языку Perl. Проверено 6 марта 2010.



Wikimedia Foundation. 2010.

См. также в других словарях:

  • Массив — У этого термина существуют и другие значения, см. Массив (значения). Эту страницу предлагается переименовать в Массив (информатика). Пояснение причин и обсуждение  на странице Википедия:К переименованию/4 ноября 2012. Возможно, её …   Википедия

  • Массив (значения) — Массив (фр. massif  мощный, сплошной, лат. massa  ком, кусок[1])  совокупность множества однородных предметов, составляющих единое целое, основная масса чего либо или кого либо[2], большое однородное по некоторому… …   Википедия

  • Индексный массив — (в некоторых языках программирования также таблица, ряд)  именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (в отличие от списка). Индекс массива … …   Википедия

  • Разрежённый массив — абстрактное представление обычного массива, в котором данные представленны не непрерывно, а фрагментарно. Для рационального использования памяти обычно реализуется как ассоциативный массив …   Википедия

  • ПХП — PHP Семантика: мультипарадигменный Тип исполнения: Интерпретатор компилирующего типа Появился в: 1995 г. Автор(ы): Расмус Лердорф Последняя версия: 4 …   Википедия

  • РНР — PHP Семантика: мультипарадигменный Тип исполнения: Интерпретатор компилирующего типа Появился в: 1995 г. Автор(ы): Расмус Лердорф Последняя версия: 4 …   Википедия

  • PHP — У этого термина существуют и другие значения, см. PHP (значения). PHP Семантика: мультипарадигменный …   Википедия

  • Ассоциативная память — Эта статья о компьютерных технологиях; о психологии см.: Ассоциация (психология). Ассоциативная память (АП) или Ассоциативное запоминающее устройство (АЗУ) является особым видом машинной памяти, используемой в приложениях очень быстрого поиска.… …   Википедия

  • Perl — Семантика: мультипарадигменный: императивный, объектно ориентированный, функциональный Тип исполнения: интерпретатор Появился в: 1987 Автор(ы) …   Википедия

  • Коллекция (программирование) — У этого термина существуют и другие значения, см. Коллекция. Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные исто …   Википедия

Книги


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»