Notes

The term "map" is a kind of hat tip to mathematics. The mathematical definition of a function is, a mapping from one set (the domain) onto another (the range) such that one input corresponds to exactly one output. This is a bijective mapping between two sets. That's all we require - one key gives one value.

Maps can take on many different impementations. 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.

While these data structures are nominally a little bit different from Dictionaries - dictionaries return positions in a data structure given an input object x) - they are ultimately a generalization of them (the position can be thought of as the value stored by the map, while the input object x is the key) and therefore identical.

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:

Map implementations using hash tables:

Flags

Maps

From charlesreid1

Contents