Maps/ADT

The Map Abstract Data Type (ADT) defines the interface contract that all map implementations must satisfy. It specifies what operations a map supports without prescribing how they are implemented — the hallmark of an ADT. A concrete map implementation may use a hash table, a balanced tree, a sorted array, or any other suitable data structure.

A map stores key-value pairs. Each key maps to exactly one value (the map is a function from a domain of keys to a codomain of values). Keys must be unique; distinct keys may map to the same value.

Basic operations

These five operations constitute the essential interface of any map ADT:

Operation	Pseudocode signatures	Description
get	m[k], m.get(k)	Return the value associated with key k; raise a key error if k is absent.
set	m[k] = v, m.put(k, v)	Associate value v with key k, overwriting any previous mapping.
remove	del m[k], m.remove(k)	Remove the entry for key k; raise a key error if absent.
size	len(m), m.size()	Return the number of key-value pairs in the map.
iterate	iter(m)	Return an iterator over the keys of the map.

Convenience operations

These operations can each be expressed in terms of the basic five above, but are provided for programmer convenience.

Lookup

• m.contains(k) / k in m — test whether key k exists in the map; returns boolean
• m.get(k, d) — return m[k] if key k exists; otherwise return default value d
• m.setdefault(k, d) — if key k exists return m[k]; otherwise set m[k] = d and return d

Modification

• m.pop(k, d) — remove key k and return its associated value; return d if key is absent
• m.popitem() — remove and return an arbitrary (k, v) pair; raise a key error if the map is empty
• m.clear() — remove all key-value pairs from the map

Views

• m.keys() — return a set-like view of all keys
• m.values() — return a set-like view of all values
• m.items() — return a set-like view of all (k, v) tuples

Views are live: changes to the underlying map are reflected in the view, and vice versa.

Bulk operations

• m.update(m2) — for every (k, v) pair in map m2, set m[k] = v
• m.equals(m2) — return true if the two maps contain the same key-value pairs

Expected complexity

While the ADT itself is implementation-agnostic, useful map implementations achieve the following amortized bounds:

Implementation	get	put	remove	contains
Hash table	O(1)	O(1)	O(1)	O(1)
Balanced BST	O(log n)	O(log n)	O(log n)	O(log n)
Unsorted array	O(n)	O(n)	O(n)	O(n)
Sorted array	O(log n)	O(n)	O(n)	O(log n)

Java Map interface

The Java Collections Framework specifies the map ADT through the java.util.Map<K,V> interface.

Core methods

Method	Description
size()	Return the number of key-value mappings.
isEmpty()	Return true if the map contains no mappings.
get(Object key)	Return the value to which key is mapped, or null if absent.
put(K key, V value)	Associate value with key; return the previous value, or null.
remove(Object key)	Remove the mapping for key; return the previous value, or null.
containsKey(Object key)	Return true if the map contains key.
containsValue(Object value)	Return true if the map maps one or more keys to value.
keySet()	Return a Set<K> view of the keys.
values()	Return a Collection<V> view of the values.
entrySet()	Return a Set<Map.Entry<K,V>> view of the entries.

Bulk and default methods

Method	Description
putAll(Map m)	Copy all mappings from m into this map.
clear()	Remove all mappings.
getOrDefault(Object key, V def)	Return value for key, or def if absent. (Java 8)
putIfAbsent(K key, V value)	Insert only if key is not already present. (Java 8)
replace(K key, V old, V new)	Replace value only if currently mapped to old. (Java 8)
computeIfAbsent(K key, Function f)	If key is absent, compute and insert a value via f. (Java 8)
merge(K key, V val, BiFunction remap)	Merge val with existing value using remap. (Java 8)

Standard implementations: HashMap (hash table, O(1) expected), TreeMap (red-black tree, O(log n)), LinkedHashMap (hash table with insertion-order iteration).

See also

• Maps — main Maps page with implementation notes
• Maps/AbstractMap — abstract base class
• Maps/UnsortedArrayMap — array-based concrete implementation
• Maps/SortedArrayMap — sorted-array concrete implementation
• Hash Maps — hash-table implementations (chaining and probing)
• Maps/Operations and Performance — timing benchmarks