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

Асоціативний масив (словник) - абстрактний тип даних ( інтерфейс до сховища даних), що дозволяє зберігати пари виду "(ключ, значення)" і підтримує операції додавання пари, а також пошуку і видалення пари по ключу:

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

Передбачається, що асоціативний масив не може зберігати дві пари з однаковими ключами.

У парі (K, v) значення v називається значенням, асоційованим з ключем k . Семантика та назви вищезазначених операцій в різних реалізаціях асоціативного масиву можуть відрізнятися.

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

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

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


1. Приклади

Найпростішим прикладом асоціативного масиву є телефонний довідник. Ключем в даному випадку є номер телефону, а значенням - сукупність П.І.Б. + Адресу. Один номер телефону має одного власника, але одна людина може мати кілька номерів.

2. Розширення асоціативного масиву

Зазначені три операції часто доповнюються іншими. Найбільш популярні розширення включають наступні операції:

  • CLEAR - видалити всі записи
  • EACH - "пробігтися" по всіх збереженим парам
  • MIN - знайти пару з мінімальним значенням ключа
  • MAX - знайти пару з максимальним значенням ключа

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

3. Реалізації асоціативного масиву

Існує безліч різних реалізацій асоціативного масиву.

Найпростіша реалізація може бути заснована на звичайному масиві, елементами якого є пари (ключ, значення). Для прискорення операції пошуку можна впорядкувати елементи цього масиву по ключу і здійснювати знаходження методом бінарного пошуку. Але це збільшить час виконання операції додавання нової пари, так як необхідно буде "розсовувати" елементи масиву, щоб в утворену порожню комірку помістити новий запис.

Найбільш популярні реалізації, засновані на різних деревах пошуку. Так, наприклад, в стандартній бібліотеці STL мови С + + контейнер map реалізований на основі червоно-чорного дерева. У мовах Ruby, Tcl, Python використовується один з варіантів хеш-таблиці. Є й інші реалізації.

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

У реалізаціях, заснованих на хеш-таблицях, середній час оцінюється як O (1) , Що краще, ніж в реалізаціях, заснованих на деревах пошуку. Але при цьому не гарантується висока швидкість виконання окремої операції: час операції INSERT в гіршому випадку оцінюється як O (n) . Операція INSERT виконується довго, коли коефіцієнт заповнення стає високим і необхідно перебудувати індекс хеш-таблиці.

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


4. Підтримка асоціативних масивів в мовах програмування

4.1. Бібліотека STL мови C + +

Тут наведено найпростіше консольний додаток, що надає інтерфейс телефонної книжки. Воно реалізовано на основі контейнера map.

 # Include   # Include   # Include   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 () 

4.2. 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"  )  ; 

4.3. 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 

4.4. 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) можна шляхом успадкування класу, див. приклад.


4.5. 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 

4.6. 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  ; 

У Delphi 2009 додана підтримка дженериків та кілька стандартних класів для роботи з ними, в тому числі TDictionary.

 uses  SysUtils  ,  Generics  .  Collections  ;  var  PhoneBook  :  TDictionary <  string  ,  string>  ;  Entry  :  TPair <  string  ,  string>  ;  begin  PhoneBook  :  =  TDictionary <  string  ,  string>  .  Create  ;  PhoneBook  .  Add  (  'Sally Smart'  ,  '555-9999 '  )  ;  PhoneBook  .  Add  (  'John Doe'  ,  '555-1212 '  )  ;  PhoneBook  .  Add  (  'J. Random Hacker '  ,  '553-1337 '  )  ;  for  Entry  in  PhoneBook  do  Writeln  (  Format  (  'Number for% s:% s'  ,  [  Entry  .  Key  ,  Entry  .  Value  ]  )  )  ;  end  . 

4.7. 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  ; 

4.8. 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'); 

4.9. 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 

4.10. 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