MapsHomepage  « Learn Java5 « Maps

In this lesson we look at the Map hierarchy and examine four of the concrete implementations of the Map<K,V> interface. So what type of collection is a Map? Maps have unique identifiers as their keys which are mapped to a value, similar to key/value pairs in other languages. A Map doesn't allow duplicates keys so every entry within a Map must be unique. In practical terms this means that we can never have more than one element within the Map referencing the same object or more than one element within the Map referencing two objects that are considered equal. See the Checking Object Equality section from the OO Concepts - The Object Superclass section of the site for a reminder of what constitutes object equality. We can also only have a maximum of one entry within the set with a value of null.

Another feature of Map collection is how the Map<K,V> interface provides three different collection views, allowing us to view a map collection as a set of keys, a collection of values and as a set of key/value mappings.

Map Hierarchy Diagramgo to top of page Top

The diagram below is a representation of the Map hierarchy and covers the interfaces and classes we will study in this lesson. The diagram has several interfaces missing and also the java.util.WeakHashMap<K,V> and java.util.IdentityHashMap<K,V> concrete implemetations which are not covered on the site, but should help in visualisation:

map hierarchy

Map Interfaces & Classesgo to top of page Top

The table below gives a description of each interface and class within the above diagram. Click a link to go to detailed information about a particular class:

Interface/Class Description
Map<K,V>The root interface in the map hierarchy which the SortedMap<K,V> interface extends.
HashMap<K,V>Hash table based implementation of the Map<K,V> interface that implements all optional map operations and permits all elements, including null and the null key.
LinkedHashMap<K,V>Hash table and linked list implementation of the Map<K,V> interface with predictable ordering and permits all elements, including null elements.
Hashtable<K,V>Hash table implementation of the Map<K,V> interface that doesn't allow null elements or null keys.
SortedMap<K,V>Interface for sorted map elements.
TreeMap<K,V>Random access tree based implementation of the SortedMap<K,V> interface.

Map Types and Orderinggo to top of page Top

The table below extrapolates the commented information about ordering from the diagram above into a more reable tabular format:

Collection Type Ordering
MapOrderedSorted
HashMap<K,V>NoNo
LinkedHashMap<K,V>By insertion order or last access orderNo
Hashtable<K,V>NoNo
TreeMap<K,V>SortedBy natural order or bespoke order

HashMapgo to top of page Top

A HashMap is an unordered and unsorted implementation of the Map<K,V> interface that allows null values and a null key. This type of map makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time.

The hashcode of the object being inserted into the collection is used so the more efficient your override of the hashCode() method of the Object class is, the more efficient the HashMap. This also means that if you want to find out if an object exists within the map, or you want to delete an object from the map, then you need a reference to the object in question.

This type of map is a good choice when you want a collection with no duplicates and fast access and the order doesn't matter when iterating over it.

HashMap<K,V> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the HashMap<K,V> class implemented from the Map<K,V> interface:

Method Declaration Description
Used in the example below
public boolean containsKey(Object key)Returns true if this HashMap contains a mapping for the specified key.
public Set<Map.Entry<K,V>> entrySet()Returns a collection view of the mappings contained in this HashMap.
public Set<K> keySet()Returns a set view of the keys contained in this HashMap.
public V put(K key, V value)Associates the specified value with the specified key in this HashMap.
public boolean remove(Object key) Removes the mapping for this key from this HashMap if present.
public int size()Returns the number of key-value mappings in this HashMap, ie. its cardinality.
public Collection<V> values()Returns a collection view of the values contained in this HashMap.
Not used in the example below
public void clear()Removes all of the elements from this HashMap.
public Object clone()Creates and returns a shallow copy of this HashMap although the elements themselves are not cloned.
public boolean containsValue(Object value)Returns true if this HashMap maps one or more keys to the specified value.
public V get(Object key)Returns the value to which the specified key is mapped in this HashMap, or null if the map contains no mapping for the specified key.
public boolean isEmpty()Returns true if this HashMap contains no elements.
public void putAll(Map<? extends K,
                       ? extends V> m)
