Maps in Java

Notes

Maps are implemented in Java as part of the Java Collections Framework. Although maps do not extend the Template:Code interface, they are part of the overall Collections Framework.

Here is a link to the OpenJDK source code, Template:Code module:

• JDK 8: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/
• JDK 11+: https://github.com/openjdk/jdk/tree/master/src/java.base/share/classes/java/util

The Java Collections Framework provides a rich hierarchy of map interfaces and concrete implementations.

Interface hierarchy

The map-related interfaces form the following hierarchy:

Interface	Description
Template:Code	The root interface. Defines the contract that all map implementations must satisfy. This is an interface, not an abstract class.
Template:Code	Extends Template:Code. A map whose keys are stored in sorted (ascending) order. Provides methods like Template:Code, Template:Code, Template:Code, Template:Code, and Template:Code.
Template:Code	Extends Template:Code. Adds navigation methods returning the closest matches for given search targets: Template:Code, Template:Code, Template:Code, Template:Code, as well as Template:Code and Template:Code.
Template:Code	Extends Template:Code. Adds thread-safe atomic operations such as Template:Code, Template:Code (key+value form), Template:Code, and Template:Code methods.
Template:Code	Extends both Template:Code and Template:Code. Provides a thread-safe navigable map.

Map interface (the root)

Template:Code is the top-level contract for maps. It is an interface, not an abstract class. It declares all the fundamental map operations.

Source (JDK 8): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/Map.java

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

Template:Code defines core methods including:

• Template:Code, Template:Code
• Template:Code, Template:Code, Template:Code
• Template:Code, Template:Code
• Template:Code, Template:Code, Template:Code
• Template:Code, Template:Code

Java 8 added default method implementations for functional-style operations:

• Template:Code
• Template:Code
• Template:Code and Template:Code
• Template:Code
• Template:Code
• Template:Code
• Template:Code
• Template:Code
• Template:Code

AbstractMap

Template:Code is an abstract class that implements the Template:Code interface. It provides skeletal implementations of most Template:Code operations, minimizing the effort required to create a concrete map implementation. Subclasses need only implement Template:Code to have a fully functioning (unmodifiable) map; implementing Template:Code as well yields a modifiable map.

Source (JDK 8): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/AbstractMap.java

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/AbstractMap.html

Constructor (protected, for subclass use only):

public abstract class AbstractMap<K,V> implements Map<K,V> {
    /**
     * Sole constructor.  (For invocation by subclass constructors, typically
     * implicit.)
     */
    protected AbstractMap() {
    }

Template:Code method — iterates the entry set, handling null values safely:

    public boolean containsValue(Object value) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if (value==null) {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getValue()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (value.equals(e.getValue()))
                    return true;
            }
        }
        return false;
    }

Template:Code method — uses an explicit Template:Code pointer to track the entry to delete, then calls the iterator's Template:Code:

    public V remove(Object key) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        Entry<K,V> correctEntry = null;
        if (key==null) {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    correctEntry = e;
            }
        } else {
            while (correctEntry==null && i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    correctEntry = e;
            }
        }
        V oldValue = null;
        if (correctEntry !=null) {
            oldValue = correctEntry.getValue();
            i.remove();
        }
        return oldValue;
    }

Concrete implementations

HashMap

Template:Code is the standard general-purpose hash-table-based map implementation. It provides O(1) expected-time performance for Template:Code and Template:Code operations, assuming the hash function disperses keys properly among buckets.

Source (JDK 8): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/HashMap.java

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

Key characteristics:

