Asocijativni niz

U informatici, asocijativni niz, mapa ili rečnik, predstavlja apstraktni tip podataka skup parova ključ:vrednost, tako da je ključ jedinstven, odnosno pojavljuje se samo jednom u skupu.

Operacije vezane za ovaj tip podataka:^[1]^[2]

dodavanje parova skupu
uklanjanje parova iz skupa
izmena vrednosti postojećih parova
pronalaženje vrednosti vezane za određen ključ

Problem rečnika predstavlja zadatak dizajniranja strukture podataka, koja implementira asocijativni niz. Uobičajeno rešenje problema rečnika su heš tabele, dok je u nekim slučajevima problem moguće rešiti korišćenjem direkotno povezanih nizova, binarnih stabala pretrage ili drugih specijalizovanih struktura.^[1]^[2]^[3] Mnogi programski jezici uključuju asocijativne nizove u osnovne tipove podataka, dok su za mnoge druge dostupni u bibliotekama. Asocijativna memorija je direktna hardverska podrška asocijativnim nizovima.

Asocijativni nizovi imaju široku primenu uključujući i osnovne šablone poput memoizacije i dekoratora šablona.^[4]

Operacije

U asocijativnom nizu, veza između ključa i vrednosti je poznata kao vezivanje, a isti termin se može odnositi i na proces kreiranja nove veze.

Operacije koje su obično definisane su:^[1]^[2]

Dodavanje ili umetanje: dodaje novi ključ:vrednost par u kolekciju, vezujući novi ključ i dodeljenu vrednost. Argumenti ove operacije su ključ i vrednost.
Zamena: menja vrednost jednog ključ:vrednost para koji se već nalazi u kolekciji, vezujući stari ključ i novu vrednost. Kao i kod umetanja, argumenti ove operacije su ključ i vrednost.
Uklanjanje ili brisanje: uklanja ključ:vrednost par iz kolekcije, brišući vezu između datog ključa i njegove vrednosti. Argument ove operacije je ključ.
Pretraga: pronalazi vrednost (ukoliko postoji) koja je vezana za dati ključ. Argument ove operacije je ključ, a vraća se vrednost. Ukoliko vrednost nije pronađena, neke implementacije asocijativnih nizova kreiraju izuzetak.

Dodatno, asocijativni nizovi mogu uključiti druge operacije poput određivanje broja vezivanja ili konstruisanje iteratora kojim bi se, kroz petlju, prošlo kroz sva vezivanja. Obično se za takvu operaciju red u kome se vraćaju vezivanja bira slučajno. Multimapa generalizuje asocijativni niz omogućujući da više vrednosti budu vezane za jedan ključ.^[5] Dvosmerna mapa je povezani apstraktni tip podataka, u kojoj vezivanja rade u oba smera: svaka vrednost mora biti vezana jedinstvenim ključem, a druga operacija pretrage uzima vrednost kao argument i pronalazi ključ vezan za tu vrednost.

Primeri

Pretpostavimo da je skup iznajmljivanja knjiga u biblioteci predstavljen u obliku strukture podataka. Svaka knjiga u biblioteci, u određenom trenutku, može biti iznajmljena od strane samo jednog člana. Takođe, jedan član može iznajmiti više knjiga. Stoga, informacije o tome koja knjiga je izdata kom članu, može biti predstavljena asocijativnim nizom, gde su knjige ključevi, a članovi su vrednosti. Na primer (koristeći Pajton notaciju, gde su veze predstavljene postavljanjem kolone između ključa i vrednosti), tekuća iznajmljivanja mogu biti prikazana asocijativnim nizom.

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

Operacija pretrage sa ključem "Great Expectations", u ovom nizu bi vratila ime osobe koja je iznajmila tu knjigu, Džona. Ukoliko bi Džon vratio knjigu, to bi prouzrokovalo operaciju brisanja u nizu, a ako bi Pet iznajmio novu knjigu, to bi dovelo do operacije dodavanja, a što bi dovelo do novog stanja.

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

U novom stanju, ista pretraga sa ključem "Great Expectations" bi stvorila izuzetak, pošto ovaj ključ više ne postoji u nizu.

