A multimap is a generalization of a map or associative array

Associative array

In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....

 abstract data type

Abstract data type

In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...

 in which more than one value may be associated with and returned for a given key. Both map and multimap are particular cases of container

Container (data structure)

In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...

s (see for example C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

 Standard Template Library

Standard Template Library

The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...

 containers). Often the multimap is implemented as a map with lists or set

Set (computer science)

In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...

s 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.
• Querystrings may have multiple values associated with a single field. This is commonly generated when a web form allows multiple check boxes
  Check box
  In computing, a checkbox is a graphical user interface element that permits the user to make multiple selections from a number of options or to have the user answer yes or no on a simple yes/no question.Normally, checkboxes are shown on...
  
   or selections to be chosen in response to a single form element.

Language support

C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

's Standard Template Library

Standard Template Library

The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...

 provides the multimap container for the sorted multimap using a self-balancing binary search tree

Self-balancing binary search tree

In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....

, and SGI

Silicon Graphics International

Silicon Graphics International Corp. , is an American manufacturer of computer hardware and software, including high-performance computing solutions, x86-based servers for datacenter deployment, and visualization products...

's STL extension provides the hash_multimap container, which implements a multimap using a hash table

Hash table

In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...

.

Apache Commons Collections provides a MultiMap interface for Java

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

. It also provides a MultiValueMap implementing class that makes a MultiMap out of a Map object and a type of Collection.

Google Collections also provides an interface Multimap and implementations.

Scala language's API also provides Multimap and implementations

See also

• Abstract data type
  Abstract data type
  In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
  
   for the type of concept in general
• Associative array
  Associative array
  In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
  
   for the more fundamental abstract data type
• Multiset
  Multiset
  In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
  
  for the case where same item can appear several times