Copies all of the mappings from the specified map to this HashMap. The mappings will replace any mappings that this map had, for any of the keys currently in the specified HashMap.

Usage for the the first seven methods is shown in the example below. For more information on the other methods in the HashMap<K,V> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the HashMap<K,V> class which you can find by scrolling down the lower left pane and clicking on HashMap.

HashMap<K,V> Examplego to top of page Top

Lets write a simple class that creates a HashMap and uses some of the methods from the HashMap<K,V> class:


/*
  Simple class to create a HashMap and use several methods from the class 
*/
import java.util.*; // Import the java.util package

public class HashMapClass {

    public static void main (String[] args) {
        Map<String, String> hm = new HashMap<String, String>();
        hm.put("hello", "goodbye");
        hm.put("goodbye", "hello");
        hm.put("yes", "hello");
        hm.put("no", "goodbye");
        System.out.println("hash map size = " + hm.size());
        System.out.println("hash map contains: " + hm);
        hm.remove("yes");  
        System.out.println(hm.containsKey("yes"));  
        System.out.println("hash map size = " + hm.size());
        System.out.println("hash map contains: " + hm);
        // Collection-views, results differ dependant upon Map implementation
         System.out.println(hm.entrySet());
        System.out.println(hm.keySet());
        System.out.println(hm.values());
        // Use Map static nested class Entry to get a reference and change all values
        for (Map.Entry<String, String> map : hm.entrySet()) {
            map.setValue("aaa");
        }
        System.out.println(hm.entrySet());
    }
}

Save, compile and run the HashMapClass class in directory   c:\_Collections in the usual way.

Run hash map class

The above screenshot shows the results of creating and running our HashMapClass class and using several of the methods contained within the HashMap<K,V> class.

A thing of note here is how we use the Map.Entry static nested class of Map to get a reference to each map entry and change the values; the only way to obtain a reference to a map entry is from the iterator of this collection-view

LinkedHashMapsgo to top of page Top

A LinkedHashMap is a Hash table and linked list implementation of the Map<K,V> interface with predictable iteration order and differs from a HashSet by maintaintaining a doubly-linked list running through all of its elements. The linked list defines the iteration order of a LinkedHashMap by the order in which elements are inserted into the set.

This type of set is a good choice when you want a collection with no duplicates and fast access and you want to maintain an insertion order when iterating over it.

LinkedHashMap<K,V> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the LinkedHashMap<K,V> class that are inherited directly from the HashMap<K,V> class:

Method Declaration Description
public boolean containsKey(Object key)Returns true if this LinkedHashMap contains a mapping for the specified key.
public Set<Map.Entry<K,V>> entrySet()Returns a collection view of the mappings contained in this LinkedHashMap.
public Set<K> keySet()Returns a set view of the keys contained in this LinkedHashMap.
public V put(K key, V value)Associates the specified value with the specified key in this LinkedHashMap.
public boolean remove(Object key) Removes the mapping for this key from this LinkedHashMap if present.
public int size()Returns the number of key-value mappings in this LinkedHashMap, ie. its cardinality.
public Collection<V> values()Returns a collection view of the values contained in this LinkedHashMap.
Not used in the example below
public void clear()Removes all of the elements from this LinkedHashMap.
public Object clone()Creates and returns a shallow copy of this LinkedHashMap although the elements themselves are not cloned.
public boolean containsValue(Object value)Returns true if this LinkedHashMap maps one or more keys to the specified value.
public V get(Object key)Returns the value to which the specified key is mapped in this LinkedHashMap, or null if the map contains no mapping for the specified key.
public boolean isEmpty()Returns true if this LinkedHashMap contains no elements.
public void putAll(Map<? extends K,
                       ? extends V> m)