Implementacija

Za rečnike sa malim brojem vezivanja, ima smisla implementirati rečnik koristeći asocijativnu listu, povezanu listu vezivanja. U ovoj implementaciji, vremenska složenost je linearna i zavisi od ukupnog broja vezivanja. Međutim, laka je za implementaciju i faktori vremenske složenosti su mali.^[1]^[6] Još jedna jednostavna implementaciona tehnika, upotrebljiva kada je ključ ograničen na uzak skup celih brojeva, je direktno adresiranje u nizu: vrednost datog ključa k se čuva u ćeliji niza A[k], ili ukuoliko nema vezivanja za k, onda ćelija čuva promenljive čuvare koje daju naznaku nepostojanja veze. Pored toga što je jednostavna, ova tehnika je i brza: svaka operacija nad rečnikom ima konstantno trajanje. Međutim, prostorna složenost je velika, što ovu tehniku čini nepraktičnom.^[3] Najčešće korišćena univerzalna implementacija asocijativnog niza je heš tabela: Niz vezivanja sa heš funkcijom koja mapira svaki mogući ključ u indeks niza. Osnovna ideja heš tabela je da je vezivanje za svaki dati ključ, sačuvano na poziciji dobijenoj primenom heš funkcije na dati ključ, a operacije pretrage se vrše posmatranjem te ćelije niza i upotrebom veze u njoj. Međutim, rečnici zasnovani na heš tablicama, moraju biti u mogućnosti da rukuju kolizijama, koje nastaju kada su dva ključa mapirana na isti indeks od strane heš funkcije. Mnoge različite strategije za izbegavanje kolizije su razvijene, a često su bazirane na zatvorenom heširanju ili heš vezivanju.^[1]^[2]^[3] Rečnici takođe mogu biti skladišteni u obliku binarnih stabala pretrage ili u strukturama podataka specijalizovanim za posebne vrste ključeva kao što su radiks stabla, Džudi nizovi ili fon Emde Boa stabla, ali su te implementacije manje efikasne od heš tabela, a takođe su restriktivnije prema tipovima podataka kojim mogu da rukuju. Njihova prednost je u tome što mogu da rukuju većim brojem operacija od osnovnih asocijativnih nizova, kao što su pronalaženje vezivanja čiji je ključ najbliži datom ključu, a dati ključ se ne nalazi u skupu vezivanja.

Jezička podrška

Asocijativni nizovi mogu biti implementirani u bilo kom jeziku u obliku paketa, dok su kod nekih prisutni u standardnim bibliotekama. U nekim jezicima, ne samo da su implementirani u standardnim bibliotekma, već imaju i posebnu sintaksu.

Ugrađena podrška za asocijativne nizove je uvedena u SNOBOL4, pod nazivom "tabela“. SETL ih je podržavao kao jedna od mogućih implementacija setova i mapa. Mnogi moderni skript jezici, počevši od AWK i uključujući Perl, Tcl, JavaScript, Pajton, Ruby i Lua podržavaju asocijativne nizove kao primarne kontejnerske tipove. U mnogim drugim jezicima dostupni su kao funkcije biblioteke bez specijalne sintakse.

Reference

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

Spoljašnje veze

NIST's Dictionary of Algorithms and Data Structures: Associative Array

[gt-1] v ^g ^d Goodrich, Michael T.; Tamassia, Roberto (2006), „9.1 The Map Abstract Data Type”, Data Structures & Algorithms in Java (4th izd.), Wiley, str. 368—371

[ms-2] v ^g Mehlhorn, Kurt; Sanders, Peter (2008), „4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox, Springer, str. 81—98

[clrs-3] v Cormen, Thomas H. (2001), „11 Hash Tables”, Introduction to Algorithms, Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2nd izd.), MIT Press and McGraw-Hill, str. 221—252, ISBN 978-0-262-03293-3

[decorator-4] Goodrich & Tamassia 2006, str. 597–599

[5] Goodrich & Tamassia 2006, str. 389–397

[6] „When should I use a hash table instead of an association list?”. lisp-faq/part2. 20. 2. 1996.

[1]

[2]

[3]

[4]

[5]

[6]