Az informatikában az asszociatív tömb, (associative array, key-value store, map, symbol table, vagy dictionary) egy absztrakt adattípusAz informatikában az absztrakt adattípus az adattípusok matematikai modellje, amelyet az adatok felhasználójának szemszögéből történő viselkedése (szemantikája) határoz meg, különösen a lehetséges értékek, az ilyen típusú adatokon végzett lehetséges műveletek és e műveletek viselkedése szempontjából., amely (kulcs, érték) párok gyűjteményétA számítógépes programozásban a collection egy absztrakt adattípus, amely az elemek polimorf módon használható csoportosítása. tárolja úgy, hogy minden lehetséges kulcs legfeljebb egyszer jelenik meg a gyűjteményben. Matematikai értelemben az asszociatív tömb véges tartományú függvény. Támogatja a „keresés”, „eltávolítás” és „beszúrás” műveleteket.
A szótári problémaAz informatika egyik alapvető és legtöbbet vizsgált problémája a szótárprobléma, vagyis az, hogy hogyan lehet egy adathalmazt a keresési, beszúrási és törlési műveletek során fenntartani. Jól ismert, hogy egy összehasonlítás-alapú modellben ezekre a műveletekre az alsó korlát [log(n+1)] összehasonlítás mind a legjobb, mind a legrosszabb esetben. Ezt a korlátot a halmaz tömbben vagy egy tökéletesen kiegyensúlyozott bináris keresési fában való tárolásával lehet archiválni. Mindkét adatszerkezet esetében azonban a frissítésenkénti rezsi költség magas, legrosszabb esetben θ(n). az asszociatív tömböket megvalósító hatékony adatszerkezetek tervezésének klasszikus problémája. A szótári probléma két fő megoldása a hash-tábla és a keresőfaA keresési fa egy fa adatstruktúra, amely meghatározott kulcsok megtalálására szolgál egy halmazon belül...Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. "Dynamic Perfect Hashing: Upper and Lower Bounds" . SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 A probléma néha közvetlenül címzett tömbök, bináris keresőfák vagy más speciálisabb struktúrák használatával is megoldható.
Számos programozási nyelv asszociatív tömböket tartalmaz primitív adattípusként, míg sok más nyelv olyan szoftverkönyvtárat kínál, amely támogatja az asszociatív tömböket. A tartalom-címezhető memóriaA tartalom-címezhető memória (CAM) a számítógépes memória egy speciális típusa, amelyet bizonyos nagyon nagy sebességű keresési alkalmazásokban használnak. az asszociatív tömbök közvetlen hardverszintű támogatásának egyik formája.
Az asszociatív tömbök számos alkalmazással rendelkeznek, beleértve az olyan alapvető programozási mintákat, mint a memoizálásA memoizálás egy olyan optimalizálási technika, amelyet elsősorban a számítógépes programok felgyorsítására használnak azáltal, hogy a drága függvényhívások eredményeit tiszta függvényekre tárolják, és ugyanazon bemenetek ismételt előfordulásakor a gyorsítótárazott eredményt adják vissza. és a dekorációs minta., pp. 597–599.
A név nem a matematikában ismert asszociatív tulajdonságból származik. Inkább az értékek és a kulcsok társításából adódik. Nem tévesztendő össze az asszociatív processzorokkal.
Műveletek Az asszociatív tömbben a kulcs és az érték közötti társítást gyakran "leképezésnek" (mapping) nevezik; ugyanaz a szó használható egy új asszociáció létrehozásának folyamatára is.
Az asszociatív tömbhöz általában definiált műveletek a következők:
Insert vagy put hozzáad egy új párt a gyűjteményhez, leképezve a kulcsot az új értékére.A számítógépes programozásban a gyűjtemény egy absztrakt adattípus, amely az elemek polimorf módon használható csoportosítása. Minden meglévő leképezés felülíródik. A művelet argumentumai a kulcs és az érték.
Remove vagy delete eltávolít egy párt a gyűjteményből, egy adott kulcs leképezését az értékéből. Ennek a műveletnek az argumentuma a kulcs.
Lookup, find, vagy get megkeresi az adott kulcshoz kötött értéket (ha van). Ennek a műveletnek az argumentuma a kulcs, és az értéket a művelet adja vissza. Ha nem található érték, egyes keresési függvények kivételt adnak (exception), míg mások alapértelmezett értéket adnak vissza (például nullát (zero), null-értéket vagy a konstruktornak átadott konkrét értéket).
Az asszociatív tömbök más műveleteket is tartalmazhatnak, például a leképezések számának meghatározását vagy egy iterátor létrehozását, amely az összes leképezést áthurkolja.A számítógépes programozásban az iterátor egy olyan objektum, amely fokozatosan hozzáférést biztosít a gyűjtemény minden egyes eleméhez, sorrendben. Az ilyen műveleteknél a leképezések visszaadási sorrendjét általában implementáció határozza meg.
A többleképezésAz informatikában a multimap (többszörös leképzés; néha multihash, multidict vagy multidictionary is) egy asszociatív tömb absztrakt adattípusának általánosítása, amelyben egy adott kulcshoz rendelve egynél több érték társítható és adható vissza. általánosít egy asszociatív tömböt azáltal, hogy lehetővé teszi több érték társítását egyetlen kulcshoz.Michael T. Goodrich / Roberto Tamassia (2006), "9.1 The Map Abstract Data Type", Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371 A kétirányú leképezés egy kapcsolódó absztrakt adattípus, amelyben a leképezések mindkét irányban működnek (bijekció): minden értéket egyedi kulccsal kell társítani, a második keresési művelet pedig egy értéket vesz fel argumentumként, és megkeresi az értékhez társított kulcsot.
Tulajdonságok Az asszociatív tömb műveleteinek különféle tulajdonságokat kell kielégíteniük: lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D) lookup(k, new()) = fail, ahol a fail kivétel vagy alapértelmezett érték remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D)) remove(k, new()) = new() ahol k és j kulcsok, v egy érték, D egy asszociatív tömb, és a new() egy új, üres asszociatív tömböt hoz létre.
Példa Tegyük fel, hogy a könyvtár által kiadott kölcsönzések halmazát egy adatszerkezetben ábrázoljuk. A könyvtárban lévő minden könyvet egyszerre egy látogató vehet ki. Előfordulhat azonban, hogy egyetlen olvasó több könyvet is megnézhet. Ezért azt az információt, hogy mely könyvek melyik mecénásaihoz nézik ki, egy asszociatív tömb képviselheti, amelyben a könyvek a kulcsok, a kölcsönzők pedig az értékek. Python vagy JSON jelölésekkel az adatstruktúra a következő lenne:
{ "Büszkeség és balítélet": "Alice", "Üvöltő szelek": "Alice", "Szép remények": "John" }
A "Szép remények" kulcsra vonatkozó keresési művelet a "John"-t adja vissza. Ha John visszaadja a könyvét, az törlési műveletet okoz, és ha Pat kivesz egy könyvet, az beszúrási műveletet vált ki, ami egy másik állapothoz vezet:
{ "Büszkeség és balítélet": "Alice", "A Karamazov testvérek": "Pat", "Üvöltő szelek": "Alice" }
Implementációk A nagyon kevés leképezést tartalmazó szótárak esetében érdemes lehet a szótárt egy asszociációs lista segítségével megvalósítani, amely a leképezések láncolt listája.A számítógépes programozásban és különösen a Lisp-ben az asszociációs lista egy láncolt lista, amelyben minden listaelem (vagy csomópont) tartalmaz egy kulcsot és egy értéket. Ezzel a megvalósítással az alapvető szótári műveletek végrehajtási ideje lineáris a leképezések teljes számában. Azonban könnyen kivitelezhető, és a futásidejének állandó tényezői csekélyek.
Egy másik nagyon egyszerű megvalósítási technika, amely akkor használható, ha a kulcsok szűk tartományra vannak korlátozva, a közvetlen címzés egy tömbbe: az adott k kulcs értéke az A[k] tömbcellában tárolódik, vagy ha nincs leképezés k-ra, akkor a cella egy speciális őrszem értéket tárol, amely a leképezés hiányát jelzi.A számítógépes programozásban az őrszem érték (más néven flag value, trip value, rogue value, signal value, vagy dummy data) egy speciális érték egy olyan algoritmus kontextusában, amely a jelenlétét a befejezés feltételeként használja, általában ciklusban vagy rekurzív algoritmusban. Ez a technika egyszerű és gyors, minden szótári művelet állandó időt vesz igénybe. Ennek a szerkezetnek a helyigénye azonban a teljes kulcstér mérete, ezért nem praktikus, hacsak nem kicsi a kulcstér.
A szótárak megvalósításának két fő megközelítése a hash-tábla vagy a keresési fa.
Hash-tábla megvalósítások
Az asszociatív tömb leggyakrabban használt általános célú megvalósítása a hash-tábla: egy hash-függvénnyel kombinált tömb, amely minden kulcsot a tömb külön "vödrébe" választ el. A hash tábla alapötlete az, hogy egy tömb elemének elérése az indexen keresztül egy egyszerű, állandó idejű művelet. Ezért egy hash-táblázat műveletének átlagos többlete csak a kulcs hash-jének kiszámítása, a tömbön belüli megfelelő gyűjtőrész elérésével kombinálva. Mint ilyenek, a hash táblák általában O(1) idő alatt teljesítenek, és általában felülmúlják az alternatív megvalósításokat.
A hash tábláknak képesnek kell lenniük az ütközések kezelésére: két különböző kulcs hash függvénye általi leképezése a tömb ugyanazon gyűjtőhelyére mutat, azaz amikor egy hash táblában két különálló adat ugyanazt a hash értéket osztja meg. Ennek a problémának a két legelterjedtebb megközelítése a külön láncolásKülön láncolás esetén a folyamat magában foglalja egy hivatkozási lista létrehozását kulcs-érték párral minden keresési tömb indexéhez. és a nyílt címzés.. Külön láncolás esetén a tömb nem magát az értéket tárolja, hanem egy másik tárolóra mutató mutatót tárol, általában egy asszociációs listát, amely a hash-nek megfelelő összes értéket tárolja. Ezzel szemben a nyílt címzés során, ha hash ütközést találunk, a tábla egy üres helyet keres egy tömbben, hogy determinisztikusan tárolja az értéket, általában a tömb következő közvetlen pozícióját tekintve.
A nyílt címzésnek alacsonyabb a gyorsítótár kihagyási aránya, mint a külön láncolásnál, amikor a tábla többnyire üres. Azonban, ahogy a táblázat megtelik több elemmel, a nyílt címzés teljesítménye exponenciálisan romlik. Ezenkívül a külön láncolás a legtöbb esetben kevesebb memóriát használ, kivéve, ha a bejegyzések nagyon kicsik (kevesebb, mint a mutató méretének négyszerese).
Fa megvalósítások Önkiegyensúlyozó bináris keresési fák Egy másik elterjedt megközelítés az asszociatív tömb megvalósítása önkiegyensúlyozó bináris keresőfávalAz önkiegyensúlyozó bináris keresési fa bármely csomópont-alapú bináris keresési fa, amely automatikusan alacsonyan tartja magasságát (a szintek maximális száma a gyökér alatt) tetszőleges elembeszúrások és -törlések esetén., például AVL fával vagy piros-fekete fával.Joel Adams and Larry Nyhoff: "Trees in STL". Quote: "The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of self-balancing binary search tree called a red–black tree."
A hash táblákhoz képest ezeknek a struktúráknak vannak erősségei és gyengeségei is. Az önkiegyensúlyozó bináris keresési fák legrosszabb teljesítménye lényegesen jobb, mint a hash tábláé, az O(log n) nagy O jelöléssel együtt. Ez ellentétben áll a hash táblákkal, amelyeknek a legrosszabb teljesítménye esetén az összes elem egyetlen gyűjtőcsoporton osztozik, ami O(n) időbeli bonyolultságot eredményez. Ezen túlmenően, mint minden bináris keresőfa, az önkiegyensúlyozó bináris keresőfák is rendben tartják az elemeiket. Így az elemeinek bejárása a legkisebbtől a legnagyobbig terjedő mintát követ, míg a hash tábla bejárása azt eredményezheti, hogy az elemek látszólag véletlenszerű sorrendben vannak. Mivel sorrendben vannak, a fa alapú térképek tartománylekérdezéseket is kielégíthetnek (minden értéket megtalálnak két határ között), míg a hashmap csak pontos értékeket találhat. A hash tábláknak azonban sokkal jobb az átlagos esetek időbeli összetettsége, mint az O(1) önkiegyensúlyozó bináris keresőfáinak, és a legrosszabb eset teljesítménye nagyon valószínűtlen, ha jó hasítófüggvényt használunk.