Copies all of the mappings from the specified map to this LinkedHashMap. The mappings will replace any mappings that this map had, for any of the keys currently in the specified LinkedHashMap.

Usage for the the first seven methods is shown in the example below. For more information on the methods not directly inherited fromthe HashMap<K,V> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the LinkedHashMap<K,V> class which you can find by scrolling down the lower left pane and clicking on LinkedHashMap.

LinkedHashMap<K,V> Examplego to top of page Top

Lets write a simple class that creates a LinkedHashMap and uses some of the inherited methods from the HashMap<K,V> class:


/*
  Simple class to create a LinkedHashMap and use several methods inherited from the HashMap class 
*/
import java.util.*; // Import the java.util package

public class LinkedHashMapClass {

    public static void main (String[] args) {
        Map<String, String> lhm = new LinkedHashMap<String, String>();
        lhm.put("hello", "goodbye");
        lhm.put("goodbye", "hello");
        lhm.put("yes", "hello");
        lhm.put("no", "goodbye");
        System.out.println("Linked hash map size = " + lhm.size());
        System.out.println("Linked hash map contains: " + lhm);
        lhm.remove("yes");  
        System.out.println(lhm.containsKey("yes"));  
        System.out.println("Linked hash map size = " + lhm.size());
        System.out.println("Linked hash map contains: " + lhm);
        // Collection-views, results differ dependant upon Map implementation
         System.out.println(lhm.entrySet());
        System.out.println(lhm.keySet());
        System.out.println(lhm.values());
        // Use Map static nested class Entry to get a reference and change all values
        for (Map.Entry<String, String> map : lhm.entrySet()) {
            map.setValue("aaa");
        }
        System.out.println(lhm.entrySet());
    }
}

Save, compile and run the LinkedHashMapClass class in directory   c:\_Collections in the usual way.

Run linked hash map class

The above screenshot shows the results of creating and running our LinkedHashMapClass class and using several of the methods inherited from the HashMap<K,V> class.

A thing of note here is how we use the Map.Entry static nested class of Map to get a reference to each map entry and change the values; the only way to obtain a reference to a map entry is from the iterator of this collection-view

Hashtablesgo to top of page Top

A Hashtable is an unordered and unsorted implementation of the Map<K,V> interface that doesn't allow null values or a null key. This type of map makes no guarantees over iteration order and in particular no guarantees that the iteration order will remain constant over time. Hashtable allows random access to elements and is similar to HashMap apart from being synchronized. In fact Hashtable is one of the two original collections shipped with Java, the other being Vector.

There is no sound reason since the introduction of the HashMap<K,V> class to use the Hashtable<K,V> class. If you need an HashMap to be synchronized this can be achieved using methods of the Collections class without all the overheads of using Hashtable<K,V> synchronized methods.

Hashtable<K,V> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the Hashtable<K,V> class implemented from the Map<K,V> interface used in the code example below:

Method Declaration Description
Used in the example below
public boolean containsKey(Object key)Returns true if this HashMap contains a mapping for the specified key.
public Set<Map.Entry<K,V>> entrySet()Returns a collection view of the mappings contained in this HashMap.
public Set<K> keySet()Returns a set view of the keys contained in this HashMap.
public V put(K key, V value)Associates the specified value with the specified key in this HashMap.
public boolean remove(Object key) Removes the mapping for this key from this HashMap if present.
public Collection<V> values()Returns a collection view of the values contained in this HashMap.

Usage for the the above methods is shown in the example below. For more information on the other methods in the Hashtable<K,V> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the Hashtable<K,V> class which you can find by scrolling down the lower left pane and clicking on Hashtable.

Hashtable<K,V> Examplego to top of page Top

Lets write a simple class that creates a Hashtable and uses some of the methods from the Hashtable<K,V> class:


/*
  Simple class to create a Hashtable and use several methods from the class 
*/
import java.util.*; // Import the java.util package

