Technical Tips

Return-Path: Received: from pacific-carrier-annex.mit.edu by po10.mit.edu (8.9.2/4.7) id TAA06768; Wed, 10 Jul 2002 19:02:04 -0400 (EDT) Received: from hermes.sun.com (hermes.sun.com [64.124.140.169]) by pacific-carrier-annex.mit.edu (8.9.2/8.9.2) with SMTP id TAA20081 for ; Wed, 10 Jul 2002 19:02:04 -0400 (EDT) Date: Wed, 10 Jul 2002 14:20:01 GMT-08:00 From: "JDC Tech Tips" To: alexp@mit.edu Message-Id: <180261581915954158@hermes.sun.com> Subject: JDC Tech Tips, July 9, 2002 (LinkedHashMap Class, RandomAccess Interface) Mime-Version: 1.0 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: SunMail 1.0 Technical Tips

View this issue as simple text July 9, 2002

Using the LinkedHashMap Class
The RandomAccess Interface
Correction to last month's tip on Using the CharSequence Interface

These tips were developed using java^TM 2 SDK, Standard Edition, v 1.4.

This issue of the JDC Tech Tips is written by Glen McCluskey.

Using the LinkedHashMap Class

Imagine that you are writing a Java application that makes use of a dictionary of words, for example, as part of a scheme to tabulate word frequencies. The application inserts the words into a hash table at program startup. Then as each word is used, the application looks up the word in the table, and increments its frequency count.

Here's some code that illustrates this approach:

    import java.util.*;
    
    class Counter {
        private int count;
    
        // initialize a Counter
        public Counter() {
            count = 0;
        }
    
        // increment counter
        public void bumpCount() {
            count++;
        }
    
        // retrieve the current count
        public int getCount() {
            return count;
        }
    
        // convert to a string
        public String toString() {
            return Integer.toString(count);
        }
    }
    
    public class MapDemo1 {
        static Map map = new HashMap();
        //static Map map = new LinkedHashMap();
    
        // initialize the map
        static void initMap() {
            map.put("able", new Counter());
            map.put("baker", new Counter());
            map.put("computer", new Counter());
        }
    
        // increment the count of a word
        static void useWord(String key) {
            Counter ctr = (Counter)map.get(key);
            ctr.bumpCount();
        }
    
        // display the contents of the map
        static void displayMap() {
            Iterator iter = map.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = 
                                (Map.Entry)iter.next();
                System.out.println(entry.getKey() + 
                               " " + entry.getValue());
            }
        }
    
        public static void main(String args[]) {
    
            // initialize the map
    
            initMap();
    
            // look up some words and 
            // bump their use counts
    
            useWord("able");
            useWord("baker");
            useWord("computer");
            useWord("baker");
    
            // display the contents of the map
    
            displayMap();
        }
    }

When you run this program, the result is:

     computer 1
     able 1
     baker 2

So "computer" is used one time, and "baker" two times.

These results are correct, but there's a potential problem: the words are displayed in a different order than originally inserted into the hash table. This problem is intrinsic to the way hash tables work. The ordering within such a table appears to be random.

You might not care about a scrambled ordering because the basic functioning of the hash table is not affected by the order of key/value pairs. But if you do care, is there anything you can do? One answer to this question is to use a LinkedHashMap instead of a HashMap. You can do this by changing one line in the previous example program, that is, the line that sets up the HashMap object at the beginning of the MapDemo1 class definition. In other words, comment out the line:

	static Map map = new HashMap();

Then uncomment the line:

	static Map map = new LinkedHashMap();

A LinkedHashMap is like a HashMap, except that it superimposes a linked list structure on top of the map (hash table). The list structure keeps track of the order of map entry insertions. The list is used when you iterate over the map.

After making the one-line change to MapDemo1, the output of the program is:

    able 1
    baker 2
    computer 1

The entries are now in alphabetical order because that is the order they were inserted into the hash table. A LinkedHashMap does not sort its entries. It simply keeps track of their insertion order.

Let's look at another example. Suppose that you're writing a method that needs to make a copy of a map, and then operate on the copy. In this case it might be important to preserve the order of entries in the map copy. That way, the results of your map operations are predictable. Here's a program that illustrates this idea:

    import java.util.*;
    
    public class MapDemo2 {
    
        // copy a map
        static Map copyMap(Map map) {
            return new HashMap(map);
            //return new LinkedHashMap(map);
        }
    
        public static void main(String args[]) {
    
            // create TreeMap and 
            // add some key/value pairs
    
            Map map_tree = new TreeMap();
            map_tree.put("able", "value1");
            map_tree.put("baker", "value2");
            map_tree.put("computer", "value3");
    
            // copy the map
    
            Map map_copy = copyMap(map_tree);
    
            // display the map contents
    
            Iterator iter = 
                          map_copy.keySet().iterator();
            while (iter.hasNext()) {
                System.out.println(iter.next());
            }
        }
    }

