Tablica asocjacyjna - Polski Serwis Naukowy

Tablica asocjacyjna (tablica skojarzeniowa, mapa, słownik, ang. associative array, map, dictionary) – nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikalny klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza.

Formalnie typ tablicy asocjacyjnej odpowiada zbiorowi skończonych funkcji częściowych z typu klucza tablicy w typ wartości tablicy. Wiele złożonych danych jest naturalnie reprezentowanych przez tego typu tablice - np. drzewa plików, nagłówki poczty, nawet wszystkie atrybuty obiektu czy przestrzeń nazw zmiennych.

Drzewo AVL, nazywane również drzewem dopuszczalnym, to zrównoważone binarne drzewo poszukiwań (BST), w którym wysokość lewego i prawego poddrzewa każdego węzła różni się co najwyżej o jeden. Nazwa AVL pochodzi od nazwisk rosyjskich matematyków: Adelsona-Velskii oraz Landisa (właściwie: Gieorgij Adelson-Wielskij i Jewgienij Ładnis), którzy zaproponowali rozwiązanie problemu utrzymania dobrego drzewa wyszukiwań w roku 1962 .

Tablica w informatyce to kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy, które najczęściej przyjmują wartości numeryczne. Rozmiar tablicy jest albo ustalony z góry (tablice statyczne), albo może się zmieniać w trakcie wykonywania programu (tablice dynamiczne).

Tablice asocjacyjne realizowane są jako drzewa poszukiwań (BST, AVL, trie itp.) lub tablice mieszające. Typ danych klucza może być praktycznie dowolny. Najczęściej są to łańcuchy znaków (napisy), ale także liczby (całkowite, zmiennoprzecinkowe, zespolone), krotki itp.

Cechy tablic asocjacyjnych

Najczęściej próba przypisania wartości do nieistniejącego klucza powoduje automatyczne utworzenie klucza i wówczas następuje zwykłe przypisanie.

