En informàtica, una matriu associativa o hash (a 2009 no existeix un terme normalitzat en català) és un tipus d'estructura de dades que conté elements indexats amb valors únics (no poden existir dos elements amb la mateixa clau índex dins de la mateixa matriu associativa). Les claus índex poden ser claus literals o cadenes. No existeix un ordre a priori dels elements dins de la matriu. Es pot accedir a cada element a partir de la seva clau índex única.

Una matriu associativa és una generalització del concepte de matriu basat només en nombres enters com a claus d'índex, que ja proporcionaven els primers llenguatges de programació. En programació, les matrius associatives es fan servir per al mapeig d'un conjunt de valors en uns altres valors corresponents.

Operacions Les operacions habituals sobre una matriu associativa són:

Les habituals dels contenidors (vegeu l'article contenidor):

Una operació per obtenir el nombre d'elements presents a la matriu associativa Un iterador sobre cada un dels elements o bé sobre cada una de les claus de la matriu associativa, ja que a priori no existeix un ordre o una seqüència. Per exemple en el llenguatge de programació awk:

for(clau in elements) { print clau "->" elements[clau]

Les específiques d'una matriu associativa: Un constructor per crear una matriu associativa inicialment buida Una operació per afegir un nou element amb una nova clau, si encara no existeix Una operació per canviar el valor de l'element amb una determinada clau, si existeix Una operació per eliminar l'element que té una determinada clau, si existeix Una operació per obtenir el valor de l'element amb una determinada clau o, cosa que és el mateix, el mapeig d'un valor en un altre de corresponent. Una operació per verificar si ja existeix un element amb una determinada clau. Per exemple en awk:

if(clau in elements) { print clau " existeix amb valor " elements[clau] } else { print clau " no existeix"

Comparació entre llenguatges de programació Entre els llenguatges de programació que proporcionen directament matrius associatives tenim: Snobol4 (on s'anomenen "table"), MUMPS, awk (on de fet són l'únic tipus estructurat disponible), perl (on s'anomenen "hash"), tcl, Javascript, Python, Ruby, Lua, PHP, entre d'altres. En molts altres llenguatges de programació, les matrius associatives estan disponibles sense una sintaxi específica com a part de llibreries.

Entre els diferents noms que reben les matrius associatives en diferents llenguatges de programació tenim: "dictionary": en Smalltalk, Objective-C, .NET, Python, ASP "hash": en perl, Ruby "map": en C++, Java "hashtable": en Common Lisp, Windows PowerShell "collection": en Visual FoxPro "table": en Snobol4, Lua

En PHP i JavaScript totes les matrius poden ser associatives, encara que les claus han de ser o bé enters o bé strings.

Suport de llenguatges Les matrius associatives es poden implementar en qualsevol llenguatge de programació com a paquet i molts sistemes de llengües els proporcionen com a part de la seva biblioteca estàndard. En alguns idiomes, no només estan integrats en el sistema estàndard, sinó que tenen una sintaxi especial, sovint utilitzant un subíndex en forma de matriu.

El suport sintàctic incorporat per a matrius associatives va ser introduït per SNOBOL4, sota el nom "table". MUMPS va fer matrius associatives multidimensionals, opcionalment persistents, la seva estructura de dades clau. SETL va donar-hi suport com una possible implementació de conjunts i mapes. La majoria dels llenguatges d'escriptura moderns, començant per AWK i incloses Rexx, Perl, Tcl, JavaScript, Maple, Python, Ruby, Wolfram Language, Go, i Lua, suporten matrius associatives com a tipus de contenidor principal. En molts altres llenguatges, estan disponibles com a funcions de biblioteca sense una sintaxi especial.

A Smalltalk, Objective-C, .NET, Python, REALbasic, Swift, VBA i Delphi s'anomenen diccionaris; a Perl, Ruby i Seed7 s'anomena hashes; a C++, Java, Go, Clojure, Scala, OCaml, Haskell s'anomene maps (vegeu mapa (C++), mapa desordenat (C++), i ); a Common Lisp i Windows PowerShell, s'anomenen hash tables (ja que tots dos solen utilitzar aquesta implementació); a Maple i Lua, s'anomenen tables. A PHP, totes les matrius poden ser associatives, excepte que les claus es limiten a enters i cadenes. A JavaScript (vegeu també JSON), tots els objectes es comporten com a matrius associatives amb claus valorades per cadenes, mentre que els tipus Map i WeakMap tenen objectes arbitraris com a claus. A Lua, s'utilitzen com a bloc de construcció primitiu per a totes les estructures de dades. A Visual FoxPro, s'anomenen Collections. El dlenguatge D també té suport per a matrius associatives.

Referències

Enllaços externs NIST's Dictionary of Algorithms and Data Structures: Associative Array

Categoria:Dades informàtiques Categoria:Tipus abstracte de dades