COMP 210: Data Structures

Maps / Dictionaries / Associative Arrays

Mathematics:

In mathematics, a mapping is an operation that associates each element of a given set (the domain) with an element from another set (the range).
The term can often be used interchangably with function.

Computing:

In computing, we might say that a function is a map if it takes a single value as a parameter; it maps the parameter to the return value.

We can also use the term Map to refer to a data structure that is a collection of similar associations, called key-value pairs. Each key in a map is unique and is associated with a single value.

This data structures is also known as a dictionary, an associative array, or a hash map.

Dictionaries are used for efficient data retrieval by looking up a value directly using its key. Additional standard operations include inserting, updating, or deleting key-value pairs. In general, entries are inserted into a dictionary in a way that optimizes searching based on the key, so iterating through entries may result in an order that is different from the order in which they were inserted. ¹

The Java Map Interface

The Java Collections Framework includes a Map interface and several associated classes.

The Map interface takes 2 type parameters: the type used for the Keys and the type used for the mapped Values: Map<K, V>. The interface also includes a nested interface for a key-value pair serving as an entry in the map: Map.Entry<K,V>.

A few of the most important Map methods are:

put(K key, V value): Associates the specified value with the specified key in this map.
get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
remove(Object key): Removes the mapping for a key from this map if it is present.
size(): Returns the number of key-value mappings in this map.
isEmpty(): Returns true if this map contains no key-value mappings.
clear(): Removes all of the mappings from this map.
containsKey(Object key): Returns true if this map contains a mapping for the specified key.
containsValue(Object value): Returns true if this map maps one or more keys to the specified value.
keySet(): Returns a Set view of the keys contained in this map.
values(): Returns a Collection view of the values contained in this map.
entrySet(): Returns a Set view of the key-value mappings contained in this map.

It is important to note that a map is not a one-to-one relationship. Any given key has only one value associated with it, but other keys may map to that same value. Thus, although the set of keys is, in fact, a Set (there cannot be duplicate keys), the “set” of values is a more general Collection because values may be associated with multiple keys and therefore repeated.

Provided Map Classes in Java

The most basic map classes in the Java Collections Framework are:

HashMap: A hash table-based implementation that offers fast average-case performance for basic operations. It does not guarantee any specific order.
TreeMap: A red-black tree-based implementation that stores elements in a sorted order based on the natural ordering of its keys or a custom Comparator.

There is also a LinkedHashMap class that extends HashMap but maintains the insertion order of the entries.²

More Information

For more information, see the Java documentation for the Map interface and its classes (especially HashMap). Many other resources are available online, including GeeksForGeeks and W3Schools, for example.

Aside #1: In functional languages, there is often a function called map that takes 2 parameters – another function and a list – and applies the second function to every item in the list, creating a new list of all of the individual results. The function being applied should take a single parameter, one of the items in the list. In other words, the parameter function is a true mapping function, while the map function is not. A better name for it might have been applyMap, but that is not the convention. For example, if we had an addOne function that takes an integer parameter and returns that value plus 1, and if we had a list containing the values 1, 5, 10, 15, 20, then
```
map (addOne, myList)
```
would create a list with the values 2, 6, 11, 16, and 21.↩
Aside #2: Java originally had a Dictionary class. They needed a different name when they developed the Java Collections Framework, in order not to break existing code, hence the use of the name Map for the interface.↩

Author: Alyce Brady, Kalamazoo College. Some phrases were provided by Oracle’s Java documentation or Google AI Overviews.
Date: 9 November 2025