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

Материал из Википедии — свободной энциклопедии

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

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

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

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

В разных реализациях ассоциативного массива семантика и названия операций могут отличаться.

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

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня, таких как Perl, PHP, Python, Ruby, Tcl, JavaScript и др.

[править] Примеры

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

Ярким примером из жизни также является база данных доменных имен в Интернет, которая доменному имени сопоставляет IP-адрес.

[править] Расширения ассоциативного массива

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

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

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

[править] Реализации ассоциативного массива

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

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

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

У каждой реализации есть свои достоинства и недостатки. Важно, чтобы все три операции выполнялись как в среднем, так и в худшем случае за время O(logn), где 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>::iterator ifind = book.find(name);
            if (ifind != book.end())
                cout << (*ifind).first << "'s phone is " << (*ifind).second << endl;
            else
                cout << name << " not find" << endl;
        } else if(cmd == "del") {
            cin >> name;
            book.erase(name);
            cout << "Deleted" << endl;
        } else if(cmd == "view") {
            map<string,string>::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;
        }
    }
    return 0;
}

[править] Ruby

Класс Hash из стандартной библиотеки Ruby поддерживает операции [] (insert), []= (find), 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 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 = (
    'cat' => 'kitten',
    'dog' => 'puppy',
    'cow' => 'calf'
);
print $hash{'cat'}; # Напечатает kitten
print keys %hash; # Вывод всех ключей. Напечатает catdogcow 
print values %hash; # Вывод всех значений. Напечатает kittenpuppycalf
print %hash; # Напечатает catkittencowcalfdogpuppy

[править] Delphi

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

procedure TForm1.Button1Click(Sender: TObject);
var
  DataField: TStrings;
  i: Integer;
begin
  DataField := TStringList.Create;
 
  DataField.Add(Format('%s=%s', ['Sally Smart', '555-9999']));
  DataField.Add(Format('%s=%s', ['John Doe', '555-1212']));
  DataField.Add(Format('%s=%s', ['J. Random Hacker', '553-1337']));
 
  // доступ к значению и вывод его в message box
  ShowMessage(DataField.Values['Sally Smart']);
 
  // проход по ассоциативному массиву 
  for i := 0 to DataField.Count - 1 do
  begin
    ShowMessage('Number for ' + DataField.Names[i] + ': ' + DataField.ValueFromIndex[i]);
  end;
 
  DataField.Free;
end;

[править] См. также

• Хэш-таблица
• Сбалансированное дерево поиска
• Красно-чёрное дерево

[править] Ссылки

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

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

• страница помощи std::map на MSDN
• страница помощи std::map на SGI STL
• страница помощи std::hashmap SGI STL

• Класс Hash в Ruby
• Модуль Array в Tcl
• Класс Dict в Python
• Класс TreeDictionary в C#
• NIST's Dictionary of Algorithms and Data Structures: Associative Array
• NIST's Dictionary of Algorithms and Data Structures: Association List

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