I'm designing a programming language, so I've been putting a lot of thought into the way base types are named.
"Dictionary" seems like a bad name for what dictionaries do. They aren't organized lists of words with their definitions; they don't deal with words, they don't with definitions, and they aren't lists. The only vague association they have with the word "dictionary" is that one performs "lookups" just as one does with a paper dictionary (which is as good an argument for calling them "phone books").
"HashTable" describes an implementation which may change.
"Key/value pair set" seems most accurate but it too long to be useful (do you really want to type "KeyValuePairSet" every time?).
If we call a "key/value pair" an "association" we get "AssociationSet". That to me is the best but doesn't jump out at me as the right answer yet; it's still long and "set" still feels a bit wrong. "AssociationList" is worse ("list" implies ordering, which isn't there). I briefly considered just "Associations" but that sounds more like something I would name an instance rather than the class. "RelationSet" and "PairSet" are shorter but less descriptive (neither captures the fact that it's sort of a one-way relationship key to value; value to key is not meaningful within the context of dictionaries).
Any ideas what a better name for dictionaries might be?