J2SE 1.4 introduces two new implementations to the Java Collections Framework, LinkedHashSet and LinkedHashMap. The advantage of these additions is that a hashed collection now maintains two paths through its elements. In addition to the standard hashing relationship, there is now a linked list that traverses through the collection. Under normal circumstances, this new second path would follow the insertion order, meaning that the iterator for the collection will return the elements in their insertion order (not in the order that their hashing codes have them incorporated into the collection), but LinkedHashMap supports a second ordering option: maintaining the linked list in access order instead of insertion order.

Let's take a look at how these new classes work.

Getting started

Getting started with these new classes is easy. Just import the java.util package and find a set of items to work with. For our example, we'll use calendar months. We'll use with the English months when working with the set, and English and Italian names when working with the map.

import java.util.*;
public class OrderedAccess {
  public static void main(String args[]) {
    String months[] = 
      new DateFormatSymbols().getMonths();
    String italianMonths[] = 
      new DateFormatSymbols(Locale.ITALIAN).getMonths();
  }
}

I'll assume you already know the names and order of the months in English. For those of you who aren't familiar with the Italian month names, they are: Gennaio, Febbraio, Marzo, Aprile, Maggio, Giugno, Luglio, Agosto, Settembre, Ottobre, Novembre, and Dicembre, though for some reason getMonths() returns the names not capitalized.

Back to top

Using the new HashSet

The LinkedHashSet is a subclass of the basic HashSet class. Thus, everything you can do with HashSet, you can do with LinkedHashSet. There are no new methods in the class. All you get are the four constructors:

• LinkedHashSet()
• LinkedHashSet(Collection c)
• LinkedHashSet(int initialCapacity)
• LinkedHashSet(int initialCapacity, float loadFactor)

To add elements to a set, we can either call add() for each element, or create a Collection and pass that to the constructor. Because we have the elements in an array, the simplest mechanism is to use Arrays.asList(), which will return the array wrapped into a List, maintaining the order from the original array. By passing the list on to the constructor, we can easily add the same list to both a LinkedHashSet and a plain HashSet.

  List list = Arrays.asList(months);
  Set orderedSet = new LinkedHashSet(list);
  Set unorderedSet = new HashSet(list);

After filling up our sets, we can examine their elements to see if the linked set maintained its elements in insertion order, and then compare the results to the standard hash set. You can either iterate through each set manually, through its iterator(), or just call the toString() method (implicitly), which essentially just does that for us.

  System.out.println("Ordered:   " + orderedSet);
  System.out.println("Unordered: " + unorderedSet);

The ordered set displays as follows:

Ordered:   [January, February, March, April, May, June, July, August, 
  September, October, November, December, ]

While the unordered set displays as:

Unordered: [March, April, November, October, January, July, September, 
  February, December, May, June, August, ]

Back to top

Using the new HashMap

The LinkedHashMap essentially works the same way as the LinkedHashSet, but you need a key and a value for each element. It also subclasses from the original class, HashMap in this case, but has five constructors now:

• LinkedHashMap()
• LinkedHashMap(int initialCapacity)
• LinkedHashMap(int initialCapacity, float loadFactor)
• LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
• LinkedHashMap(Map)

The additional constructor deals with the access order option. Think of a false access order as the default, where you must pass in a true to have the list in access order; that is, the head of the map is the least recently used map entry.

The nice thing about a LinkedHashMap over a regular HashMap is that iteration times are not affected by the map's capacity. Choosing a large capacity does not have any effect on iteration traversal times with a LinkedHashMap, where it does affect performance on a regular HashMap.

Adding elements to the map is a little more involved than adding to a set, only because we have to put() each pair of elements separately. There's nothing special in the following code, just that we're looping through the month names, instead of just passing in a Map to the constructor.

  Map orderedMap = new LinkedHashMap();
  Map unorderedMap = new HashMap();
  for (int i=0, n=months.length; i < n; i++) {
    orderedMap.put(months[i], italianMonths[i]);
    unorderedMap.put(months[i], italianMonths[i]);
  }

Thankfully, like sets, you can just call the toString() method of the map to get the map entries in insertion order. This will return each key-value pair as key=value.

  System.out.println("Ordered:   " + orderedMap);
  System.out.println("Unordered: " + unorderedMap);

The ordered map displays as follows:

Ordered:   {January=gennaio, February=febbraio, March=marzo, April=aprile, 
  May=maggio, June=giugno, July=luglio, August=agosto, September=settembre, 
  October=ottobre, November=novembre, December=dicembre, =}

While the unordered map displays as:

Unordered: {August=agosto, July=luglio, November=novembre, June=giugno, 
  October=ottobre, April=aprile, May=maggio, March=marzo, January=gennaio,
  February=febbraio, =, December=dicembre, September=settembre}

