Storia della matrice associativa?

Penso che la prima lingua che includeva il supporto nativo per gli array associati era SNOBOL4 (1967), chiamandoli tabelle. Da LA LINGUA DI PROGRAMMAZIONE SNOBOL4 (seconda edizione) :

Often it is desirable to associate a group of items with one variable name through numerical indexing or some other identifying property. The SNOBOL4 array and table provide these capabilities with more flexibility than most programming languages. An array is a data element consisting of a set of pointers to other data elements, so that each array element may be any data type, even an array. An element of an array is referenced by using an integer index. A table is similar to an array, except that the reference value need not be an integer, but can be any of several other types. Conversion can be made between tables and arrays.

...

1.13 Tables

Sets of pairs of associated data objects can be created by the use of tables. A table is similar to a one-dimensional array. However, instead of referencing an element with an integer, any data object can be used.

A table is created by the primitive function TABLE. For example

T TABLE ( ) 

creates a table and assigns it as value of T.

Elements in the table can be assigned values In a manner similar to array elements.

Examples are

T<'A'> 5 

and

T T + 1

Tables have varying lengths and are dynamically extended if necessary. Some efficiency can be achieved by specifying an estimate of the size of a table at the time it is created. TABLE (N) creates a table that initially has room for N entries.

MUMPS (1966) supporta nativamente array multidimensionali sparsi, memorizzati come b-tree, ma non posso trova davvero un solido riferimento che spiega il design originale.

AWK (1977) supporta nativamente array sparsi monodimensionali e influisce direttamente sul Perl. PHP a sua volta ha preso in prestito molti concetti da Perl (compresi gli array associativi), poiché la prima versione di PHP era semplicemente una raccolta di script Perl.

In ogni caso, gli array associativi sono un tipo di dati fondamentale e banale, anche se le implementazioni si sono certamente evolute nel tempo, non penso che il design sia cambiato molto.

Which language first adopted such a design? And how was this design evolved?

Non so se è stato il primo, ma AWK aveva array associativi molto prima che Perl, Python, Ruby, PHP, ecc. fossero mai stati concepiti. Aggiornamento: Yannis dice che SNOBOL4 aveva array associativi prima di AWK, e non ci sono voluti molti googling per trovare una pagina che accetta . Ecco un pezzo interessante su come gli array associativi sono implementati in SNOBOL4 .

Sebbene altri linguaggi iniziali come Lisp potrebbero non avere il supporto esplicito per gli array associativi come tipo predefinito, è possibile implementarli facilmente in altri modi. In Lisp, ad esempio, è possibile implementare un array associativo come un elenco di elenchi in cui ogni sotto-elenco ha due elementi: una chiave e un valore.

Ti interessa la storia del concetto di array associativo, in cui i valori sono accessibili usando una chiave piuttosto che un indice numerico, o sei interessato alla storia degli algoritmi utilizzati per implementare gli array associativi? Le tabelle hash sono comunemente usate per implementare array associativi, ma come mostra il link SNOBOL4 sopra, non sono l'unica implementazione possibile.

L'idea di associare chiavi e valori è certamente precedente ai linguaggi e ai computer del computer. I cataloghi di schede e gli indici di libri sono solo due esempi di array associativi reali.