What is the difference between a map and a diction

Question

I know a map is a data structure that maps keys to values. Isn't a dictionary the same? What is the difference between a map and a dictionary¹?

---

_{1. I am not asking for how they are defined in language X or Y (which seems to be what generally people are asking here on SO), I want to know what is their difference in theory.}

Answer 1

These are two different terms for the same concept.
Hashtable and HashMap also refer to the same concept.

Answer 2

One is an older term for the other. Typically the term "dictionary" was used before the mathematical term "map" took hold. Also, dictionaries tend to have a key type of string, but that's not 100% true everywhere.

Answer 3

Typically I assume that a map is backed by a hash table; it connotes an unordered store. Dictionaries connote an ordered store.

There is a tree-based dictionary called a Trie.

In Lisp, it might look like this:

(a (n (d t)) n d )

Which encapsulates the words:

• a
• and
• ant
• an
• ad

The traversal from the top to the leaf yields a word.

Answer 4

Other terms for this concept that are fairly common: associative array and hash.

Answer 5

so on a purely theoretical level.

A Dictionary is a value that can be used to locate a Linked Value. A Map is a Value that provides instructions on how to locate another values

all collections that allow non linear access (ie only get first or get last) are a Map, as even a simple Array has an index that maps to the correct value. So while a Dictionary is a Type of map, maps are a much broader range of possible function.

In Practice a its usually the mapping function that defines the name, so a HashMap is a mapped data structure that uses a hashing algorithm to link the key to the value, where as a Dictionary doesn't specify how the keys are linked to a value so could be stored via a linked list, tree or any other algorithm. from the usage end you usually don't care what the algorithm only that they work so you use a generic dictionary and only shift to one of the other structures only when you need to enfore the type of algorithm

Answer 6

Yes, they are the same, you may add "Associative Array" to the mix.

using Hashtable or a Hash ofter refers to the implementation.