To check for yourself, you can iterate. All the iterators are insertion-order aware, so when you received the values iterator (values()), you can walk through the values in insertion order like this:

  Collection values = orderedMap.values();
  for (Iterator i = values.iterator(); i.hasNext(); 
    System.out.println(i.next()));

to display this:

gennaio
febbraio
marzo
aprile
maggio
giugno
luglio
agosto
settembre
ottobre
novembre
dicembre

Back to top

Visiting in access order

The last aspect of the new classes we'll examine is the access order option for the LinkedHashMap. Passing true into the LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) constructor allows you to keep the linked list for the map in access order, from least recently used to most recently used. In other words, new items are added to the end, and map lookups move items to the end of the linked list. This last point is important. Because the typical read-access of a map changes the order, if multiple threads could be reading from the map, you should synchronize access.

To demonstrate, we can look up a few months and print the new order:

  Map accessorderedMap = 
    new LinkedHashMap(20, .80f, true);
  for (int i=0, n=months.length; i < n; i++) {
    accessorderedMap.put(months[i], italianMonths[i]);
  }
  accessorderedMap.get("June");
  accessorderedMap.get("April");
  accessorderedMap.get("February");
  System.out.println(accessorderedMap);

Because we accessed three months, they will be moved to the end of the list, with February last and April before June:

{January=gennaio, March=marzo, May=maggio, July=luglio, August=agosto, 
    September=settembre, October=ottobre, November=novembre, 
    December=dicembre, =, June=giugno, April=aprile, February=febbraio}

Note: You'll notice an extra element in the linked map. The = is an extra entry that gets returned by getMethods(). For some reason getMonths() returns 13 months, not 12, where the last one has no name. For the same reason there is a comma with no last element in the linked set example.

Another note: The 1.4 beta 2 version of LinkedHashMap adds a protected removeEldestEntry() method. Subclasses can have this method return true if the oldest node should be removed, for instance to ensure a map doesn't get over n elements.

Back to top

Complete example

Here's the complete example source.

import java.util.*;
import java.text.*;
public class OrderedAccess {
  public static void main(String args[]) {
    String months[] = 
      new DateFormatSymbols().getMonths();
    String italianMonths[] = 
      new DateFormatSymbols(Locale.ITALIAN).getMonths();
    List list = Arrays.asList(months);
    Set orderedSet = new LinkedHashSet(list);
    Set unorderedSet = new HashSet(list);
    System.out.println("Ordered:   " + orderedSet);
    System.out.println("Unordered: " + unorderedSet);
    Map orderedMap = new LinkedHashMap();
    Map unorderedMap = new HashMap();
    for (int i=0, n=months.length; i < n; i++) {
      orderedMap.put(months[i], italianMonths[i]);
      unorderedMap.put(months[i], italianMonths[i]);
    }
    System.out.println("Ordered:   " + orderedMap);
    System.out.println("Unordered: " + unorderedMap);
    Collection values = orderedMap.values();
    for (Iterator i = values.iterator(); i.hasNext(); 
      System.out.println(i.next()));
    Map accessorderedMap = 
      new LinkedHashMap(20, .80f, true);
    for (int i=0, n=months.length; i < n; i++) {
      accessorderedMap.put(months[i], italianMonths[i]);
    }
    accessorderedMap.get("June");
    accessorderedMap.get("April");
    accessorderedMap.get("February");
    System.out.println(accessorderedMap);
  }
}

Back to top

Download

Information about download methods

Resources

• Learn more about the changes to the Collections Framework in the 1.4 release.
  
  
• Learn about the LinkedHashSet with its javadoc.
  
  
• Learn about the LinkedHashMap with its javadoc.
  
  
• The Java Collections Framework tutorial (developerWorks, June 2001), also by John Zukowski, offers an in-depth, hands-on examination of the JCF.
  
  
• Read the complete collection of Merlin tips by John Zukowski.
  
  
• Find more Java resources on the developerWorks Java technology zone.
  
  

About the author

John Zukowski conducts strategic Java consulting with JZ Ventures, Inc. and serves as the resident guru for a number of jGuru's community-driven Java FAQs. His latest books are Java Collections and Definitive Guide to Swing for Java 2 (2nd ed) from Apress. Contact John at jaz@zukowski.net.

Rate this article

Comments

Back to top

Table of contents

• Getting started
• Using the new HashSet
• Using the new HashMap
• Visiting in access order
• Complete example
• Download
• Resources
• About the author
• Comments

Local resources

• IBM Innovation Center - Austin, TX
• IBM Innovation Center - Chicago, IL
• IBM Innovation Center - Dallas, TX
• IBM Innovation Center - San Mateo, CA
• IBM Innovation Center - Waltham, MA
• Technical Briefings in North America

Dig deeper into Java on developerWorks

Discover knowledge paths

Skill-building guides for Java, Linux, open source, cloud, business analytics, and more.

Special offers