A számítástechnikában az asszociatív tömb (más néven szótár vagy asszociációs tábla ) egy olyan adattípus, amely a kulcsok halmazát a megfelelő értékkészlettel társítja . Minden kulcs van társítva egyetlen érték (maximum): egy asszociatív tömb tehát megfelel egy olyan véges tartomány alkalmazása a matematikában.
A programozó szempontjából az asszociatív tömb a tömb általánosításának tekinthető : míg a hagyományos tömb egymás után következő egész számokat társít értékekhez, addig az asszociatív tömb az egyik tetszőleges típusú kulcsot egy másik.
Az asszociatív tömb által biztosított műveletek általában a következők:
Az asszociatív tömböket általában használják az informatikában, például a fájlrendszerben a fordító szimbólumtáblájának kezelésére a lexikai elemzés során, a virtuális memória elérésére vagy a routerek csomagjainak továbbítására .
Úgy gondolhat, hogy a telefonkönyv asszociatív tömb, ahol a nevek kulcsok, a telefonszámok pedig értékek. Egy másik példa egy szótár (hagyományos értelemben), ahol a szavak a kulcsok, a meghatározások pedig az értékek. Az adatbázis tábla egyben asszociatív tömb, amelyben az értékek teljes rekordok (sorok). Egy teljes adatbázis asszociatív tömbök halmazának tekinthető, amelyeket Edgar Codd szabályainak korlátai kötnek meg .
Az asszociatív tömböket leggyakrabban akkor használják, amikor a keresési művelet a leggyakoribb. Emiatt a tervezés leggyakrabban ezt a műveletet részesíti előnyben, rontva az összeadás és a memóriafoglalás hatékonyságát más adatstruktúrákkal (például társítási listákkal) szemben. Az útválasztókban a virtuális memóriához való hozzáférés érdekében, vagy általánosabban, ha a hozzáférési idő nagyon korlátozott, asszociatív tömb valósítható meg hardver szinten (lásd tartalom szerint címezhető memória ).
A következőkben n kijelöli az asszociatív tömb elemeinek számát.
Két asszociációs struktúra hatékony az asszociatív tömbök ábrázolásában: a hash tábla és a kiegyensúlyozott fa . E két megoldás előnyei és hátrányai a következők:
Nem hatékony (de egyszerűbb) elvégzésére egy asszociatív tömb (bevezetett Lisp 1957) egy kapcsolat listát , láncolt lista a kulcs-érték párokat. A keresés ekkor abból áll, hogy a listát egymás után végigjárják, amíg egy adott kulcs megtalálható; ezért összetettsége O ( n ). Az egyesületi listának a következő előnyei vannak:
Ha a kulcsok egy bizonyos típusúak, akkor néha lehet jobb teljesítményt elérni egy speciális adatstruktúra használatával. Például lehetséges Patricia fát használni, ha a kulcsok egész számok (amikor a kulcsok túl ritkák egy hagyományos tömb használatához). Általánosságban elmondható, hogy a rendezés használható, amint a kulcsok szószerkezettel rendelkeznek. Számos összehasonlítást elkerülünk, ha több kulcsnak közös előtagja van, ez például az útválasztási tábláknál .
C ++ forráskód mapa standard könyvtár osztályát használó asszociatív tömb segítségével :
#include <map> #include <string> using namespace std; int main() { map <string, string> repertoire; repertoire["Jean Dupont"] = "01.02.03.04.05"; repertoire["François Martin"] = "02.03.04.05.06"; repertoire["Louis Durand"] = "03.04.05.06.07"; return 0; }A fenti asszociatív tömböt szótárnak is nevezik , különösen azért, mert gyors kereséseket tesz lehetővé anélkül, hogy végig kellene menned a teljes tömbön.
Az OCaml nyelv háromféle asszociatív tömböt biztosít a szokásos könyvtárában . A legegyszerűbb a párok listája:
# let m = ["Sally Smart", "555-9999"; "John Doe", "555-1212"; "J. Random Hacker", "553-1337"];; val m : (string * string) list = [("Sally Smart", "555-9999"); ("John Doe", "555-1212"); ("J. Random Hacker", "553-1337")] # List.assoc "John Doe" m;; - : string = "555-1212"A második egy polimorf hash táblázat :
# let m = Hashtbl.create 3;; val m : ('_a, '_b) Hashtbl.t = <abstr> # Hashtbl.add m "Sally Smart" "555-9999"; Hashtbl.add m "John Doe" "555-1212"; Hashtbl.add m "J. Random Hacker" "553-1337";; - : unit = () # Hashtbl.find m "John Doe";; - : string = "555-1212"Végül az utolsó egy tisztán alkalmazható szótár (amelyet az AVL fák készítettek ):
# include (Map.Make(String));; ... # let m = empty |> add "Sally Smart" "555-9999" |> add "John Doe" "555-1212" |> add "J. Random Hacker" "553-1337";; val m : string t = <abstr> # find "John Doe" m;; - : string = "555-1212"A párok és szótárak listája állandó adatszerkezet, mivel pusztán funkcionálisak . A hash-táblák éppen ellenkezőleg , kötelező adatstruktúrák , hatékonyabbak, mint a listák és általában az AVL-ek .
A JavaScriptben az asszociatív tömböket objektumoknak nevezzük, az alaposztály megnevezésével Object.
// définition de l'objet const agenda = { lundi: 'dodo', mardi: 'dodo', mercredi: 'resto' } // ajout dynamique de clés/valeurs agenda.jeudi = 'apero' // modification des clés/valeurs existante agenda.mardi = 'apero' delete agenda.lundi // Pour obtenir une liste des clés const jours = Object.keys(agenda) // Pour obtenir une liste des valeurs const activités = Object.values(agenda) // Plusieurs manières de faire une boucle sur ces valeurs for (const key in agenda) { const value = agenda[key] console.log(`${key} c'est ${value} : ça va être super bien`) } // ou bien Object.keys(agenda).forEach(key => { const value = agenda[key] console.log(`${key} c'est ${value} : ça va être super bien`) })Ne feledje, hogy ebből a javascript objektum jelölésből származik a szokásos JavaScript Object Notation adatcsere-formátum , rövidítve JSON .
PHP forráskód asszociatív tömb segítségével:
$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }Ugyanaz a kód a Perl-ben :
%dico = ( lundi => 'dodo', mardi => 'dodo', mercredi => 'resto' ); print "$dico{lundi}\n"; foreach $key (sort keys %dico) { print "Le $key c'est $dico{$key}.\n"; }
Képernyő kimenet mindkét esetben:
Python forráskód, asszociatív tömb tartalmának létrehozása és megjelenítése, közismertebb nevén szótár:
monuments = {"La tour Eiffel": "à Paris", "La statue de la liberté": "à New-York", "Le nombre de visiteurs de la tour Eiffel": 6930000 } for clef in monuments: print("{} est {}".format(clef, monuments[clef]))
Mint a példa mutatja, a szótárak bármilyen típusú változót vagy objektumot tartalmazhatnak. Ez a jellemző a listákra vagy a sorrendekre is érvényes. Az eredmény: