Array associatiu (estructura de dades)

En informàtica, un array associatiu 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 del mateix array associatiu). Les claus índex poden ser claus literals o strings. No existeix un ordre a priori dels elements dins de l'array. Es pot accedir a cada element a partir de la seva clau index única.

Un array associatiu és una generalització del concepte d'array basat només en nombres enters com a claus d'índex, que ja proporcionaven els primers llenguatges de programació. En programació, els arrays associatius es fan servir per al mapeig d'un conjunt de valors en uns altres valors corresponents.

Operacions

Les operacions habituals sobre un array associatiu són:

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

• Una operació per obtenir el nombre d'elements presents a l'array associatiu
• Un iterador sobre cada un dels elements o bé sobre cada una de les claus de l'array associatiu, 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'un array associatiu:

• Un constructor per crear un array associatiu inicialment buit
• 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 arrays associatius 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 altres. En molts altres llenguatges de programació, els arrays associatius estan disponibles sense una sintaxi específica com a part de llibreries.

Entre els diferents noms que reben els arrays associatius 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 tots els arrays poden ser associatius, 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 Map); 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.

Enllaços externs

• NIST's Dictionary of Algorithms and Data Structures: Associative Array