Asszociatív tömb

Az informatikában az asszociatív tömb, (associative array, map, symbol table, vagy dictionary) egy absztrakt adattípus(wd)^[1], amely (kulcs, érték) párok(wd) gyűjteményét(wd)^[2] 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ú(wd) függvény.^[3] Támogatja a „keresés”, „eltávolítás” és „beszúrás” műveleteket.

A szótári probléma^[4] az asszociatív tömböket megvalósító hatékony adatszerkezetek tervezésének klasszikus problémája.^[5] A szótári probléma két fő megoldása a hash-tábla és a keresőfa(wd)^[6].^{[7][8][9][10]} A probléma néha közvetlenül címzett tömbök, bináris keresőfák(wd) 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ória(wd)^[11] 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ás(wd)^[12] és a dekorációs minta.^[13]

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(wd) 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:^[7][8][14]

Insert vagy put

hozzáad egy új ${\displaystyle (key,value)}$ párt a gyűjteményhez(wd), leképezve a kulcsot az új értékére.^[15] 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 ${\displaystyle (key,value)}$ 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(wd) létrehozását, amely az összes leképezést áthurkolja.^[16] Az ilyen műveleteknél a leképezések visszaadási sorrendjét általában implementáció határozza meg.

A többleképezés(wd)^[17] á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.^[18] A kétirányú leképezés(wd) egy kapcsolódó absztrakt adattípus, amelyben a leképezések(wd) 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:^[14]

• 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(wd) segítségével megvalósítani, amely a leképezések láncolt listája.^[19] 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.^[7][20]

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(wd) tárol, amely a leképezés hiányát jelzi.^[21] 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.^[9]

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(wd).^{[7][8][9][10]}

Hash-tábla megvalósítások

Ez a grafikon összehasonlítja a CPU gyorsítótár(wd)-kihagyások átlagos számát, amely a nagy hash-táblázatok elemeinek megkereséséhez szükséges (a gyorsítótár méretét jóval meghaladja) a láncolással és a lineáris vizsgálattal.^[22] A lineáris szondázás(wd) jobban teljesít a jobb referencia lokalitás(wd) miatt^[23], bár a táblázat megteltével a teljesítménye drasztikusan csökken.

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(wd) 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ás^[24] és a nyílt címzés(wd).^{[7][8][9][25]} 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(wd), 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ával(wd)^[26], például AVL fával vagy piros-fekete fával.^[27]

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.

Egy önkiegyensúlyozó bináris keresőfa használható a külön láncolást használó hash tábla gyűjtősávjainak megvalósítására. Ez lehetővé teszi az átlagos esetszámú állandó keresést, de biztosítja a legrosszabb O(log n) teljesítményt. Ez azonban extra bonyolultságot jelent a megvalósításban, és még rosszabb teljesítményt eredményezhet a kisebb hash tábláknál, ahol a fába való beillesztéssel és a kiegyensúlyozással eltöltött idő nagyobb, mint a csatolt lista vagy hasonló adatstruktúra összes elemére vonatkozó lineáris keresés végrehajtásához szükséges idő.^[28][29]

Egyéb fák

Az asszociatív tömbök kiegyensúlyozatlan bináris keresési fákban vagy egy bizonyos típusú kulcsokra specializálódott adatstruktúrákban is tárolhatók, például radix fák(wd)^[30], trie(wd)^[31], Judy tömbök(wd)^[32] vagy van Emde Boas fák(wd)^[33], bár ezeknek a megvalósításoknak a relatív teljesítménye változó. Például a Judy-fák kevésbé hatékonyan teljesítenek, mint a hash-táblák, míg a gondosan kiválasztott hash-táblák általában hatékonyabban teljesítenek, mint az adaptív radix fák, és potenciálisan nagyobb korlátozásokkal rendelkeznek a kezelhető adattípusokra vonatkozóan.^[34] Ezen alternatív struktúrák előnyei abból fakadnak, hogy képesek további asszociatív tömbműveleteket kezelni, például megtalálni azt a leképezést, amelynek kulcsa a legközelebb van a lekérdezett kulcshoz, ha a lekérdezés hiányzik a leképezések halmazából.

Összehasonlítás

Mögöttes adatstruktúra	Keresés vagy eltávolítás		Beszúrás		Rendelve
	átlagos	legrosszabb eset	átlagos	legrosszabb eset
