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 distinguish 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 element. Some programming languages, such as Go and Python, have "built-in" Maps.

Resources