Maps in Java

From charlesreid1

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:

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:

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:

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:

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

Flags


CSFlag.jpg
Maps and Dictionaries
Part of Computer Science Notes

Series on Data Structures


Maps and Sets Study Guide  · Hash Tables Study Guide


Maps/Dictionaries

Maps  · Maps/ADT  · Maps in Java  · Maps/OOP  · Maps/Operations and Performance

Multimaps  · Guava Maps

Map implementations: Maps/AbstractMap  · Maps/UnsortedArrayMap  · Maps/SortedArrayMap

Dictionaries

Dictionary implementations: Dictionaries/LinkedDict  · Dictionaries/ArrayDict


Hashes

Hash Maps/OOP  · Hash Maps/Operations and Performance

Hash Maps/Dynamic Resizing  · Hash Maps/Collision Handling with Chaining

Hash functions: Hash Functions  · Hash Functions/Cyclic Permutation

Hash map implementations: Hash Maps/AbstractHashMap  · Hash Maps/ChainedHashMap


Skip Lists

Skip Lists  · Java/ConcurrentSkipList  ·

Java implementations: SkipList


Sets

Sets  · Sets/ADT  · Sets in Java  · Sets/OOP  · Multisets


Flags  · Template:MapsFlagBase  · e



Retrieved from "https://charlesreid1.com/w/index.php?title=Maps_in_Java&oldid=30538"