Sorting by multiple keys in nested HashMap

Question

I currently have a setup where the data structure is an ArrayList with each key containing a HashMap for each key in ArrayList. What I'm trying to do is be able to sort by key or keys within the HashMap itself. In my research, most advice seems to be to use Collections.sort(ArrayList, comparatorFunction()) and then build a custom Comparatorfunction to do the sorting, but as a complete noob as to how to build a Comparator...I don't even know where to start, much less build one that' I'm sure is not a simple setup. Anyone happen to know of some resources that would be useful to address this kind of functionality?

EDIT: Sorry some sample structure would be helpful.

if you called arrayList.get(0) and did a System.out.println on it, it would return say {town=Toronto, population=2,500,000, age=147}, what I'm trying to do is have it so I could say order the ArrayList by say population, and then age for example.

Answer 1

Usually in situations like this the job of the Comparator is to simple return the value of a compare from something else. For example, here is a Comparator that will alphabetize Fonts:

class FontAlphabetizer
implements Comparator<Font> {
    @Override
    public int compare(Font font1, Font font2) {
        return font1.getName().compareTo(font2.getName());
    }
}

That's actually pretty simple: getName returns a String and all we do is return the value of String's compareTo method.

Here it seems like what you have is an ArrayList<Map> and you want to sort the ArrayList based on a chosen value from the Map. So what you need is a Comparator<Map>. And you need to give the Comparator the key for the corresponding value that you want to sort by. This can be expressed generically like the following:

class MapValueComparator<K, V extends Comparable<V>>
implements Comparator<Map<K, V>> {
    final K key;

    MapValueComparator(K key) {
        this.key = key;
    }

    @Override
    public int compare(Map<K, V> map1, Map<K, V> map2) {
        return map1.get(key).compareTo(map2.get(key));
    }
}

That is a Comparator that compares Maps and it's specified in the declaration there that the Map's values must also be Comparable. It compares based on the value retrieved from the given key.

So for example if we have an ArrayList<Map<String, String>>, we can sort by the value from "town" like this:

static void sortByTown(List<Map<String, String>> list) {
    Collections.sort(list, new MapValueComparator<String, String>("town"));
}

The hiccup is that you say you have town=Toronto, population=2,500,000 which indicates that the population you want to sort by is a String (since presumably it's in the same map as Toronto). Comparing population as String probably isn't desired because it will sort lexicographically (50 comes after 2,500,000 because 5 comes after 2). In that case the generic version might not work because you need to take an extra step of converting the value to a number.

class PopulationComparator
implements Comparator<Map<String, String>> {
    @Override
    public int compare(Map<String, String> map1, Map<String, String> map2) {
        final Long pop1 = Long.valueOf(map1.get("population"));
        final Long pop2 = Long.valueOf(map2.get("population"));

        return pop1.compareTo(pop2);
   }
}

(And as a side note if your population contains commas you'd need to format that before parsing it to a number. You can use replaceAll("\\D", "") to remove all non digits from a String.)

This is also a case where it could be advantageous to create a class for this instead of using a Map. Then you could have the numerical fields be number types. If you had a class, the comparison would be mostly the same though: just returning a comparison of a chosen field.

Answer 2

Here is what you are looking for:

final List<Map<String, Object>> towns = new ArrayList<Map<String, Object>>();

final Map<String, Object> toronto = new HashMap<String, Object>();
toronto.put("town", "Toronto");
toronto.put("population", 2500000);
toronto.put("age", 147);
towns.add(toronto);

final Map<String, Object> ottawa = new HashMap<String, Object>();
ottawa.put("town", "Ottawa");
ottawa.put("population", 883000);
ottawa.put("age", 159);
towns.add(ottawa);

final Map<String, Object> montreal = new HashMap<String, Object>();
montreal.put("town", "Montreal");
montreal.put("population", 1600000);
montreal.put("age", 372);
towns.add(montreal);

final Map<String, Object> quebec = new HashMap<String, Object>();
quebec.put("town", "Quebec City");
quebec.put("population", 600000);
quebec.put("age", 406);
towns.add(quebec);

final Map<String, Object> vancouver = new HashMap<String, Object>();
vancouver.put("town", "Vancouver");
vancouver.put("population", 600000);
vancouver.put("age", 128);
towns.add(vancouver);

Collections.sort(towns, new Comparator<Map<String, Object>>() {
    @Override
    public int compare(final Map<String, Object> o1, final Map<String, Object> o2) {
        if (o1.get("population") instanceof Integer && o2.get("population") instanceof Integer && !((Integer)o1.get("population")).equals((Integer)o2.get("population"))) {
            return ((Integer)o1.get("population")).compareTo((Integer)o2.get("population"));
        }
        if (o1.get("age") instanceof Integer && o2.get("age") instanceof Integer) {
            return ((Integer)o1.get("age")).compareTo((Integer)o2.get("age"));
        }
        // Default if there is no population/no age, shouldn't happen.
        // TODO : do something else.
        return o1.toString().compareTo(o2.toString());
    }
});

for (final Map<String, Object> town: towns) {
    System.out.println(town.get("population")+"\t"+town.get("age")+"\t"+town.get("town"));
}

The first part of the code is just to create the ArrayList according to what you said you have, then we use a custom Comparator to sort the List, and print the result.

Here is the output:

600000  128 Vancouver
600000  406 Quebec City
883000  159 Ottawa
1600000 372 Montreal
2500000 147 Toronto

As you can see, it's sorted by population, then by age.

But, maybe the best solution would be to create an object Town, with three fields (name, population and age), and use this object instead of the HashMaps.

Answer 3

Custom Comparator can be used to define the way the objects of your class can be compared. It has the following Syntax :

 public class CustomComparator implements Comparator<MyObjectType>
 {
  public int compare(MyObjectType ob1 , MyObjectType ob2)
  {
     //code to compare the 2 objects
  }
 }

Refer to the following link for information on creating a Comparator class for custom sorting of elements in collection : link