Maps: Difference between revisions
From charlesreid1
No edit summary |
(→Notes) |
||
| Line 9: | Line 9: | ||
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. | 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]]. | |||
==Example: word counts== | ==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. | |||
== | ==Map classification== | ||
Map types are organized as follows: | |||
* Unsorted maps | |||
* Hash maps | |||
* Sorted maps | |||
See implementations below. | |||
==Map Implementations== | ==Map Implementations== | ||
| Line 34: | Line 39: | ||
* [[Maps/ChainHashMap]] | * [[Maps/ChainHashMap]] | ||
* [[Maps/ProbeHashMap]] | * [[Maps/ProbeHashMap]] | ||
=Flags= | =Flags= | ||
{{MapsFlag}} | {{MapsFlag}} | ||
Revision as of 04:06, 21 June 2017
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.
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.
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 base class:
Map implementations using arrays:
Map implementations using hash tables:
Flags
 |
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
|