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 Functions - 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.

Implementations

For implementations of maps, see the following:

Map base class:

• Maps/MapBase

Map implementations using arrays:

• Maps/UnsortedArrayMap
• Maps/SortedArrayMap

Map implementations using hash tables:

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

• Maps
• Map example - word counts
• Hash tables
• Sorted maps
• Skip lists
• Sets
• Multisets
• Multimaps