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:

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:

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

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.

Flags

Maps in Java

From charlesreid1

Contents

Notes

Interface hierarchy

Map interface (the root)

AbstractMap

Concrete implementations

HashMap

TreeMap

LinkedHashMap

Hashtable

ConcurrentHashMap

WeakHashMap

IdentityHashMap

EnumMap

Comparison of implementations

See also

Flags