Maps

See also: Dictionaries

Maps are value-based data structures that create a bijection from one set onto another, such that one input key yields one corresponding output value.

Notes

Maps are, under the hood, related to the concept of a Function - a map from one set onto another.

Under the hood, maps can take many forms. They can be stored as a simple unsorted array of key-value item objects. They can be stored in a sorted array of key-value items. They can be stored with a tree. They can be stored with a hash table. etc.

These are essentially identical to Dictionaries.

Maps ADT

See Maps/ADT for abstract data type/interface specification for Maps.

See Java API docs page for Map class for Java Collections interface class Map: http://docs.oracle.com/javase/8/docs/api/java/util/Map.html

Example: word counts

A canonical example of maps is performing word counts for text files. Each word is added to the dictionary as a key, and the word count is the value. Keys are added with a default key value of 1, and if a word already exists as a key its value is incremented.

Pseudocode:

create empty map
for each word in input file:
    if(word in map keys):
        increment value at key word
    else:
        add new pair (word, 1) to map

Map classification

Map types are organized as follows:

• Unsorted maps
• Hash maps
• Sorted maps

See implementations below.

Map Implementations

For implementations of maps, see the following:

Map abstract data type:

• Maps/ADT

Map base class (implements most of the ADT above):

• Maps/MapBase

Map implementations using arrays:

• Maps/UnsortedArrayMap
• Maps/SortedArrayMap

Map implementations using hash tables:

• Maps/HashMapBase
• Maps/ChainHashMap
• Maps/ProbeHashMap