Map ADT: The Abstraction

A Map is a collection of <key, value> pairs. Keys must be unique and immutable.

Maps are also known as "dictionaries" or "associative arrays" or "symbol tables" in other contexts. Some references make a distinction between Map and Dictionary by defining the latter as a Map in which duplicate keys are allowed.

The core operations of a Map involve "insertion", "removal" and "update" of <key, value> pairs, as well as the lookup of a value associated with a particular key.

Maps are a very popular abstraction. To understand the versatility of Maps, consider that Arrays can be seen as Maps where keys are the array indices. In a way, a Map is a (fast) "key lookup" data structure that offers a flexible means of indexing into its individual element. Some programming languages, such as Go and Python, have "built in" Maps.

Resources