Asszociatív tömb

Az asszociatív tömb  egy absztrakt adattípus ( interfész az adattárhoz), amely lehetővé teszi a "(kulcs, érték)" formátumú párok tárolását, és támogatja a pár hozzáadásának, valamint a pár keresésének és törlésének műveleteit kulcs:

• INSERT(kulcs, érték)
• KERESÉS(kulcs)
• ELTÁVOLÍTÁS (kulcs)

Feltételezzük, hogy egy asszociatív tömb nem tud két párt tárolni azonos kulcsokkal.

Egy párban az értéket a kulcshoz tartozó értéknek nevezzük . Ahol kulcs ,  a érték .  _ A fenti műveletek szemantikája és neve eltérhet a különböző asszociatív tömb-megvalósításokban.

A FIND(kulcs) művelet az adott kulcshoz tartozó értéket adja vissza, vagy valamilyen speciális UNDEF objektumot, jelezve, hogy az adott kulcshoz nincs érték társítva. A másik két művelet nem ad vissza semmit (kivéve talán azt, hogy a művelet sikeres volt-e vagy sem).

Az interfész szempontjából kényelmes egy asszociatív tömböt szabályos tömbnek tekinteni , amelyben nemcsak egész számok, hanem más típusú értékek, például karakterláncok is használhatók indexként.

Az asszociatív tömbök támogatása számos magas szintű értelmezett programozási nyelvben megtalálható , mint például a Perl , PHP , Python , Ruby , Tcl , JavaScript [1] és mások. Azoknál a nyelveknél, amelyek nem rendelkeznek beépített asszociatív tömbökkel, számos megvalósítás létezik könyvtárak formájában .

Az asszociatív tömbre példa a telefonkönyv: ebben az esetben az érték a „ Teljes név + cím” kombinációja, a kulcs pedig a telefonszám, egy telefonszámnak egy tulajdonosa van, de egy személynek több telefonszáma is lehet. .

A három fő műveletet gyakran kiegészítik másokkal, a legnépszerűbb kiterjesztések a következők:

• CLEAR  - minden bejegyzés törlése
• EACH  - "futtassa" az összes tárolt páron,
• MIN  - keresse meg a párt a minimális kulcsértékkel,
• MAX  – keresse meg a maximális kulcsértékkel rendelkező párt.

Az utolsó két esetben szükséges, hogy az összehasonlítási műveletet a billentyűkön definiáljuk.

Asszociatív tömb megvalósítások

Az asszociatív tömbnek számos különféle megvalósítása létezik.

A legegyszerűbb megvalósítás alapja lehet egy szabályos tömb, amelynek elemei (kulcs, érték) párok. A keresési művelet felgyorsítása érdekében a tömb elemeit kulcs szerint rendezheti, és bináris keresési módszert hajthat végre . Ez azonban megnöveli az új pár hozzáadásának műveletének végrehajtási idejét, mivel a tömb elemeit „szét kell tolni”, hogy új bejegyzést helyezzenek el a kapott üres cellában.

A legnépszerűbb megvalósítások különféle keresési fákon alapulnak . Így például a C++ nyelv szabványos STL könyvtárában a térképtároló egy piros-fekete fa alapján van megvalósítva . A D , Java , Ruby , Tcl , Python nyelvek a hash tábla egyik változatát használják . Vannak más megvalósítások is.

Minden megvalósításnak megvannak a maga előnyei és hátrányai. Fontos, hogy mindhárom műveletet átlagosan és legrosszabb esetben időben is végrehajtsák , hol  van a tárolt párok aktuális száma. A kiegyensúlyozott keresési fákra (beleértve a vörös-fekete fákat is) ez a feltétel teljesül.

A hash táblákon alapuló megvalósításokban az átlagos idő becslése , ami jobb, mint a keresési fák alapú megvalósításokban. Ez azonban nem garantálja egyetlen művelet gyors végrehajtását: az INSERT művelet idejét a legrosszabb esetben becsülik . Az INSERT művelet hosszú ideig tart, amikor a kitöltési tényező magas lesz, és a hash tábla indexét újra kell építeni.

A hash táblák azért is rosszak, mert nem használhatók gyors további MIN, MAX műveletek végrehajtására, valamint egy algoritmus az összes tárolt pár megkerülésére a kulcsok növekvő vagy csökkenő sorrendjében.

Jegyzetek

1. ↑ JavaScriptben az objektumok támogatják a tulajdonságok tetszőleges (karakterlánc) kulccsal történő létrehozását, így egy asszociatív tömb alapvető tulajdonságait is megvalósítják. Lásd: Objektumok asszociatív tömbökként . JavaScript oktatóanyag . Hozzáférés dátuma: 2012. december 20. Az eredetiből archiválva : 2012. december 23. (határozatlan)

Linkek

• A NIST algoritmusok és adatstruktúrák szótára: Associative Array
• A NIST algoritmusok és adatstruktúrák szótára: asszociációs lista