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[szerkesztés]
Java[szerkesztés]
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[szerkesztés]
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)