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

Python mapping protocol

Python specifies the map ADT through two abstract base classes in collections.abc: the read-only Mapping and the mutable MutableMapping (which extends Mapping). The built-in dict type is the primary concrete implementation; user-defined map types can register as virtual subclasses or inherit directly from these ABCs.

The ABC hierarchy relevant to maps:

• Container → Collection → Mapping → MutableMapping
• Iterable → Collection
• Sized → Collection

A minimal concrete MutableMapping must implement five abstract methods: __getitem__, __setitem__, __delitem__, __iter__, and __len__. All other mixin methods are derived from these five.

Core methods — Mapping (read-only)

Method	Description
m[k] (__getitem__)	Return the value for key k; raise KeyError if absent. Abstract.
k in m (__contains__)	Return True if key k is present. Default: iterate and compare.
len(m) (__len__)	Return the number of key-value pairs. Abstract.
iter(m) (__iter__)	Return an iterator over the keys. Abstract.
m.keys()	Return a KeysView (set-like) of all keys.
m.values()	Return a ValuesView of all values.
m.items()	Return an ItemsView (set-like) of (k, v) tuples.
m.get(k, d=None)	Return m[k] if key exists; otherwise return default d.
m == m2 (__eq__)	Return True if both maps have the same key-value pairs.

All views are live: they reflect changes to the underlying map.

Mutable methods — MutableMapping

Method	Description
m[k] = v (__setitem__)	Insert or overwrite the mapping for key k. Abstract.
del m[k] (__delitem__)	Remove the mapping for key k; raise KeyError if absent. Abstract.
m.pop(k, d)	Remove key k and return its value; return d (or raise KeyError) if absent.
m.popitem()	Remove and return an arbitrary (k, v) pair; raise KeyError if empty.
m.setdefault(k, d=None)	Return m[k] if present; otherwise set m[k] = d and return d.
m.clear()	Remove all key-value pairs.
m.update(m2)	For every (k, v) in m2 (or from keyword arguments), set m[k] = v.

Dict-specific methods

Beyond the MutableMapping contract, dict provides:

Method	Description
dict.fromkeys(iterable, v=None)	Class method: build a new dict with keys from an iterable, all mapped to value v.
m.copy()	Return a shallow copy of the dict.
m2 (__or__)	Return a new dict merging m and m2. (Python 3.9+)
= m2 (__ior__)	In-place merge: update m with m2. (Python 3.9+)
reversed(m) (__reversed__)	Return a reverse iterator over keys. (Python 3.8+)

Standard implementations

Class	Module	Backing	Notes
dict	built-in	Hash table, O(1) expected	The default mapping type. Insertion-ordered since Python 3.7.
OrderedDict	collections	Doubly-linked list + hash table	Remembers insertion order (present since Python 3.1; dict also preserves order since 3.7, but OrderedDict adds move_to_end and order-sensitive equality).
defaultdict	collections	Hash table	Missing keys are auto-created by a user-supplied factory function.
Counter	collections	Hash table	operators.
ChainMap	collections	Linked list of mappings	Chains multiple mappings together; lookups search each in order.
MappingProxyType	types	Wraps a dict	Read-only dynamic view onto another mapping.

Python has no balanced-BST map in the standard library. Third-party packages such as sortedcontainers provide SortedDict with O(log n) operations.

Example: minimal custom MutableMapping

from collections.abc import MutableMapping

class SingleEntryMap(MutableMapping):
    """A map that holds at most one key-value pair."""

    def __init__(self):
        self._key = None
        self._value = None

    def __getitem__(self, key):
        if self._key == key:
            return self._value
        raise KeyError(key)

    def __setitem__(self, key, value):
        self._key = key
        self._value = value

    def __delitem__(self, key):
        if self._key == key:
            self._key = None
            self._value = None
        else:
            raise KeyError(key)

    def __iter__(self):
        if self._key is not None:
            yield self._key

    def __len__(self):
        return 1 if self._key is not None else 0

    def __repr__(self):
        return repr(dict(self)) if self._key is not None else '{}'

Implementing the five abstract methods automatically provides keys(), values(), items(), get(), pop(), popitem(), setdefault(), clear(), update(), __contains__, and __eq__ — all supplied by the MutableMapping mixin.

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