073LinkedHashMap is Actually Quite Useful

Author: Dr. Heinz M. KabutzDate: 2003-06-22Java Version: 1.4Category: Language

Abstract: LinkedHashMap gives us a map that retains the order in which elements were inserted. This can help us maintain a dictionary of key-value pairs in the same order as they were read in.

Welcome to the 73rd edition of The Java(tm) Specialists' Newsletter. Five years ago today, I was holding my newly-released son Maximilian Francis in my arms.

After last week's newsletter, some readers remarked that Dilbert could also be received via email. I knew that, but my way is more interesting than subscribing to a mailing list and has far greater applications than just "Dilbert". Another reader suggested that we should always read the "terms of use" of websites to ensure we do not inadvertantly violate a law.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

LinkedHashMap is Actually Quite Useful

Did you know that the JDK 1.4.x contained a LinkedHashMap and a LinkedHashSet?

I love catching people off-guard. I love it more than being caught off-guard. I was speaking to my pastor the other day and told him: "Bruce, you should put a wireless network in your house so that you can communicate with your office downstairs." Bruce had this look on his face of "Yeah, pull the other leg, I won't fall for you again!" That is a problem that wisecracks experience: even useful comments sound like jokes :-(

This is similar to my experience with programmers when I mention the LinkedHashMap. It usually results in a look of puzzlement: "Should I believe that such a thing exists? Or is Heinz having me on again?"

Granted, the term LinkedHashMap sounds like something I would invent, like the IdentityWeakSoftHardPhantomHashLinkMap that I spoke about in an earlier newsletter.

What is a LinkedHashMap?

A LinkedHashMap is a combination of hash table and linked list. It has a predictable iteration order (a la linked list), yet the retrieval speed is that of a HashMap. The order of the iteration is determined by the insertion order, so you will get the key/values back in the order that they were added to this Map. You have to be a bit careful here, since re-inserting a key does not change the original order.

Let us imagine that we want to retrieve rows from a database table and convert these rows to Java Objects. Let us also imagine we are not using JDO. We need the elements in some order, and we need to search on keys quickly.

Pre JDK 1.4, I would probably have made the objects Comparable and inserted them into a TreeMap. TreeMap works with a type of balanced binary tree, so the lookup would be O(log2n). If we have 1024 elements, it will take at most ten lookups. This is worse than a HashMap with a good hash function, which should only take one lookup. Keeping the tree balanced is expensive since it involves shuffling the nodes around whenever one side of the tree becomes too deep. Inserting the elements into a TreeMap is probably more expensive than sorting in your database, since the database is optimised for such things. [Balanced binary trees make excellent second-year computer science assignments. Mine did not work, but then neither did my tutor, so he gave me full marks.]

With the LinkedHashMap we get the best of both worlds. We can let the database do the sorting, retrieve the rows and insert them into the LinkedHashMap. This way we can retrieve them quickly via the HashMap mechanism, but we can still iterate through them in the sorted order.

To illustrate, let us use a domain that nerds know little about: Sport. We start with a Player, which we term as someone professionally engaged in a particular sporting activity. He makes his money from running around, instead of pushing a mouse around a mousepad. My father-in-law was a professional sportsman and even at sixty is fitter than me. My teenage brothers-in-law are world-ranked gravity racers. I was excused from physical education classes in school.

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
 * Super athlete who earns money running around and styling
 * his hair nicely.
 */
public class Player {
  private final Key key;
  private final String name;
  private final Date dateOfBirth;
  public Player(String id, String name, Date dob) {
    this.key = new Key(id);
    this.name = name;
    this.dateOfBirth = dob;
  }
  public Key getKey() {
    return key;
  }
  public String getName() {
    return name;
  }
  public Date getDateOfBirth() {
    return dateOfBirth;
  }
  private static final DateFormat df = 
    new SimpleDateFormat("yyyy/MM/dd");
  public String toString() {
    return name + " born on " + df.format(dateOfBirth);
  }
  public static final class Key {
    private final String id;
    public Key(String id) {
      if (id == null) {
        throw new IllegalArgumentException();
      }
      this.id = id;
    }
    public int hashCode() {
      return id.hashCode();
    }
    public boolean equals(Object obj) {
      if (!(obj instanceof Key)) return false;
      return id.equals(((Key) obj).id);
    }
  }
}

We now define a SportDatabase interface:

/**
 * This represents some database that retrieves the Players from
 * a backend database.
 */
public interface SportDatabase {
  Player[] getPlayers();
}

In South Africa, we put on white clothes and stand on a big field hoping for a ball to come our way. The complaining outfielders kept on "chirping", which led to the sport being called "Cricket".

import java.util.Date;
/**
 * Cricket is a boring sport that is popular in countries
 * previously occupied by the British Empire.  Like warm
 * beer, the taste for cricket has to be acquired.  It is
 * probably more of a spectator sport than unterwater hockey, 
 * but not by much.
 * 
 * South Africa does officially have a cricket team.
 */
public class CricketDatabase implements SportDatabase {
  private static final Player[] p =  {
    new Player("12341", "Boeta Dippenaar", new Date(77, 5, 14)),
    new Player("23432", "Gary Kirsten", new Date(67, 10, 23)),
    new Player("23411", "Graeme Smith", new Date(81, 1, 1)),
    new Player("55221", "Jonty Rhodes", new Date(69, 6, 27)),
    new Player("61234", "Monde Zondeki", new Date(82, 6, 25)),
    new Player("23415", "Paul Adams", new Date(77, 0, 20)),
  };
  public Player[] getPlayers() {
    return p;
  }
}

Note that the players are sorted by name. We assume that the players would be retrieved in that sort order from the database. We can see the difference between the HashMaps from this example:

import java.util.*;
public class LinkedHashMapTest {
  private static void fill(Map players, SportDatabase sd) {
    Player[] p = sd.getPlayers();
    for (int i = 0; i < p.length; i++) {
      players.put(p[i].getKey(), p[i]);
    }
  }  
  private static void test(Map players, SportDatabase sd) {
    System.out.println("Testing " + players.getClass().getName());
    fill(players, sd);
    for (Iterator it = players.values().iterator(); it.hasNext();) {
      System.out.println(it.next());
    }
    System.out.println();
  }  
  public static void main(String[] args) {
    SportDatabase sd = new CricketDatabase();
    test(new HashMap(), sd);
    test(new LinkedHashMap(), sd);
    test(new IdentityHashMap(), sd);
  }
}

When we run this code, we get the following output:

Testing java.util.HashMap
Jonty Rhodes born on 1969/07/27
Graeme Smith born on 1981/02/01
Paul Adams born on 1977/01/20
Monde Zondeki born on 1982/07/25
Gary Kirsten born on 1967/11/23
Boeta Dippenaar born on 1977/06/14

Testing java.util.LinkedHashMap
Boeta Dippenaar born on 1977/06/14
Gary Kirsten born on 1967/11/23
Graeme Smith born on 1981/02/01
Jonty Rhodes born on 1969/07/27
Monde Zondeki born on 1982/07/25
Paul Adams born on 1977/01/20

Testing java.util.IdentityHashMap
Paul Adams born on 1977/01/20
Jonty Rhodes born on 1969/07/27
Gary Kirsten born on 1967/11/23
Graeme Smith born on 1981/02/01
Monde Zondeki born on 1982/07/25
Boeta Dippenaar born on 1977/06/14

LRU Cache

Another application for the LinkedHashMap is in building LRU caches. One of the constructors allows us to specify that we use access order instead of insert order. The order is from least-recently accessed to most-recently. You can override the removeEldestEntry(Map.Entry) method to impose a policy for automatically removing stale when new mappings are added to the map. The implementation of this LRUCache is left as an exercise to the reader, or just look at the IdentityWeakSoftHardPhantomHashLinkMap from our earlier newsletter ;-)

Kind regards

Heinz

P.S. In case you thought I was kidding about my brothers-in-law being world-ranked street lugers and skateboarders, search for Kytides on the gravity-sports world rankings.

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive