Асоцијативни низ

У информатици, асоцијативни низ, мапа или речник, представља апстрактни тип података скуп парова кључ:вредност, тако да је кључ јединствен, односно појављује се само једном у скупу.

Операције везане за овај тип података:[1][2]

  • додавање парова скупу
  • уклањање парова из скупа
  • измена вредности постојећих парова
  • проналажење вредности везане за одређен кључ

Проблем речника представља задатак дизајнирања структуре података, која имплементира асоцијативни низ. Уобичајено решење проблема речника су хеш табеле, док је у неким случајевима проблем могуће решити коришћењем дирекотно повезаних низова, бинарних стабала претраге или других специјализованих структура.[1][2][3] Многи програмски језици укључују асоцијативне низове у основне типове података, док су за многе друге доступни у библиотекама. Асоцијативна меморија је директна хардверска подршка асоцијативним низовима.

Асоцијативни низови имају широку примену укључујући и основне шаблоне попут мемоизације и декоратора шаблона.[4]

Операције

У асоцијативном низу, веза између кључа и вредности је позната као везивање, а исти термин се може односити и на процес креирања нове везе.

Операције које су обично дефинисане су:[1][2]

  • Додавање или уметање: додаје нови кључ:вредност пар у колекцију, везујући нови кључ и додељену вредност. Аргументи ове операције су кључ и вредност.
  • Замена: мења вредност једног кључ:вредност пара који се већ налази у колекцији, везујући стари кључ и нову вредност. Као и код уметања, аргументи ове операције су кључ и вредност.
  • Уклањање или брисање: уклања кључ:вредност пар из колекције, бришући везу између датог кључа и његове вредности. Аргумент ове операције је кључ.
  • Претрага: проналази вредност (уколико постоји) која је везана за дати кључ. Аргумент ове операције је кључ, а враћа се вредност. Уколико вредност није пронађена, неке имплементације асоцијативних низова креирају изузетак.

Додатно, асоцијативни низови могу укључити друге операције попут одређивање броја везивања или конструисање итератора којим би се, кроз петљу, прошло кроз сва везивања. Обично се за такву операцију ред у коме се враћају везивања бира случајно. Мултимапа генерализује асоцијативни низ омогућујући да више вредности буду везане за један кључ.[5] Двосмерна мапа је повезани апстрактни тип података, у којој везивања раде у оба смера: свака вредност мора бити везана јединственим кључем, а друга операција претраге узима вредност као аргумент и проналази кључ везан за ту вредност.

Примери

Претпоставимо да је скуп изнајмљивања књига у библиотеци представљен у облику структуре података. Свака књига у библиотеци, у одређеном тренутку, може бити изнајмљена од стране само једног члана. Такође, један члан може изнајмити више књига. Стога, информације о томе која књига је издата ком члану, може бити представљена асоцијативним низом, где су књиге кључеви, а чланови су вредности. На пример (користећи Пајтон нотацију, где су везе представљене постављањем колоне између кључа и вредности), текућа изнајмљивања могу бити приказана асоцијативним низом. 

{
    "Great Expectations": "John",
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice"
}

Операција претраге са кључем "Great Expectations", у овом низу би вратила име особе која је изнајмила ту књигу, Џона. Уколико би Џон вратио књигу, то би проузроковало операцију брисања у низу, а ако би Пет изнајмио нову књигу, то би довело до операције додавања, а што би довело до новог стања. 

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

У новом стању, иста претрага са кључем "Great Expectations" би створила изузетак, пошто овај кључ више не постоји у низу.

Имплементација

За речнике са малим бројем везивања, има смисла имплементирати речник користећи асоцијативну листу, повезану листу везивања. У овој имплементацији, временска сложеност је линеарна и зависи од укупног броја везивања. Међутим, лака је за имплементацију и фактори временске сложености су мали.[1][6] Још једна једноставна имплементациона техника, употребљива када је кључ ограничен на узак скуп целих бројева, је директно адресирање у низу: вредност датог кључа к се чува у ћелији низа А[к], или укуолико нема везивања за к, онда ћелија чува променљиве чуваре које дају назнаку непостојања везе. Поред тога што је једноставна, ова техника је и брза: свака операција над речником има константно трајање. Међутим, просторна сложеност је велика, што ову технику чини непрактичном.[3] Најчешће коришћена универзална имплементација асоцијативног низа је хеш табела: Низ везивања са хеш функцијом која мапира сваки могући кључ у индекс низа. Основна идеја хеш табела је да је везивање за сваки дати кључ, сачувано на позицији добијеној применом хеш функције на дати кључ, а операције претраге се врше посматрањем те ћелије низа и употребом везе у њој. Међутим, речници засновани на хеш таблицама, морају бити у могућности да рукују колизијама, које настају када су два кључа мапирана на исти индекс од стране хеш функције. Многе различите стратегије за избегавање колизије су развијене, а често су базиране на затвореном хеширању или хеш везивању.[1][2][3] Речници такође могу бити складиштени у облику бинарних стабала претраге или у структурама података специјализованим за посебне врсте кључева као што су радикс стабла, Џуди низови или фон Емде Боа стабла, али су те имплементације мање ефикасне од хеш табела, а такође су рестриктивније према типовима података којим могу да рукују. Њихова предност је у томе што могу да рукују већим бројем операција од основних асоцијативних низова, као што су проналажење везивања чији је кључ најближи датом кључу, а дати кључ се не налази у скупу везивања.

Језичка подршка

Асоцијативни низови могу бити имплементирани у било ком језику у облику пакета, док су код неких присутни у стандардним библиотекама. У неким језицима, не само да су имплементирани у стандардним библиотекма, већ имају и посебну синтаксу.

Уграђена подршка за асоцијативне низове је уведена у SNOBOL4, под називом "табела“. SETL их је подржавао као једна од могућих имплементација сетова и мапа. Многи модерни скрипт језици, почевши од AWK и укључујући Perl, Tcl, JavaScript, Пајтон, Ruby и Lua подржавају асоцијативне низове као примарне контејнерске типове. У многим другим језицима доступни су као функције библиотеке без специјалне синтаксе.

Референце

  1. ^ а б в г д Goodrich, Michael T.; Tamassia, Roberto (2006), „9.1 The Map Abstract Data Type”, Data Structures & Algorithms in Java (4th изд.), Wiley, стр. 368—371 
  2. ^ а б в г Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox, Springer, стр. 81—98 
  3. ^ а б в Cormen, Thomas H. (2001), „11 Hash Tables”, Introduction to Algorithms, Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2nd изд.), MIT Press and McGraw-Hill, стр. 221—252, ISBN 978-0-262-03293-3 
  4. ^ Goodrich & Tamassia 2006, стр. 597–599
  5. ^ Goodrich & Tamassia 2006, стр. 389–397
  6. ^ „When should I use a hash table instead of an association list?”. lisp-faq/part2. 20. 2. 1996. 

Спољашње везе