Maps
From charlesreid1
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.
Basic properties of maps
Example: word counts
Hash maps
Unsorted maps
Sorted maps
Implementations
For implementations of maps, see the following:
Map base class:
Map implementations using arrays:
Map implementations using hash tables:
- Maps
- Map example - word counts
- Hash tables
- Sorted maps
- Skip lists
- Sets
- Multisets
- Multimaps
 |
Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
|