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

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

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

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня (Perl, PHP, Python, Ruby и др.). В языке C++ поддержка ассоциативных массивов включена в стандартную библиотеку (контейнер map).

[править] Достоинства

• Наглядность, удобство для человека, возможность присвоить каждому элементу осмысленный идентификатор
• Лёгкость добавления или удаления элементов, так как в общем случае не требуется изменения позиций других
• Ассоциативный массив обобщает собой сразу несколько типов данных (записи или структуры, обычные массивы, простейшие объекты)

[править] Недостатки

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

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

[править] 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  ; # Вывод всех ключей. Напечатает catdogcow 
print values ; # Вывод всех значений. Напечатает kittenpuppycalf
print %hash ; #Напечатает catkittencowcalfdogpuppy

[править] Delphi

Delphi не имеет прямых средств работы с ассоциативными массивами. Однако, вы можете имитировать ассоциативные массивы, используя объект TStrings. Например:

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;

[править] С

В языке Си может использоватся подобие ассоциативного массива

enum notes {DO,RE, MI, FA, SOL, LA, SI}; //Объявляем ключи
unsigned short int sample[7];            //Создаем массив
 
//Обращаемся к элемента массива по именованным ключам
//Задаем частоту нотных семплов в герцах
sample[DO]=262;
sample[RE]=294; 
sample[MI]=330;
sample[FA]=349;
sample[SOL]=392;
sample[LA]=440;
sample[SI]=494;

Хэш может быть "связан" (tie) с внешним источником данных, например с файлом или же с таблицей базы данных.

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