Asszociatív tömb

Az asszociatív tömb (angolul map vagy dictionary) adatszerkezet kulcs-érték párokat tartalmaz, ahol egy kulcshoz pontosan egy érték tartozik. Az asszociatív tömb a hagyományos tömb olyan bővítésének tekinthető, ahol a kulcsok nem feltétlenül alkotnak folytonos résztartományt. Míg a hagyományos tömb általában csak felsorolható (egyes nyelvekben csak pozitív egész) indexekkel rendelkezhet, az asszociatív tömb kulcsa lehet karakterfüzér vagy összetett típus is. Például a következő asszociatív tömb a hónapok magyar nevéhez rendeli a hónapok sorszámát:

{"január":1, "február":2, "március":3, "április":4, "május":5, "június":6, "július":7, "augusztus":8, "szeptember":9, "október":10, "november":11, "december":12}

A fordított esethez elegendő lenne egy egyszerű tömb, mivel az 1..12 számok folytonos tartományt alkotnak. (Egyes nyelveken csak nullától kezdődhet a tömb számozása, ezért vagy az indexeket kell módosítanunk, vagy a nulladik indexre be kell iktatnunk egy helykitöltő elemet.)

Az asszociatív tömb hasonlít a hagyományos tömbre abban, hogy egy adott kulcshoz hatékonyan lehet megkeresni az értéket, de egy adott értékhez csak lassan lehet megtalálni a rá hivatkozó kulcs(ok)at. Míg a hagyományos tömbben egy kulcshoz tartozó érték mindig konstans időben megtalálható, az asszociatív tömb egyes megvalósításaiban ez O(log n) időbe is kerülhet. Ez a gyakorlatban nem jelentős lassulás, hiszen a logaritmus függvény nagyon lassan növekszik. Míg a hagyományos tömbben az elemek sorrendje egyértelműen meghatározott, az asszociatív tömbben ez nem feltétlenül igaz; az adatszerkezet bejárásakor az elemeket általában valamilyen önkényes sorrendben kapjuk vissza.

Az, hogy mi történik, ha nem létező kulcsra hivatkozunk, az adott nyelvtől és környezettől függ. A szokásos megoldás vagy valamilyen hibajelzés, vagy egy speciális érték visszaadása. Ahol hibajelzés a válasz, lehetőség van a kulcs meglétének ellenőrzésére a hivatkozás előtt.

Példák különböző programnyelvekben

Java

A standard könyvtár Map interfésze jelzi ezt az adattípust, általában a HashMap konkrét megvalósítását használják. Nem létező kulcs esetén null értéket kapunk vissza, de egy adott kulcs megléte kézzel is ellenőrízhető.

Map<String, Integer> hónapok = new HashMap<String, Integer>();
hónapok.put("január", 1);
hónapok.put("február", 2);
hónapok.put("március", 3);
//többi hónap kihagyva

boolean vanHarmadik = hónapok.containsKey("március"); // eredmény: true
Integer harmadik = hónapok.get("március"); // eredmény: 3
boolean vanZöldség = hónapok.containsKey("cékla"); // eredmény: false
Integer zöldség = hónapok.get("cékla"); // eredmény: null

Python

A beépített dict adattípus valósítja meg. Egy adott kulcs létezését az in operátorral ellenőrizhetjük Nem létező kulcs hivatkozásakor a beépített KeyError kivétel váltódik ki.

honapok = {"január":1, "február":2, "március":3, "április":4, "május":5, "június":6,
           "július":7, "augusztus":8, "szeptember":9, "október":10, "november":11, "december":12}

van_harmadik = "március" in honapok # eredmény: True
harmadik = honapok["március"]       # eredmény: 3
van_zoldseg = "cékla" in honapok    # eredmény: False

zoldseg = honapok["cékla"]          # a sor végrehajtásakor KeyError kivétel dobódik
zoldseg = honapok.get("cékla")      # előző péda szebben, get() metódussal. Eredmény itt: None (nincs)