Tablica asocjacyjna

W informatyce An asocjacyjna (zwany również słowniku lub stół Association ) jest typu danych skupiających zestaw kluczy z odpowiedniego zbioru wartości . Każdy klucz jest powiązany z jedną wartością (co najwyżej): tablica asocjacyjna odpowiada zatem zastosowaniu w matematyce skończonej dziedziny.

Z punktu widzenia programisty tablicę asocjacyjną można postrzegać jako uogólnienie tablicy  : podczas gdy tradycyjna tablica wiąże kolejne liczby całkowite z wartościami, tablica asocjacyjna wiąże klucze jednego dowolnego typu z wartościami innego typu.

Operacje zwykle wykonywane przez tablicę asocjacyjną to:

Tablice asocjacyjne są powszechnie stosowane w informatyce, na przykład w systemach plików , zarządzać tablicę symboli z kompilatorów podczas analizy leksykalnej, aby uzyskać dostęp do pamięci wirtualnej , lub do rozsyłania pakietów w routerze .

Przykłady

Możesz myśleć o książce telefonicznej jako o tablicy asocjacyjnej, w której nazwy są kluczami, a numery telefonów są wartościami. Innym przykładem jest słownik (w tradycyjnym sensie), w którym słowa są kluczami, a definicje wartościami. Tabela bazy danych jest również tablicą asocjacyjną, w której wartości są pełnymi rekordami (wierszami). Cała baza danych może być postrzegana jako zbiór asocjacyjnych związani ograniczeniami Edgar Codd w przepisach .

Struktury danych dla tablic asocjacyjnych

Tablice asocjacyjne są najczęściej używane, gdy operacja wyszukiwania jest najczęstsza. Z tego powodu projekt najczęściej faworyzuje tę operację, ze szkodą dla wydajności dodawania i zajętości pamięci w porównaniu z innymi strukturami danych (takimi jak listy skojarzeń). W routerach, aby uzyskać dostęp do pamięci wirtualnej, lub bardziej ogólnie, gdy czas dostępu jest bardzo ograniczony, tablica asocjacyjna może być zaimplementowana na poziomie sprzętowym (patrz pamięć adresowana przez zawartość ).

W dalszej części n oznacza liczbę elementów tablicy asocjacyjnej.

Skuteczne reprezentacje

Istnieją dwie struktury danych, które skutecznie reprezentują tablice asocjacyjne: tabela skrótów i zrównoważone drzewo . Odpowiednie zalety i wady tych dwóch rozwiązań są następujące:

Listy stowarzyszeń

Nieefektywnie (ale prostsze) wykonanie tablicy asocjacyjnej (wprowadzonej w Lisp w 1957) jest listą asocjacyjną , połączoną listą par klucz-wartość. Wyszukiwanie polega następnie na przeglądaniu listy sekwencyjnie, aż do znalezienia danego klucza; dlatego ma złożoność O ( n ). Lista skojarzeń ma następujące zalety:

Wyspecjalizowane przedstawicielstwa

Jeśli klucze są określonego typu, czasami można uzyskać lepszą wydajność przy użyciu wyspecjalizowanej struktury danych. Na przykład możliwe jest użycie drzewa Patricia, jeśli klucze są liczbami całkowitymi (gdy klucze są zbyt rzadkie, aby można było użyć tradycyjnej tablicy). Mówiąc bardziej ogólnie, sortowanie może być użyte, gdy tylko klucze będą miały strukturę słów. Unika się wtedy wielu porównań, gdy kilka kluczy ma wspólne przedrostki, co ma miejsce na przykład w tablicach routingu .

Obsługiwane w językach programowania

C ++

Kod źródłowy C ++ z wykorzystaniem tablicy asocjacyjnej przy użyciu klasy mapz biblioteki standardowej  :

#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; }

Powyższa tablica asocjacyjna jest również nazywana słownikiem, w szczególności dlatego, że umożliwia szybkie wyszukiwanie bez przechodzenia przez całą tablicę.

OCaml

Język OCaml udostępnia trzy rodzaje tablic asocjacyjnych w swojej bibliotece standardowej . Najprostsza to lista par:

# 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"

Drugi to polimorficzna tablica mieszająca :

# 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"

Wreszcie ostatni jest słownikiem czysto aplikacyjnym (produkowanym przez drzewa AVL ):

# 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"

Listy par i słowniki są trwałymi strukturami danych, ponieważ są czysto funkcjonalne . Wręcz przeciwnie , tabele skrótów są koniecznymi strukturami danych , bardziej wydajnymi niż listy i ogólnie AVL .

JavaScript

W JavaScript tablice asocjacyjne nazywane są obiektami, a nazwa klasy bazowej 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`) })

Zauważ, że to z tej notacji obiektu javascript pochodzi standardowy format wymiany danych JavaScript Object Notation , w skrócie JSON .

PHP i Perl

Kod źródłowy PHP wykorzystujący tablicę asocjacyjną:

$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }

Ten sam kod w Perlu  :

%dico = ( lundi => 'dodo', mardi => 'dodo', mercredi => 'resto' ); print "$dico{lundi}\n"; foreach $key (sort keys %dico) { print "Le $key c'est $dico{$key}.\n"; }


Wyjście ekranu w obu przypadkach:

dodo Le lundi c'est dodo Le mardi c'est dodo Le mercredi c'est resto

Pyton

Kod źródłowy Pythona tworzący i wyświetlający zawartość tablicy asocjacyjnej, powszechnie znanej jako słownik:

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]))


Jak pokazuje przykład, słowniki mogą zawierać dowolny typ zmiennej lub obiektu. Ta cecha dotyczy również list lub krotek. Rezultatem będzie:

La tour Eiffel est à Paris La statue de la liberté est à New-York Le nombre de visiteurs de la tour Eiffel est 6930000

Bibliografia

  • (en) Mehlhorn Kurt i Peter Sanders , „  4 Hash Tables and Associative Arrays  ” , w artykule Algorithms and Data Structures: The Basic Toolbox , Springer,2008, s.  81-98