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.
We have a requirment say 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.
Before 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.
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
Student class with roll number, name and DOB.
Before 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.
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
Student class with roll number, name and DOB.
package LinkedHashMapTest;
import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;
public class Student {
private final String id;
private final String name;
private final Date dateofbirth;
public Student(String id, String name, Date dateofbrith)
{
this.name = name;
this.id = id;
this.dateofbirth = dateofbrith;
}
private final static DateFormat df =
new SimpleDateFormat("yyyy/MM/dd");
public String toString() {
return name + " born on " + df.format(dateofbirth);
}
public String getId() {
return id;
}
public String getName() {
return name;
}
public Date getDateofbirth() {
return dateofbirth;
}
public int hashCode(){
return id.hashCode();
}
public boolean equals(Object obj)
{
if(!(obj instanceof String)) return false;
String key = (String)obj;
return id.equals(key);
}
}
Now define Interface Department.
public interface Department
{
Student[] getStudents();
}
Define ComputerScient Department with students
import java.util.Date;
public class ComputerScienceDepartment implements Department {
private final static Student[] students = {
new Student("19", "Keerthi", new Date(88, 11, 25)),
new Student("01", "Kanish", new Date(99, 07, 27)),
new Student("22", "Naresh", new Date(81, 02, 07)),
new Student("11", "Avi", new Date(82, 05, 07)),
new Student("44", "Vedh", new Date(84, 03, 10)),
new Student(new String("44"), "Vedh", new Date(84, 03, 10)),
};
@Override
public Student[] getStudents() {
return students;
}
}
Note that the students are sorted by name. We assume that the students would be retrieved in that sort order from the database. We can see the difference between the HashMaps from this example:
IdentityHashMap as name suggests uses the equality operator(==) for comparing the keys. So when you put any Key Value pair in it the Key Object is compared using == operator
import java.util.*;
public class LinkedHashMapTest {
private static void fill(Map players, Department sd) {
Student[] p = sd.getStudents();
for (int i = 0; i < p.length; i++) {
players.put(p[i].getId(), p[i]);
}
}
private static void test(Map players, Department 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) {
Department sd = new ComputerScienceDepartment();
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
Vedh born on 1984/04/10
Hanuman born on 1988/12/25
Naresh born on 1981/03/07
Kanish born on 1999/08/27
Sairam born on 1982/06/07
Testing java.util.LinkedHashMap
Hanuman born on 1988/12/25
Kanish born on 1999/08/27
Naresh born on 1981/03/07
Sairam born on 1982/06/07
Vedh born on 1984/04/10
Testing java.util.IdentityHashMap
Hanuman born on 1988/12/25
Kanish born on 1999/08/27
Vedh born on 1984/04/10
Sairam born on 1982/06/07
Naresh born on 1981/03/07
Vedh born on 1984/04/10
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.
