Sorting LinkedHashMap by value

Question

How can you sort a LinkedHashMap using the value ?

Is there a way to insert entries into a LinkedHashMap so that they are inserted in order based on their value ?

Answer 1

How can you sort a LinkedHashMap using the value?

LinkedHashMap is not sorted, it is ordered by order of insertion.

If your goal is to reorder the Map, you might do something like

static <K, V> void orderByValue(
        LinkedHashMap<K, V> m, final Comparator<? super V> c) {
    List<Map.Entry<K, V>> entries = new ArrayList<>(m.entrySet());

    Collections.sort(entries, new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> lhs, Map.Entry<K, V> rhs) {
            return c.compare(lhs.getValue(), rhs.getValue());
        }
    });

    m.clear();
    for(Map.Entry<K, V> e : entries) {
        m.put(e.getKey(), e.getValue());
    }
}

We put all the entries in a List, sort the List, then put the entries back in the Map in the new order.

Here's a Java 8 translation for those inclined:

static <K, V> void orderByValue(
        LinkedHashMap<K, V> m, Comparator<? super V> c) {
    List<Map.Entry<K, V>> entries = new ArrayList<>(m.entrySet());
    m.clear();
    entries.stream()
        .sorted(Comparator.comparing(Map.Entry::getValue, c))
        .forEachOrdered(e -> m.put(e.getKey(), e.getValue()));
}

(Which, out of curiosity, can be condensed to, although it is less efficient):

static <K, V> void orderByValue(
        LinkedHashMap<K, V> m, Comparator<? super V> c) {
    new ArrayList<>(m.keySet()).stream()
        .sorted(Comparator.comparing(m::get, c))
        .forEachOrdered(k -> m.put(k, m.remove(k)));
}

Is there a way to insert entries into a LinkedHashMap so that they are inserted in order based on their value?

No. See above. LinkedHashMap is not sorted.

If your goal is to keep the Map sorted, you need to use a TreeMap; however there are problems with doing so. Entries in the Map need to have unique values. See here and here.

Answer 2

I think the best way to sort a LinkedHashMap by value is to write a comparator that compares two Map.Entry<K,V> objects by value, then

Map.Entry<K,V>[] entries = (Map.Entry<K,V>[])map.entrySet().toArray();
Arrays.sort(entries, comparator);

The comparator would look something like

Comparator<Map.Entry<K,V>> comparator = new Comparator<Map.Entry<K,V>>() {
    @Override
    public int compare(Map.Entry<K,V> o1, Map.Entry<K,V> o2) {
        return o1.getValue().compareTo(o2.getValue());
    }
};

Basically, it's the obvious thing: create an array of all the key/value pairs in the map, and then sort it. NOTE: I haven't tested this.

As for the second question: this would require a special data structure that maintains the values in order. When you insert an element, it would set up the hash table and maintain a doubly-linked list of the elements in insertion order and set up some sort of AVL tree to keep the values in order like TreeSet. I don't think Java defines a class like this, but maybe there's one in a third-party library. It might be easiest to maintain two separate structures, a LinkedHashMap<K,V> and a TreeSet<Map.Entry<K,V>>.

Answer 3

Like the answer before me suggested a LinkedHashMap is not sorted it only holds the insertion order. You have to manually create your comparator.

now the question is what do you what to sort the Map by ? By an integer key...

Here is a example: (Tree Map)

Default Compare

           // Create a hash map
          TreeMap tm = new TreeMap();
          // Put elements to the map
          tm.put("person1", new Double(1));
          tm.put("person2", new Double(2));
          tm.put("person3", new Double(3));
          tm.put("person4", new Double(4));
          tm.put("person5", new Double(5));
          
          // Get a set of the entries
          Set set = tm.entrySet();
          // Get an iterator
          Iterator i = set.iterator();
          // Display elements
          while(i.hasNext()) {
             Map.Entry me = (Map.Entry)i.next();
             System.out.print(me.getKey() + ": ");
             System.out.println(me.getValue());
          }
          System.out.println();
          
          // Deposit 1000 into person5's account
          double balance = ((Double)tm.get("person5")).doubleValue();
          tm.put("person5", new Double(balance + 1000));
          System.out.println("person5's new balance: " +
          tm.get("person5"));

This tree will sort in the natural order of the keys. i.e. person1 threw person5

    person1: 1.00
    person2: 2.00
    person3: 3.00
    person4: 4.00
    person5: 5.00
    person5's new balance: 1005.00

Use a custom comparator:

public class MyTMCompUserDefine {
 
    public static void main(String a[]){
        //By using name comparator (String comparison)
        TreeMap<Empl,String> tm = new TreeMap<Empl, String>(new MyNameComp());
        tm.put(new Empl("Ram",3000), "RAM");
        tm.put(new Empl("John",6000), "JOHN");
        tm.put(new Empl("Crish",2000), "CRISH");
        tm.put(new Empl("Tom",2400), "TOM");
        Set<Empl> keys = tm.keySet();
        for(Empl key:keys){
            System.out.println(key+" ==> "+tm.get(key));
        }
        System.out.println("===================================");
        //By using salary comparator (int comparison)
        TreeMap<Empl,String> trmap = new TreeMap<Empl, String>(new MySalaryComp());
        trmap.put(new Empl("Ram",3000), "RAM");
        trmap.put(new Empl("John",6000), "JOHN");
        trmap.put(new Empl("Crish",2000), "CRISH");
        trmap.put(new Empl("Tom",2400), "TOM");
        Set<Empl> ks = trmap.keySet();
        for(Empl key:ks){
            System.out.println(key+" ==> "+trmap.get(key));
        }
    }
}
 
class MyNameComp implements Comparator<Empl>{
 
    @Override
    public int compare(Empl e1, Empl e2) {
        return e1.getName().compareTo(e2.getName());
    }
}
 
class MySalaryComp implements Comparator<Empl>{
 
    @Override
    public int compare(Empl e1, Empl e2) {
        if(e1.getSalary() > e2.getSalary()){
            return 1;
        } else {
            return -1;
        }
    }
}
 
class Empl{
     
    private String name;
    private int salary;
     
    public Empl(String n, int s){
        this.name = n;
        this.salary = s;
    }
     
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getSalary() {
        return salary;
    }
    public void setSalary(int salary) {
        this.salary = salary;
    }
    public String toString(){
        return "Name: "+this.name+"-- Salary: "+this.salary;
    }
}

Output:
Name: Crish-- Salary: 2000 ==> CRISH
Name: John-- Salary: 6000 ==> JOHN
Name: Ram-- Salary: 3000 ==> RAM
Name: Tom-- Salary: 2400 ==> TOM
===================================
Name: Crish-- Salary: 2000 ==> CRISH
Name: Tom-- Salary: 2400 ==> TOM
Name: Ram-- Salary: 3000 ==> RAM
Name: John-- Salary: 6000 ==> JOHN