• Extends Template:Code and implements Template:Code, Template:Code, Template:Code.
• Uses separate chaining with bins (linked lists). Starting in Java 8, when a bin accumulates enough collisions (Template:Code = 8), the bin is converted to a balanced tree (Template:Code), improving worst-case performance from O(n) to O(log n).
• Permits Template:Code keys and Template:Code values.
• Not synchronized. For a thread-safe counterpart, use Template:Code or Template:Code.
• Two configurable parameters affect performance: initial capacity (the number of buckets at creation) and load factor (the fraction of capacity at which the map is resized; default 0.75).
• The iterators returned by Template:Code, Template:Code, and Template:Code are fail-fast: if the map is structurally modified after an iterator is created (except through the iterator's own Template:Code method), the iterator throws Template:Code.

From the implementation comments describing the tree-bin transition:

     * The use and transitions among plain vs tree modes is
     * complicated by the existence of subclass LinkedHashMap. See
     * below for hook methods defined to be invoked upon insertion,
     * removal and access that allow LinkedHashMap internals to
     * otherwise remain independent of these mechanics. (This also
     * requires that a map instance be passed to some utility methods
     * that may create new nodes.)
     *
     * The concurrent-programming-like SSA-based coding style helps
     * avoid aliasing errors amid all of the twisty pointer operations.

TreeMap

Template:Code is a Red-Black tree-based implementation of the Template:Code interface. It stores keys in sorted (natural or Comparator-defined) order, yielding O(log n) time for Template:Code, Template:Code, Template:Code, Template:Code, and most other operations.

Source (JDK 8): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/TreeMap.java

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

Key characteristics:

• Extends Template:Code and implements Template:Code, Template:Code, Template:Code.
• Maintains keys in ascending sorted order, either by their natural ordering (Template:Code) or by a Template:Code supplied at construction time.
• Provides efficient access to min and max keys via Template:Code / Template:Code and Template:Code / Template:Code (both O(log n)).
• Template:Code methods like Template:Code, Template:Code, Template:Code, Template:Code allow range queries — each O(log n).
• Does not permit Template:Code keys (a Template:Code is thrown when a Template:Code key is used with natural ordering, or when the Template:Code does not allow Template:Code).
• Not synchronized.
• Slower than Template:Code for basic lookup/insertion (O(log n) vs. O(1) expected), but preferred when sorted traversal or range queries are needed.

LinkedHashMap

Template:Code extends Template:Code and maintains a doubly-linked list running through all entries. This preserves iteration order — either insertion order (default) or access order (configurable via constructor).

Source (JDK 8): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/LinkedHashMap.java

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Key characteristics:

• Extends Template:Code and implements Template:Code.
• Performance is slightly lower than Template:Code due to the overhead of maintaining the linked list, but iteration over the entry set is proportional to size (not capacity), unlike Template:Code.
• When constructed in access-order mode (Template:Code), it is suitable for building an LRU (least-recently-used) cache: override Template:Code to evict the oldest entry when the map exceeds a desired size.
• Not synchronized.

Class declaration:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

The doubly-linked list is managed with Template:Code and Template:Code pointers (line 199 of the source):

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

Private utility method for linking a node at the end of the list (line 217):

    // link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

Hashtable

Template:Code is a legacy hash-table-based map implementation that predates the Collections Framework. It was retrofitted to implement Template:Code when the Collections Framework was introduced in Java 1.2.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html

Key characteristics:

• Synchronized — all methods are thread-safe through intrinsic locking on the Template:Code instance. This makes it slower than Template:Code for single-threaded use.
• Does not permit Template:Code keys or Template:Code values (throws Template:Code).
• Largely superseded by Template:Code (non-synchronized) and Template:Code (for concurrent use). Template:Code is considered a legacy class; new code should prefer Template:Code or Template:Code.

ConcurrentHashMap

Template:Code is a highly concurrent, thread-safe hash-table-based map. Unlike Template:Code (which locks the entire map for every operation), Template:Code uses fine-grained locking (lock striping) to allow concurrent reads and a configurable number of concurrent writes.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html

Key characteristics:

• Implements Template:Code and Template:Code.
• Does not permit Template:Code keys or Template:Code values.
• Obsoletes Template:Code for concurrent use cases. Provides dramatically better scalability under contention.
• Supports atomic compound operations: Template:Code, Template:Code, Template:Code.
• Iterators are weakly consistent: they reflect the state of the map at some point since the iterator was created, do not throw Template:Code, and may proceed concurrently with other operations.
• Bulk operations (Template:Code, Template:Code, Template:Code) support parallelism via the common Template:Code.

WeakHashMap

Template:Code is a hash-table-based map whose keys are held via weak references. When a key is no longer strongly reachable from elsewhere in the application, the garbage collector may reclaim it, and the corresponding entry is automatically removed from the map.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/WeakHashMap.html

This is useful for canonicalizing or caching mappings where the lifetime of the entry should not prevent garbage collection of the key. Example use case: storing metadata about objects without preventing those objects from being garbage-collected.

IdentityHashMap

Template:Code is a hash-table-based map that uses reference equality (Template:Code) instead of object equality (Template:Code) when comparing keys. This violates the general Template:Code contract — it is intended for rare use cases where reference-equality semantics are required, such as topology-preserving object graphs, serialization, or proxy objects.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/IdentityHashMap.html

EnumMap

Template:Code is a specialized map implementation for enum keys. Internally, it uses a compact array indexed by the enum's ordinal values, yielding extremely fast O(1) performance with minimal memory overhead.

Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/EnumMap.html

Key characteristics:

• All keys in an Template:Code must belong to a single enum type, specified at construction time.
• Does not permit Template:Code keys; permits Template:Code values.
• Iteration order follows the natural order of the enum constants (the order in which they are declared).
• Extremely efficient: uses a plain Java array internally (one array slot per enum constant), avoiding hashing overhead entirely.
• Not synchronized.

Comparison of implementations

Implementation	Interface	Underlying structure	Ordering	Template:Code keys	Template:Code values	Thread-safe	Typical Template:Code / Template:Code
Template:Code	Template:Code	Hash table (+ tree bins)	None	Yes	Yes	No	O(1) expected
Template:Code	Template:Code	Hash table + doubly-linked list	Insertion or access order	Yes	Yes	No	O(1) expected
Template:Code	Template:Code	Red-Black tree	Sorted (natural or Comparator)	No*	Yes	No	O(log n)
Template:Code	Template:Code	Hash table	None	No	No	Yes (per-method)	O(1) expected
Template:Code	Template:Code	Hash table (lock-striped)	None	No	No	Yes (non-blocking reads)	O(1) expected
Template:Code	Template:Code	Hash table (weak ref keys)	None	Yes	Yes	No	O(1) expected
Template:Code	Template:Code	Array (linear-probe, ref-equality)	None	Yes	Yes	No	O(1) expected
Template:Code	Template:Code	Array (indexed by enum ordinal)	Enum declaration order	No	Yes	No	O(1)

Template:Code permits Template:Code keys only if the Template:Code supports them; with natural ordering, a Template:Code is thrown.

See also

• Maps — main Maps page
• Maps/ADT — Map Abstract Data Type specification
• Maps/AbstractMap — AbstractMap implementation notes
• Hash Maps — custom hash-table implementations
• Java/Collections — overview of the Java Collections Framework