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.
Not sure if there is a definitive answer but Smalltalk certainly had dictionaries (hash maps) built into the language (as such it can be given an OO language) and Smalltalk predates Perl.
AWK had associative arrays from day one.
Associative arrays seem to have been introduced in SNOBOL4.