I'm having a discussion elsewhere about this. I suspect that it was Perl, with the hash maps, but that is because I don't know much about older languages rather than any exhaustive research on the matter. The wikipedia article says that the data structure was invented in 1953, so it is plausible that there are earlier examples.
AWK had associative arrays from day one.
Associative arrays seem to have been introduced in SNOBOL4.