Hash-tábla	O(1)	O(n)	O(1)	O(n)	Nem
Önkiegyensúlyozó bináris keresőfa(wd)	O(log n)	O(log n)	O(log n)	O(log n)	Igen
Kiegyensúlyozatlan bináris keresőfa(wd)	O(log n)	O(n)	O(log n)	O(n)	Igen
Kulcs-érték párok(wd) szekvenciális tárolása (e.g. association list(wd))	O(n)	O(n)	O(1)	O(1)	Nem

Rendezett szótár

A szótár alapdefiníciója nem ír elő rendezést. A felsorolás rögzített sorrendjének garantálására gyakran használják az asszociatív tömb rendezett változatait. A rendezett szótárnak két értelme van:

• A felsorolás sorrendje rendezés útján mindig determinisztikus egy adott kulcskészletre. Ez a helyzet a fa alapú megvalósításoknál, amelyek egyik képviselője a C++ <map> tárolója.^[35]
• A felsorolás sorrendje kulcsfüggetlen, és ehelyett a beillesztés sorrendjén alapul. Ez a helyzet a .NET keretrendszer „rendezett szótárával”, a Java és a Python LinkedHashMap-jával.^[36][37][38]

Ez utóbbi gyakoribb. Az ilyen rendezett szótárakat asszociációs lista(wd) segítségével, egy duplán láncolt lista(wd) átfedésével egy normál szótár tetejére lehet megvalósítani, vagy a tényleges adatokat a ritka (rendezetlen) tömbből egy sűrű beillesztési sorrendbe helyezzük át.

Nyelvi támogatás

Az asszociatív tömbök bármilyen programozási nyelven megvalósíthatók csomagként, és számos nyelvi rendszer a szabványos könyvtár részeként biztosítja őket. Egyes nyelveken nem csak a szabványos rendszerbe vannak beépítve, hanem speciális szintaxissal is rendelkeznek, gyakran tömb-szerű feliratkozást használva.

Az asszociatív tömbök beépített szintaktikai támogatását 1969-ben a SNOBOL4(wd) vezette be "table" néven. A TMG(wd) táblázatokat kínált karakterlánc-kulcsokkal és egész értékekkel. A MUMPS(wd) többdimenziós asszociatív tömböket készített, amelyek opcionálisan perzisztensek, kulcsfontosságú adatstruktúrája. A SETL(wd) a készletek és térképek egyik lehetséges megvalósításaként támogatta őket. A legtöbb modern szkriptnyelv, az AWK-tól kezdve, beleértve a Rexxet, Perl-t, PHP-t, Tcl-t(wd), JavaScriptet, Maple-t, Python-t, Ruby-t, Wolfram Language-t(wd), Go-t és Lua-t, támogatja az asszociatív tömböket elsődleges tárolótípusként. Sokkal több nyelven érhetők el könyvtári függvényként, speciális szintaxis nélkül.

A Smalltalk, Objective-C, .NET,^[39] Python, REALbasic(wd), Swift, VBA és Delphi^[40] ezeket szótárnak nevezik; a Perlben, Rubyban és Seed7ben hash-nek nevezik; a C++, C#, Java, Go, Clojure(wd), Scala(wd), OCaml(wd), Haskell nyelvekben maps-nek nevezik (lásd map (C++)(wd), unordered_map (C++)(wd) és Map); a Common Lisp-ben és a Windows PowerShell-ben ezeket hash tables-nak nevezik (mivel mindkettő általában ezt a megvalósítást használja); a Maple-ben és Lua-ban tables-nak hívják. PHP-ben és R-ben minden tömb lehet asszociatív, kivéve, hogy a kulcsok egész számokra és karakterláncokra korlátozódnak. A JavaScriptben (lásd még JSON) minden objektum asszociatív tömbként viselkedik karakterlánc-értékű kulcsokkal, míg a Map és WeakMap típusok tetszőleges objektumokat vesznek fel kulcsként. A Lua-ban minden adatstruktúra primitív építőelemeként használja őket. A Visual FoxPro-ban(wd) ezeket Collections-nek hívják. A D nyelv is támogatja az asszociatív tömböket.^[41]

Állandó tárhely