Drzewo trie (wym. traj; od ang. retrieval, czyli odczyt) — drzewo poszukiwań przechowujące w węzłach fragmenty kluczy ("zwykłe" drzewa poszukiwań - np. BST, AVL - przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży.

W informatyce tablica mieszająca lub tablica haszująca to jeden ze sposobów realizacji tablicy asocjacyjnej, tj. struktury danych służącej do przechowywania informacji, w taki sposób aby możliwy był do nich szybki dostęp.

Na ogół przypisanie nowej wartości do istniejącego klucza zastępuje poprzednią wartość, ale np. w języku Ocaml z kluczami powiązane są listy wartości i przypisanie wartości do klucza powoduje tak naprawdę dopisanie jej na początek listy.

Sięgnięcie do nieistniejącego klucza zwykle kończy się błędem, ale np. w języku AWK zwracany jest pusty łańcuch znaków.

Istniejące implementacje tablic asocjacyjnych, bądź to dostępne bezpośrednio w danym języku programowania, bądź jako oddzielna biblioteka programistyczna na ogół oferują większą funkcjonalność niż tylko przypisanie wartości do klucza i pobranie wartości. Może to być:

JavaScript (JS) – obiektowy skryptowy język programowania, stworzony przez firmę Netscape, najczęściej stosowany na stronach internetowych. Pod koniec lat 90. XX wieku organizacja ECMA wydała na podstawie JavaScriptu standard języka skryptowego o nazwie ECMAScript. Głównym autorem JavaScriptu jest Brendan Eich.

Binarne drzewo poszukiwań (skrót BST, z ang. Binary Search Tree) – dynamiczna struktura danych w postaci drzewa binarnego stosowana do szybkiego wyszukiwania. Drzewa BST służą do realizacji bardziej abstrakcyjnych struktur danych, np. zbiorów, czy słowników.

usunięcie pary (klucz, wartość);

stwierdzenie, czy dany klucz znajduje się w tablicy (bez pobierania wartości);

pobranie listy wszystkich kluczy lub przynajmniej możliwość iterowania po niej;

pobranie listy wszystkich wartości;

pobranie listy wszystkich par (klucz, wartość).

Tablice asocjacyjne w różnych językach programowania

AWK

W języku AWK tablica asocjacyjna nazywana jest tablicą (array). Kluczem może być pojedyncze wyrażenie (zamieniane zawsze na łańcuch znaków), albo lista wyrażeń, które są sklejane razem, a ciąg je separujący jest określony przez zmienną SUBSEP.

OCaml (Objective Caml) to obiektowy funkcyjny język programowania, który istnieje w wersji zarówno interpretowanej jak i kompilowanej, przy czym kompilowany Ocaml to jeden z najszybszych języków funkcyjnych. OCaml jest tworzony przede wszystkim we francuskim akademickim instytucie badawczym INRIA od 1985 roku. Jest dostępny na licencji LGPL.

Krotka (ang. tuple) - struktura danych będąca odzwierciedleniem matematycznej n-tki, tj. uporządkowanego ciągu wartości. Krotki przechowują stałe wartości o różnych typach danych - nie można zmodyfikować żadnego elementu, odczyt natomiast wymaga podania indeksu liczbowego żądanego elementu.

tablica["Wikipedia"] = "Wolna encyklopedia";
tablica[10, 12, 2006] = "środa";
tablica[255] = 0xff;
if ("Wikipedia" in tablica)
        print tablica["Wikipedia"];

C++

W standardowej bibliotece języka C++ istnieje szablon map, który przyjmuje jako parametry dwa typy danych: typ klucza i typ wartości.

Python – interpretowany, interaktywny język programowania stworzony przez Guido van Rossuma w 1990. Python posiada w pełni dynamiczny system typów i automatyczne zarządzanie pamięcią, jest zatem podobny do takich języków, jak Tcl, Perl, Scheme czy Ruby.

Standard Template Library, STL (ang. standardowa biblioteka szablonów) – biblioteka C++ zawierająca algorytmy, pojemniki, iteratory oraz inne konstrukcje w formie szablonów, gotowe do użycia w programach.

using namespace std;
map<string, int> liczba_dni; // klucze typu string, wartości typu int
 
liczba_dni["styczeń"] = 31; // wstawienie pary klucz, wartość
liczba_dni["luty"]    = 28;
liczba_dni["marzec"]  = 31;
 
if (rok_przestępny)
   liczba_dni["luty"] = 29; // zmiana wartości związanej z kluczem "luty"
 
// wyszukanie wartości klucza metodą 'find'
if (liczba_dni.find("marzec") == liczba_dni.end())
    cout << "klucz 'marzec' nie występuje w tablicy";
else
    cout << "liczba dni w marcu = " << liczba_dni["marzec"];

PHP

$tablica = array("klucz" => "wartosc", 
                 "nowy_klucz" => 2);
// lub też:
$tablica["klucz"] = "wartosc";
$tablica["nowy_klucz"] = 2;

Perl

$tablica_asocjacyjna{"nazwa_elementu"}
%kolejna_tablica_asocjacyjna = (apple  => "red", banana => "yellow", );

JavaScript

tab_asoc["klucz"]="wartosc";

Python

W języku Python tablice są nazywane słownikami (dictionary, dict). Kluczem może być dowolny obiekt, która posiada metodę __hash__. Jeśli chodzi o typy wbudowane, jako klucze mogą służyć liczby całkowite, zmiennoprzecinkowe, zespolone, łańcuchy znaków (zwykłe i unikodowe), niemodyfikowalne zbiory (immutable sets), krotki, a nawet funkcje. Natomiast listy, modyfikowalne zbiory ani słowniki nie mogą być kluczami.

tablica = {"Wikipedia": "Wolna encyklopedia",
           (10, 12, 2006): "środa",
           255: 0xff}
 
# wypisanie wszystkich kluczy z tablicy
for klucz in tablica:
        print klucz
 
# wypisanie wszystkich wartości z tablicy
for wartosc in tablica.itervalues():
        print wartosc
 
# wypisanie jakie wartości są przypisane do jakich kluczy
for klucz, wartosc in tablica.iteritems():
        print klucz, '=>', wartosc
 
# wyświetlenie wartości związanej z kluczem (łańcuchem) "Wikipedia"
if "Wikipedia" in tablica:
        print tablica["Wikipedia"]
 
print tablica.get("Wikipedia", "brak klucza 'Wikipedia'")

Zobacz też

tablica