public class HashtableClass {

    public static void main (String[] args) {
        Map<String, String> ht = new Hashtable<String, String>();
        ht.put("hello", "goodbye");
        ht.put("goodbye", "hello");
        ht.put("yes", "hello");
        ht.put("no", "goodbye");
        System.out.println("hash table size = " + ht.size());
        System.out.println("hash table contains: " + ht);
        ht.remove("yes");  
        System.out.println(ht.containsKey("yes"));  
        System.out.println("hash table size = " + ht.size());
        System.out.println("hash table contains: " + ht);
        // Collection-views, results differ dependant upon Map implementation
         System.out.println(ht.entrySet());
        System.out.println(ht.keySet());
        System.out.println(ht.values());
        // Use Map static nested class Entry to get a reference and change all values
        for (Map.Entry<String, String> map : ht.entrySet()) {
            map.setValue("aaa");
        }
        System.out.println(ht.entrySet());
    }
}

Save, compile and run the HashtableClass class in directory   c:\_Collections in the usual way.

Run linked hash table class

The above screenshot shows the results of creating and running our HashtableClass class and using several of the methods contained within the Hashtable<K,V> class.

A thing of note here is how we use the Map.Entry static nested class of Map to get a reference to each map entry and change the values; the only way to obtain a reference to a map entry is from the iterator of this collection-view

TreeMapsgo to top of page Top

A TreeMap is a sorted implementation of the Map<K,V> interface. This type of map guarantees that the map will be sorted in ascending order, according to the natural order of the elements contained within it, or by a custom comparator/comparable, dependant upon the type of constructor used on creation.

The ordering maintained by a map whether through natural order of the elements contained within it or by a custom comparator/comparable, must be consistent with the equals() method override rules of the Object class if it is to correctly implement the Map<K,V> interface and obey the rules of equality.

This type of map is a good choice when you want a sorted collection with no duplicates with the option of custom sorting.

TreeMap<K,V> Method Overviewgo to top of page Top

The table below shows the declarations of all the methods for the TreeMap<K,V> class implemented from the Map<K,V> and SortedMap<K,V> interfaces:

Method Declaration Description
Used in the example below
public boolean containsKey(Object key)Returns true if this TreeMap contains a mapping for the specified key.
public Set<Map.Entry<K,V>> entrySet()Returns a collection view of the mappings contained in this TreeMap.
public Set<K> keySet()Returns a set view of the keys contained in this TreeMap.
public V put(K key, V value)Associates the specified value with the specified key in this TreeMap.
public boolean remove(Object key) Removes the mapping for this key from this TreeMap if present.
public int size()Returns the number of key-value mappings in this TreeMap, ie. its cardinality.
public Collection<V> values()Returns a collection view of the values contained in this TreeMap.
Not used in the example below
public void clear()Removes all of the elements from this TreeMap.
public Object clone()Creates and returns a shallow copy of this TreeMap although the elements themselves are not cloned.
public Comparator<? super K> comparator()Returns the comparator used to order this TreeMap, or null if this TreeMap uses its elements natural ordering.
public boolean containsValue(Object value)Returns true if this TreeMap maps one or more keys to the specified value.
public K firstKey()Returns the first (lowest) key currently in this TreeMap.
public V get(Object key)Returns the value to which the specified key is mapped in this TreeMap, or null if the map contains no mapping for the specified key.
public SortedMap<K,V> headMap(k toKey)Returns a view of the portion of this TreeMap whose keys are strictly less than toKey.
public K lastKey()Returns the last (highest) key currently in this TreeMap.
public void putAll(Map<? extends K,
                       ? extends V> m)
Copies all of the mappings from the specified map to this TreeMap. The mappings will replace any mappings that this map had, for any of the keys currently in the specified TreeMap.
public SortedMap<K,V> subMap(k fromKey,
                             k toKey)
