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. HashMap.java Link: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/HashMap.java

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. TreeMap.java Link: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/TreeMap.java

LinkedHashMap

There is also a LinkedHashMap, which implements a Hash Map using a linked structure: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/LinkedHashMap.java

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

Maps in Java

From charlesreid1

Contents