Tablica asocjacyjna

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 (unikatowy 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, a nawet wszystkie atrybuty obiektu czy przestrzeń nazw zmiennych.

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.
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 ona obejmować następujące operacje:

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.

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.

#include <iostream>
#include <map>
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;

//od PHP 5.4
$tablica = ["klucz" => "wartosc", "inny_klucz" => 1];

Perl

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

JavaScript

W języku JavaScript każdy obiekt jest tablicą asocjacyjną.

var tab_asoc = {};
tab_asoc["klucz"]="wartość";
//co jest równoważne
tab_asoc.klucz="wartość";

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.values():
 	print(wartosc)

# wypisanie jakie wartości są przypisane do jakich kluczy
for klucz, wartosc in tablica.items():
 	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'"))

Lua

tablica = {
    klucz = 'wartość',
    innyklucz = 'innawartosc'
}

-- w przypadku kiedy klucz ma więcej niż jeden wyraz lub jest liczbą
tablica = {
    ['klucz numer 1'] = 'wartosc',
    ['2'] = 'innawartosc'
}

-- lub inny zapis:

tablica = {}
tablica["klucz"] = "wartosc"
-- lub
tablica.klucz = 'wartosc'

Object Pascal

W bibliotece VCL środowiska Delphi istnieje klasa generyczna TDictionary, która przyjmuje dwa typy danych jako parametry: typ klucza i typ wartości. Poniższy kod kompiluje się od wersji Delphi XE3, ponieważ użyto w nim rekordów pomocników (record helpers).

program LiczbaDniRoku;

{$APPTYPE CONSOLE}

uses
  System.SysUtils, System.Generics.Collections, System.DateUtils;

var
  LiczbaDni: TDictionary<String, Integer>; // klucze typu String, wartości typu Integer

begin
  // utworzenie słownika
  LiczbaDni := TDictionary<String, Integer>.Create;
  LiczbaDni.Add('styczeń', 31); // wstawienie pary: klucz, wartość
  LiczbaDni.Add('luty', 28);
  LiczbaDni.Add('marzec', 31);
  // podaje liczbę kluczy przechowywaną w słowniku
  Writeln('liczba dodanych miesiecy: ', LiczbaDni.Keys.Count.ToString);
  // korekta liczby dni 'lutego', gdy rok jest przestępny
  if DaysInAYear(2000) = 366
   then LiczbaDni['luty'] := 29; // zmiana wartości związanej z kluczem "luty"
  // wyszukanie wartości klucza w słowniku
  if LiczbaDni.ContainsKey('marzec')
    then Write('liczba dni w marcu = ', LiczbaDni['marzec'])
    else Write('klucz "marzec" nie występuje w słowniku');
  // usunięcie słownika
  LiczbaDni.Free;
  // zatrzymanie okna konsoli
  Readln;
end.

W bibliotece FCL środowiska Lazarus, które używa kompilatora FPC, istnieje klasa generyczna TFPGMap. Przyjmuje ona dwa typy danych jako parametry: typ klucza i typ wartości. W środowisku Lazarus można też korzystać z klasy TDictionary, która jest dostępna w module Generics.Collections i działa podobnie jak ta z biblioteki VCL. Poniższy kod kompiluje się od wersji 2.6 kompilatora FPC, ponieważ użyto w nim rekordów pomocników (record helpers).

program LiczbaDniRoku;

uses
  SysUtils, DateUtils, Fgl;

var
  LiczbaDni: specialize TFPGMap<String, Integer>; // klucze typu String, wartości typu Integer

begin
  // utworzenie słownika
  LiczbaDni := specialize TFPGMap<String, Integer>.Create;
  LiczbaDni.Add('styczeń', 31); // wstawienie pary: klucz, wartość
  LiczbaDni.Add('luty', 28);
  LiczbaDni.Add('marzec', 31);
  // podaje liczbę kluczy przechowywaną w słowniku
  Writeln('liczba dodanych miesiecy: ', LiczbaDni.Count.ToString);
  // korekta liczby dni 'lutego', gdy rok jest przestępny
  if DaysInAYear(2000) = 366
   then LiczbaDni['luty'] := 29; // zmiana wartości związanej z kluczem "luty"
  // wyszukanie wartości klucza w słowniku
  if LiczbaDni.IndexOf('marzec') > -1
    then Write('liczba dni w marcu: ', LiczbaDni['marzec'])
    else Write('klucz "marzec" nie występuje w słowniku');
  // usunięcie słownika
  LiczbaDni.Free;
  // zatrzymanie okna konsoli
  Readln;
end.

Zobacz też

tablica