Számos asszociatív tömböt használó programnak tartósabb formában kell tárolnia ezeket az adatokat, például számítógépes fájlban. A probléma általános megoldása az archiválásnak vagy szerializálásnak(wd) nevezett általános koncepció, amely az eredeti objektumok szöveges vagy bináris reprezentációját hozza létre, amely közvetlenül egy fájlba írható.^[42] Ezt leggyakrabban az alapul szolgáló objektummodellben valósítják meg, mint például a .Net(wd) vagy a Cocoa(wd), amely szabványos függvényeket tartalmaz, amelyek a belső adatokat szöveggé alakítják. A program bármely objektumcsoport teljes szöveges reprezentációját képes létrehozni ezen metódusok meghívásával, amelyek szinte mindig már az alap asszociatív tömbosztályban implementáltak.^[43]

A nagyon nagy adatkészleteket használó programok esetében ez a fajta egyedi fájltárolás nem megfelelő, és adatbázis-kezelő rendszerre (DB) van szükség. Egyes adatbázis-rendszerek natív módon asszociatív tömböket tárolnak az adatok sorba rendezésével, majd a rendezett adatok és a kulcs tárolásával. Az egyes tömbök ezután betölthetők vagy elmenthetők az adatbázisból a rájuk hivatkozó kulccsal. Ezeket a kulcsérték-tárolókat sok éve használják, és olyan hosszú múltra tekintenek vissza, mint a gyakoribb relációs adatbázisoké (RDB), de a szabványosítás hiánya, többek között, bizonyos fülke-szerepekre^[44] korlátozta a használatát. A legtöbb esetben RDB-ket használtak ezekhez a szerepekhez, bár az objektumok RDB-be mentése bonyolult lehet, ez a probléma objektum-relációs impedancia eltérésként(wd) ismert.

Körülbelül 2010 után a nagy teljesítményű, felhőalapú számítástechnikára alkalmas és az azokat használó programok belső struktúrájához jobban illeszkedő adatbázisok iránti igény reneszánszát idézte elő a kulcs-érték alapú kínálat piacán. Ezek a rendszerek natív módon képesek asszociatív tömböket tárolni és lekérni, ami nagymértékben javíthatja a teljesítményt az általános webhez kapcsolódó munkafolyamatokban.

Lásd még

• Rendezett n-es
• Függvény (matematika)
• Keresőtábla

Jegyzetek

