Maps in Java

Notes

Maps are implemented in Java as part of the Collections framework. These are notes from the source.

Here is a link to the OpenJDK source code, util module: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/

The Java Collections framework provides a number of different useful map-related classes.

Map

The top level map-related class is an abstract class called Map.

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

Docs: Docs: https://docs.oracle.com/javase/7/docs/api/java/util/Map.html

AbstractMap

The next level down is a step toward concrete implementations of a map, but it is not a concrete implementation itself. AbstractMap is an abstraact class. This minimizes the amount of work required to extend the map type.

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

Docs: https://docs.oracle.com/javase/7/docs/api/java/util/AbstractMap.html

Constructor:

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

Search method, checking if a map contains a value:

    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;
    }

Check out the remove method:

    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;
    }

using correctEntry as a pointer.

HashMap

HashMap is a faster, O(1) map that uses a hash table to store data but stores the data in an unsorted fashion.

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

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

• HashMap class extends the abstract map type
• HashMap class uses a binned approach (like separate chaining). If there enough collisions it converts the bins to TreeNodes.
• This is similar to the Hashtable class (see below), except that it is unsynchronized and accepts null values and null keys
• This provides constant time get and put functions, assuming hash function disperses among buckets properly
• Two parameters, initial capacity and load factor, set performance of object

IDK, there's kind of a LOT here...

From the comments at the beginning of the class:

     * 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

TreeMap is a slower, O(log N) map that uses a tree structure to store data in a sorted fashion. This provides faster access to max/min of data.

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

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

LinkedHashMap

There is also a LinkedHashMap, which implements a Hash Map using a linked structure. This is a child class of HashMap. "This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries."

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

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

Here is the class declaration:

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

Here on line 199 we see the double pointers of head and tail for this doubly-linked list: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/LinkedHashMap.java#l199

    /**
     * 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;

The way this class is organized is to implement private utility methods, and expose a public API that utilizes those private utility classes. For example, the add method uses the linkNodeLast() method: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/LinkedHashMap.java#l217

    // internal utilities

    // 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

The Hashtable class also provides a slimmed down version of a map - a straight hash table implementation arbitrary key-value types: http://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html