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).