How To Sort A Java Map By Its VALUES and not KEYS?

Amazon A Java map or hash table is a data structure that allows you to map a key to a value. If you use a class that implements the SortedMap interface then the map automatically sorted the entries by keys during insertion.

According to Java API a SortedMap is a map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods).
Obviously you can define how sorting works by supplying a user defined Comparator class. Examples of such abound on the Internet. However a Map is meant to be sorted by its keys, NOT by its values. So here's the million dollar question: HOW DO YOU SORT A MAP BY ITS VALUES instead of KEYS?

Goal
Our goal is to start with an unsorted hash map and end with a sorted map. Many solutions online result in a sorted Set or something like that, but that's not very nice is it. If we start with a map we should end up with a map. My solution does exactly that.

Solution: Concept
The concept is easy. Here are the steps:

1. First you define a Comparator that sorts your map by its values.
2. Then you create a SortedMap and insert your data.
3. When you are done inserting, create a LinkedHashMap and copy and paste all entries from the SortedMap to the LinkedHashMap.
Next I'll walk you through an example and explain each step.

Solution: A Live Example
Let me use a live example from the source code of my award winning Men's Fashion website http://www.mensfashionforless.com/. Here's how I create the top navigation menu:

Each property (e.g. Brand, Color, etc.) contains relevant attributes (e.g. For Brand we have H&M, G By Guess, Express, etc. For Color we have Black, White, etc.) in the descending order sorted by number of the attribute's matched items. For example my database has more H&M items than G By Guess items; therefore H&M shows up above G By Guess in Brand hover drop down menu.

The purpose is obvious: I want visitors to first see attributes that has the most items.

AttributeSummary: a Custom Class to be used as Values
Each attribute (e.g. For Brand we have H&M, G By Guess, Express, etc. For Color we have Black, White, etc.) is mapped a class called AttributeSummary defined as follows:

public class AttributeSummary {
  public int itemCount;
  public String url;
  ...some other stuff
}

The key instance variable is itemCount which represents the number of items matching this attribute. This is the focus for the Comparator class which I'll define next.

Comparator Definition
My Comparator looks like the following:

static class ItemCountComparator implements Comparator {
  Map<String,AttributeSummary> base;
  public ItemCountComparator(Map<String,AttributeSummary> base) {
    this.base = base;
  }

  public int compare(Object a, Object b) {
    AttributeSummary sumA=base.get(a);
    AttributeSummary sumB=base.get(b);
    if(sumA.itemCount < sumB.itemCount){
      return 1;
    }else if(sumA.itemCount == sumB.itemCount){
      // If you return 0 here you may lose data during
      // insertion as .put() will call this function 
      // and when it returns 0 it will overwrite the 
      // original value with the new value.
      //
      // If you return -1 here then you don't lose data; 
      // however when you do .get() you'll get null even 
      // if keys match! This is because TreeMap's get()
      // will return the value for which 
      // compare(query key, any key in this treemap) 
      // returns 0, indicating a match. Since it returns
      // -1 it'll never get a match!
      //
      // SOLUTION: Return -1 here. After you are done 
      // inserting key-value entries in the TreeMap,
      // copy all entries from it to a LinkedHashMap!
      //
      return -1;
    }else{
      return -1;
    }
  }
}

As you see from the comments inline the code you should be able to understand why we need to use a SortedMap first and after we are done inserting entries we copy them from the SortedMap to a LinkedHashMap for access later!

Solution: Final Part
Now you simply follow the three steps we've mentioned earlier:

1. First you define a Comparator that sorts your map by its values.
2. Then you create a SortedMap and insert your data.
3. When you are done inserting, create a LinkedHashMap and copy and paste all entries from the SortedMap to the LinkedHashMap.
Here's sample code of following these steps:

// Map<String, AttributeSummary> mapLevel2 is the unsorted hash map

TreeMap<String, AttributeSummary> treeMap = new TreeMap<String, AttributeSummary>(new ItemCountComparator(mapLevel2));

treeMap.putAll(mapLevel2);

LinkedHashMap<String, AttributeSummary> linkedHashMap = new LinkedHashMap<String, AttributeSummary>();

linkedHashMap.putAll(treeMap);

// linkedHashMap contains sorted entries of mapLevel2 

Any questions? Let me know!