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>>.