How to sort a complex HashMap structure in Java?

Question

I'm developing a frequency map for counting the frequency of lemmata in a text, while saving their flexions. My data structure looks like this:

HashMap<List<String>, HashMap<List<String>, Long>> frequencyMap = ... ;

The first list contains a sequence of lemmata, the second one contains the flexions of the words and their frequency. Is there a way to sort this data structure by the frequency counts?

Or would you suggest another data structure to store those values, which is e.g. easier to sort.

Any help is appreciated.

Can you further clarify how do you want it to be sorted? I'm not familiar with the concept of `lemmata` and `flexion`. — Adam Arold, May 26 '14 at 15:02
maybe this topic can help you a bit: [here](http://stackoverflow.com/questions/8725387/why-there-is-no-sortedlist-in-java) — DCarochoC, May 26 '14 at 15:03
Maybe it's better to define these concept (lemmata, etc..) in a class, and expose methods that make clear what you want to do with that class, than is just to implements the `Comparable` interface on what you want to sort ...and the code will be more clear :) — rascio, May 26 '14 at 15:04
`HashMap` makes no guarantees as to the order of the map. `TreeMap` does. Secondly, can you provide an example input and expected output? — emesx, May 26 '14 at 15:04
@AdamArold: `Lemmata` and `flexions` are strings, which describe my sentences. I need my map sorted by the frequency, which seems to be tricky, because the frequency is contained in the inner `HashMap`. I thought of converting it to a `List`, while generating an object of each outer `HashMap` entry. @user979349: I read, that `TreeMap` only provides a total ordering on its keys. — JanFo, May 26 '14 at 15:07
according to this http://stackoverflow.com/questions/12947088/java-treemap-comparator it is not possible to sort a TreeMap by value. Maybe take a look at this post. Also comparators are used there, I think they will help you — wastl, May 26 '14 at 15:15
You just want to sort each `(List, HashMap)` pair by some value derived from the hashmap? Or do you need to do something more with the data, like break the list down into individual strings, or put the elements of each hashmap into some order? — Kenster, May 26 '14 at 15:44

score 0 · Answer 1 · answered May 26 '14 at 15:17

0

List sortedKeys=new ArrayList(yourMap.keySet());
Collections.sort(sortedKeys);

Try this !

answered May 26 '14 at 15:17

Lockon

13
5

score 0 · Answer 2 · answered May 26 '14 at 15:30

The data structure that you have is not easily sortable because you can have a set of keys for every list of values.

For example, you would have a list of strings that match to the map of list of strings and values, where all these values could reference different keys.

Try first simplifying the data structure. Express it in term of . Then use a TreeMap or a Collections.sort, as @Lockon described.

For a TreeMap example: http://tutorialswithexamples.com/java-treemap-tutorial-and-examples/

score 0 · Answer 3 · answered May 26 '14 at 15:32

There are two way of sorting this map. Sorting inner map based on Long value. Or sorting the outer map based on Long value in inner map. In latter case the sorting will compare only the value of first item in inner map. I assume this is your requrement. Then you can use the below method

private Map<List<String>, HashMap<List<String>, Long>> sortMap(
        Map<List<String>, HashMap<List<String>, Long>> unsortedMap) {

    List<Entry<List<String>, HashMap<List<String>, Long>>> list = new LinkedList<Entry<List<String>, HashMap<List<String>, Long>>>(
            unsortedMap.entrySet());

    Collections.sort(list,
            new Comparator<Entry<List<String>, HashMap<List<String>, Long>>>() {

                @Override
                public int compare(
                        Entry<List<String>, HashMap<List<String>, Long>> o1,
                        Entry<List<String>, HashMap<List<String>, Long>> o2) {

                    return o1.getValue().entrySet().iterator().next().getValue().compareTo(o2.getValue().entrySet().iterator().next().getValue());
                }
            });

    Map<List<String>, HashMap<List<String>, Long>> sortedMap = new LinkedHashMap<List<String>, HashMap<List<String>, Long>>();
    for(Entry<List<String>, HashMap<List<String>, Long>> item : list){
        sortedMap.put(item.getKey(), item.getValue());
    }
    return sortedMap;
}

score 0 · Answer 4 · answered May 26 '14 at 17:28

HashMaps don't support ordering the elements, so you have to start by copying your data into a data structure that permits sorting:

ArrayList<Map.Entry<List<String>, HashMap<List<String>, Long>> items =
    new ArrayList<>(frequencyMap.entrySet());

Now, write a Comparator that comparies Map.Entry values:

class FrequencyComparator
implements Comparator<Map.Entry<List<String>, HashMap<List<String>, Long>> {
    public int compare(Map.Entry<List<String>, HashMap<List<String>, Long>> a,
                       Map.Entry<List<String>, HashMap<List<String>, Long>> b) {
        // code to get a's and b's frequency counts and compare them
    }
}

Now, you can sort the array:

Collections.sort(items, new FrequencyComparator());

If it's expensive to get the frequency count for an item, then you could calculate it once for each item and then sort data structures containing these precalculated values:

class FrequencySortHelper implements Comparable<FrequencySortHelper> {
    final List<String> key;
    final int score;
    public FrequencySortHelper(List<String> key, HashMap<List<String>, Long>> value) {
        this.key = key;
        score = getFrequencyCount(value);
    }

    public int compareTo(FrequencySortHelper other) {
        int thisVal = this.score;
        int anotherVal = other.score;
        return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }
}

ArrayList<FrequencySortHelper> items = new ArrayList<>(frequencyMap.size());
for (Map.Entry<List<String>, HashMap<List<String>, Long>> item : frequencyMap.entrySet()) {
    items.add(new FrequencySortHelper(item.key(), item.value()));
}

Collections.sort(items);  // Uses FrequencySortHelper's compareTo()

If you're thinking all this Map.Entry<List<String>, HashMap<List<String>, Long>> stuff is awkward, you're right. You should think about defining some objects to contain this data, rather than just stringing together collections.

How to sort a complex HashMap structure in Java?

4 Answers4