Returns a view of the portion of this TreeMap whose keys range from fromKey inclusive, to toKey exclusive.
public SortedMap<K,V> tailMap(k fromKey)Returns a view of the portion of this TreeMap whose keys are greater than or equal to fromKey.

We will go use the first seven methods in in the example below. For more information on the other methods in the TreeMap<K,V> class the following link will take you to the online version of documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the TreeMap<K,V> class which you can find by scrolling down the lower left pane and clicking on TreeMap.

TreeMap<K,V> Examplego to top of page Top

Lets write a simple class that creates a TreeMap and uses some of the methods from the TreeMap<K,V> class:


/*
  Simple class to create a TreeMap and use several methods fron from the class 
*/
import java.util.*; // Import the java.util package

public class TreeMapClass {

    public static void main (String[] args) {
        Map<Object, Object> tm = new TreeMap<Object, Object>();
        tm.put("hello", "goodbye");
        tm.put("goodbye", "hello");
        tm.put("yes", "hello");
        tm.put("no", "goodbye");
        tm.put(2, "goodbye");  // Key autoboxed to Integer
        System.out.println("tree map size = " + tm.size());
        System.out.println("tree map contains: " + tm);
        tm.remove("yes");  
        System.out.println(tm.containsKey("yes"));  
        System.out.println("tree map size = " + tm.size());
        System.out.println("tree map contains: " + tm);
        // Collection-views, results differ dependant upon Map implementation
         System.out.println(tm.entrySet());
        System.out.println(tm.keySet());
        System.out.println(tm.values());
        // Use Map static nested class Entry to get a reference and change all values
        for (Map.Entry<Object, Object> map : tm.entrySet()) {
            map.setValue("aaa");
        }
        System.out.println(tm.entrySet());
    }
}

Save, compile and run the TreeMapClass class in directory   c:\_Collections in the usual way.

Run tree map class

The above screenshot shows the results of creating and running our TreeSetClass class. We get a ClassCastException and the reason for this is that if a collection is to be sorted, then the objects within it need to be mutually comparable and the String and Integer objects are not. We will talk more about sorting collection, comparables, comparators and natural order in much more detail later in the Sorting Collections lesson. For now remove the put() to the TreeMap for the Integer object and save, compile and run the TreeMapClass class again.

Run tree map class 2

The above screenshot shows the results of creating and running our TreeMapClass class and it now works.

Maps Quizgo to top of page Top

Try the quiz below to test your knowledge of this lesson

Question 1 : What do maps care about
- All maps care about uniqueness, which is achieved via their key.
Question 2 : What type of map would you use if you wanted a fast access ordered map but didn't care about sorting?
- If you wanted a fast access ordered map but didn't care about sorting you would use a LinkedHashMap.
Question 3 : Can we have a sorted and unordered map?
- If a map is sorted, as a TreeMap is, it will always be ordered by natural or comparator order.
Question 4 : What type of map would you use if you wanted fast access and didn't care about ordering?
- If you wanted a fast access set and didn't care about ordering you should use a HashMap.
Question 5 : What type of exception is raised when we try run a program with objects that are not mutually comparable in a sorted map?
- When we try to run a program with objects that are not mutually comparable in a sorted map (TreeMap) we get a ClassCastException exception.
Question 6 : What type of map would you use if you wanted it sorted?
- If you wanted a sorted map you would use a TreeMap.
Question 7 : Which static nested class of Map<K,V> allows us to get a reference to a mapping via an iterator?
- The Map.Entry static nested class allows us to get a reference to a map entry via an iterator.
Question 8 : What type of map has synchronized methods?
- Hashtable contains synchronized methods.
Status Bar Please select an answer

What's Next?

In the next lessons we look at the Utilities hierarchy and examine the java.util.Arrays and java.util.Collections classes that contains a lot of static utility methods we can use with our collections.

<<  Queues                    Utilities  >>

go to home page Java5 Tutor Homepage go to top of page Top