1. Az 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(wd)) 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.
2. A számítógépes programozásban a collection egy absztrakt adattípus(wd), amely az elemek polimorf módon használható csoportosítása.
3. A theory of finite maps, Higher Order Logic Theorem Proving and Its Applications, Lecture Notes in Computer Science, 122–137. o.. DOI: 10.1007/3-540-60275-5_61 (1995. január 5.). ISBN 978-3-540-60275-0 
4. Az 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).
5. Andersson, Arne. Optimal Bounds on the Dictionary Problem, Proc. Symposium on Optimal Algorithms, Lecture Notes in Computer Science. Springer Verlag, 106–114. o.. DOI: 10.1007/3-540-51859-2_10 (1989. január 5.). ISBN 978-3-540-51859-4 
6. A keresési fa egy fa adatstruktúra, amely meghatározott kulcsok megtalálására szolgál egy halmazon belül.
7. Goodrich, Michael T. & Tamassia, Roberto (2006), "9.1 The Map Abstract Data Type", Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371
8. Mehlhorn, Kurt & Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox, Springer, pp. 81–98, <http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf>
9. Cormen, Thomas H.; Leiserson, Charles E. & Rivest, Ronald L. et al. (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.
10. 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" Archiválva 2016. március 4-i dátummal a Wayback Machine-ben.. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094
11. A 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.
12. A 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.
13. (Goodrich & Tamassia 2006), pp. 597–599.
14. dictionary. Dictionary of Algorithms and Data Structures , 2020. november 2. (Hozzáférés: 2022. január 26.)
15. A számítógépes programozásban a gyűjtemény egy absztrakt adattípus(wd), amely az elemek polimorf módon használható csoportosítása.
16. 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(wd) minden egyes eleméhez, sorrendben.
17. Az 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(wd) általánosítása, amelyben egy adott kulcshoz rendelve egynél több érték társítható és adható vissza.
18. Michael T. Goodrich(wd) / Roberto Tamassia(wd) (2006), "9.1 The Map Abstract Data Type", Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371
19. 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(wd)) tartalmaz egy kulcsot és egy értéket.
20. When should I use a hash table instead of an association list?. lisp-faq/part2, 1996. február 20.
21. 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(wd) egy olyan algoritmus kontextusában, amely a jelenlétét a befejezés feltételeként(wd) használja, általában ciklusban vagy rekurzív algoritmusban.
22. A lineáris szondázás egy olyan séma a számítógépes programozásban, amely a hash táblákban, az adatstruktúrákban a kulcs-érték párok(wd) gyűjteményének karbantartására és az adott kulcshoz tartozó érték megkeresésére szolgáló ütközések(wd) feloldására szolgál.
23. A számítástechnikában a referencia lokalitása, más néven lokalitás elve, a processzor azon tendenciája, hogy rövid időn keresztül ismétlődően hozzáférjen ugyanahhoz a memóriahely-készlethez.
24. Kü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.
25. Klammer, F. & Mazzolini, L. (2006), "Pathfinders for associative maps", Ext. Abstracts GIS-l 2006, GIS-I, pp. 71–74.
26. Az önkiegyensúlyozó bináris keresési fa bármely csomópont-alapú(wd) bináris keresési fa(wd), 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.
27. 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."
28. Knuth, Donald. The Art of Computer Programming, 2nd, Addison-Wesley, 513–558. o. (1998). ISBN 0-201-89685-0 
29. Probst, Mark: Linear vs Binary Search, 2010. április 30. (Hozzáférés: 2016. november 20.)
30. A radix fa (más néven compact prefix tree vagy compressed trie) egy olyan adatstruktúra, amely egy méretre optimalizált trie-t(wd) (előtagfát) képvisel, amelyben minden egyes csomópont, amely az egyetlen gyermek, összevonódik a szülőjével.
31. Az informatikában a trie, amelyet digitális fának vagy prefix-fának is neveznek, a keresőfa egy fajtája: konkrétan egy k-áris fa(wd) adatstruktúra, amelyet egy készlet bizonyos kulcsainak belülről történő megtalálására használnak.
32. A Judy-tömb egyfajta asszociatív tömböt valósít meg nagy teljesítménnyel és alacsony memóriahasználattal.A legtöbb más kulcs-érték tárolótól eltérően a Judy tömbök nem használnak kivonatolást, a kulcsaikon (amelyek lehetnek egész számok vagy karakterláncok) tömörítést alkalmaznak, és hatékonyan képesek megjeleníteni a ritka adatokat; vagyis nagy tartományban lehetnek hozzá nem rendelt indexeik anélkül, hogy jelentősen megnövelnék a memóriahasználatot vagy a feldolgozási időt.
33. A van Emde Boas fa (más néven vEB tree vagy van Emde Boas priority queue) egy fa adatstruktúra, amely asszociatív tömböt valósít meg m bites egész kulcsokkal. Peter van Emde Boas(wd) holland informatikus vezette csapat találta fel 1975-ben.
34. A comparison of adaptive radix trees and hash tables, 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea: IEEE, 1227–1238. o.. DOI: 10.1109/ICDE.2015.7113370 (2015. április 1.). ISBN 978-1-4799-7964-6 
35. std::map. en.cppreference.com
36. OrderedDictionary Class (System.Collections.Specialized) (amerikai angol nyelven). MS Docs
37. LinkedHashMap
38. collections — Container datatypes — Python 3.9.0a3 documentation. docs.python.org
39. Dictionary<TKey, TValue> Class. MSDN
40. System.Generics.Collections.TDictionary - RAD Studio API Documentation (angol nyelven). docwiki.embarcadero.com . (Hozzáférés: 2017. április 18.)
41. Associative Arrays, the D programming language. Digital Mars
42. A számítástechnikában a szerializálás (amely a Pythonban pickling(wd) néven ismert) az a folyamat, amikor egy adatszerkezetet vagy objektum állapotát tárolható formátumba fordítanak (pl. fájlok másodlagos tárolóeszközökön, adatpufferek az elsődleges tárolóeszközökön), ill. továbbítják (pl. adatfolyamok(wd) számítógép-hálózatokon keresztül) és később rekonstruálják (esetleg más számítógépes környezetben).
43. "Archives and Serializations Programming Guide", Apple Inc., 2012
44. A niche roles, fülke-szerepek erősen specializálódott szakmák, amelyek rendelkeznek a komplex problémák megoldásához szükséges készségekkel, tapasztalattal és képesítéssel.

Fordítás

• Ez a szócikk részben vagy egészben az Associative array című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.