Multimap (data structure)
- Multimap (data structure)
A multimap is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Both map and multimap are particular cases of containers (see for example C++ Standard Template Library containers). Often the multimap is implemented as a map with lists or sets as the map values.
Examples
* In a student enrollment system, where students may be enrolled in multiple classes simultaneously, there might be an association for each enrollment of a student in a course, where the key is the student ID and the value is the course ID. If a student is enrolled in three courses, there will be three associations containing the same key.
* The index of a book may report any number of references for a given index term, and thus may be coded as a multimap from index terms to any number of reference locations.
Language Support
C++'s Standard Template Library provides the "multimap" container for the sorted multimap using a self-balancing binary search tree [http://www.sgi.com/tech/stl/Multimap.html] , and SGI's STL extension provides the "hash_multimap" container, which implements a multimap using a hash table [http://www.sgi.com/tech/stl/hash_multiset.html] .
Apache Commons Collections provides a [http://commons.apache.org/collections/api-release/org/apache/commons/collections/MultiMap.html MultiMap] interface for Java. It also provides a [http://commons.apache.org/collections/api-release/org/apache/commons/collections/map/MultiValueMap.html MultiValueMap] implementing class that makes a MultiMap out of a Map object and a type of Collection.
Google Collections also provides an interface [http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html Multimap] and implementations.
See also
* Abstract data type for the type of concept in general
* Associative array for the more fundamental abstract data type
* Multiset for the case where same item can appear several times
Wikimedia Foundation.
2010.
Look at other dictionaries:
Data structure — In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly … Wikipedia
Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… … Wikipedia
Container (data structure) — For the abstract notion of containers in Type theory, see Container (Type theory). In computer science, a container is a class, a data structure[1][2], or an abstract data type (ADT) whose instances are collections of other objects. In other… … Wikipedia
Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap … Wikipedia
multimap — noun A data structure that maps a single key to multiple values … Wiktionary
Abstract data type — In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations. The… … Wikipedia
Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space … Wikipedia
Associative array — In computer science, an associative array (also called a map or a dictionary) is an abstract data type composed of a collection of (key,value) pairs, such that each possible key appears at most once in the collection. Operations associated with… … Wikipedia
Web mapping — is the process of designing, implementing, generating and delivering maps on the World Wide Web and its product. While web mapping primarily deals with technological issues, web cartography additionally studies theoretic aspects: the use of web… … Wikipedia
Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… … Wikipedia