This example again uses a dictionary application. In this code, the words of the dictionary are added to a TreeMap, a class that guarantees that its entries will be sorted in ascending key order.

Suppose that you'd like to make a copy of the TreeMap, and preserve the ordering. But you don't really need all the overhead of a TreeMap structure -- implemented in J2SE^TM v 1.4 using "red-black trees". (If you're unfamiliar with red-black trees, see the book Introduction to Algorithms by Cormen, Leiserson, and Rivest.) How can you make such a copy?

The first approach in MapDemo2 uses a HashMap, that is:

   static Map copyMap(Map map) {
               return new HashMap(map);           
        }

The result is:

    computer
    able
    baker

The problem here is the same as illustrated earlier -- a hash table stores its entries in apparent random order. The entries in the TreeMap are in order, but when the entries are copied to the HashMap, the order is scrambled.

If the MapDemo2 code is changed to use a LinkedHashMap, like this:

   static Map copyMap(Map map) {
               return new LinkedHashMap(map);           
        }

then the result is:

    able
    baker
    computer

The hash table still scrambles its entries, but there's also a linked list that keeps track of the entry insertion order. This is the list that is used to iterate across the entries.

There's another way you can use a LinkedHashMap. If you create a map with "true" passed as the third argument to the constructor, like this:

    Map map = new LinkedHashMap(16, 0.75f, true);

then the map will keep track of access order instead of insertion order. Each get or put call on the map represents an access, and the iteration order is from oldest to newest. Let's look at an example:

    import java.util.*;
    
    public class MapDemo3 {
        public static void main(String args[]) {
    
            // create a map and 
            // add some key/value pairs
    
            Map map = new LinkedHashMap(
                                      16, 0.75f, true);
            map.put("able", "value1");
            map.put("baker", "value2");
            map.put("computer", "value3");
    
            // display the map contents
    
            Iterator iter1 = map.keySet().iterator();
            while (iter1.hasNext()) {
                System.out.println(iter1.next());
            }
    
            // use the map entries
    
            map.get("baker");
            map.get("able");
            map.get("computer");
    
            // display the map contents again
    
            System.out.println();
            Iterator iter2 = map.keySet().iterator();
            while (iter2.hasNext()) {
                System.out.println(iter2.next());
            }
        }
    }

When you run this program, the result is:

    able
    baker
    computer

    baker
    able
    computer

The first part of the results reflects the sequence of put calls. The put call for "able" is older than the put call for "computer". Then a sequence of get calls is made. The first get call is for "baker", followed by get calls for "able" and "computer".

Retrieving map entries in access order is quite useful in some applications, for example if you're working with a cache, and you want to flush old entries. If you place the cache entries in a LinkedHashMap, each map access will automatically update the access order. So at any time you can determine which entries are the oldest, and remove them if desired. This scheme is often called an LRU or "least recently used" cache.

For more information about LinkedHashMap, see the class description.

The RandomAccess Interface

Suppose you are writing a method that takes a List parameter. The List is composed of Integer object references, and your method computes the sum of the values in the list. Here's some code that illustrates this idea:

    import java.util.*;
    
    public class RandomDemo1 {
        static final int N = 25000;
    
        // create a List of Integer objects
        static void buildList(List lst) {
            for (int i = 1; i <= N; i++) {
                lst.add(new Integer(i));
            }
        }
    
        // sum a List of Integer objects, using get()
        static long sumList(List lst) {
            long sum = 0;
            for (int i = 0, size = lst.size(); 
                                       i < size; i++) {
                Integer iobj = (Integer)lst.get(i);
                sum += iobj.intValue();
            }
            return sum;
        }
    
        // sum a List of Integer objects,
        // using get() or iterators
        static long newsumList(List lst) {
            long sum = 0;
            if (lst instanceof RandomAccess) {
                for (int i = 0, size = lst.size(); 
                                       i < size; i++) {
                    Integer iobj = (Integer)lst.get(i);
                    sum += iobj.intValue();
                }
            }
            else {
                for (Iterator i = lst.iterator(); 
                                       i.hasNext(); ) {
                    Integer iobj = (Integer)i.next();
                    sum += iobj.intValue();
                }
            }
            return sum;
        }
    
        public static void main(String args[]) {
    
            // create a List as an ArrayList
    
            List lst_array = new ArrayList();
            buildList(lst_array);
    
            // sum the contents of the list
    
            long start_time_array = 
                            System.currentTimeMillis();
            long sum_array = sumList(lst_array);
    
            // display the sum and elapsed time
    
            System.out.println(
                    "sum of ArrayList = " + sum_array);
            System.out.println("sum time = " +
                (System.currentTimeMillis() - 
                                    start_time_array));
    
            // create a List as a LinkedList
    
            List lst_link = new LinkedList();
            buildList(lst_link);
    
            // sum the contents of the list
    
            long start_time_link = 
                            System.currentTimeMillis();
            long sum_link = sumList(lst_link);
    
            // display the sum and elapsed time
    
            System.out.println(
                    "sum of LinkedList = " + sum_link);
            System.out.println("sum time = " +
                (System.currentTimeMillis() - 
                                     start_time_link));
        }
    }

The sumList method does the obvious thing. It obtains the size of the list. Then it calls the get method to retrieve each list element in turn, and extracts the integer value.

The results of running the program look something like this:

    sum of ArrayList = 312512500
    sum time = 16
    sum of LinkedList = 312512500
    sum time = 12969

Notice the sum time for the ArrayList as compared to that for the LinkedList. The sumList method works well for the ArrayList, but for the LinkedList, the performance is nearly a thousand times slower.

What is wrong? The problem is that it's a bad choice to use the get method for a linked list. That's because there is no fast way to access a random element in a linked list. For example, if you want to access the 379th element of such a list, you need to start at the beginning or end of the list, and then iterate to the proper element. There's no alternative approach. By contrast, an ArrayList is backed by a Java array, so accessing a particular array element is inexpensive.

This difference in cost doesn't prove that ArrayList is always a better choice than LinkedList. It depends on what operations are done on the lists. For example, inserting in the middle of an ArrayList is expensive, because elements with indices above the insertion point must be moved.

If you change the calls of sumList to newsumList in the RandomDemo1 example, the behavior changes dramatically. You should see results that look something like this:

    sum of ArrayList = 312512500
    sum time = 16
    sum of LinkedList = 312512500
    sum time = 16

How is newsumList different than sumList? It checks whether the passed-in List object is an instance of the RandomAccess interface, that is, whether the class of the object implements the RandomAccess interface. RandomAccess is an empty marker interface. It is used to give an implementing class a specific property.

In this particular case, the desired property is that a List implementation supports fast random access. In J2SE v 1.4, ArrayList and Vector implement the RandomAccess interface. LinkedList does not. If a List implementation does not implement RandomAccess, then it's better to traverse the list using iterators instead of using get method calls.

You can use the RandomAccess marker interface both in List implementation classes that you define, and in programming with existing List classes such as ArrayList, LinkedList, and Vector.

Another example where RandomAccess is used is in the reverse(List) method in the java.util.Collections class. For small lists and for list objects whose class implements RandomAccess, a loop involving Collections.swap is used. The swap method is based on get/put. By contrast, for larger lists that do not support fast random access, a scheme based on two iterators is used. Here, one iterator goes forward through the list, and the other goes backward from the end of the list.

It pays to be cautious in your use of List implementations such as ArrayList and LinkedList, given the big performance tradeoffs. The RandomAccess interface can help you in writing code that will work efficiently for any type of List.

For more information about the RandomAccess interface, see the interface description.

Correction to last month's tip on Using the CharSequence Interface

In the June 4, 2002 Tech Tips, there was a tip about the use of the CharSequence interface. The CSDemo2 program in that tip demonstrated a class called CharArrayWrapper for wrapping char arrays. Two lines in that class need to be changed as follows:

Change:

    return vec[index];

to:

    return vec[index + off];

and:

    return new CharArrayWrapper(
                              vec, start, end - start);

to:

    return new CharArrayWrapper(
                        vec, start + off, end - start);

In casual use of the CharArrayWrapper class, "off" will be 0, and this change will have no effect. But if subSequence() is called, and then a further operation is applied to the subsequence, the original code will not work. Here's a test case that fails with the original code:

    if (cs.subSequence(2, 4).charAt(0) != 'c')
        System.out.println("*** error ***");

IMPORTANT: Please read our Terms of Use, Privacy, and Licensing policies:
http://www.sun.com/share/text/termsofuse.html
http://www.sun.com/privacy/
http://developer.java.sun.com/berkeley_license.html

Comments? Send your feedback on the Java^TM Developer Technical Tips to: jdc-webmaster@sun.com

Go to the subscriptions page to subscribe or unsubscribe to this newsletter.

ARCHIVES: You'll find the Java Developer Connection Technical Tips archives at:
http://developer.java.sun.com/developer/JDCTechTips/

Sun, Sun Microsystems, Java, Java Developer Connection, and J2SE are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.

Please send me newsletters in text.
Please unsubscribe me from this newsletter.