I think the first language that included native support for associated arrays was SNOBOL4 (1967), calling them tables. From THE SNOBOL4 PROGRAMMING LANGUAGE (second edition):
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.
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
Elements in the table can be assigned values In a manner similar to array elements.
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) natively supports sparse multi-dimensional arrays, stored as b-trees, but I can't really find a solid reference that explains the original design.
AWK (1977) natively supports one-dimensional sparse arrays and directly influenced Perl. PHP in turn has borrowed a lot of concepts from Perl (including associative arrays), as the first version of PHP was simply a collection of Perl scripts.
In any case, associative arrays are a fundamental and trivial data type, although implementations have certainly evolved over time, I don't really think the design changed much.