Sorting of Map based on keys

Question

This is not basically how to sort the HashMap based on keys. For that I could directly use TreeMap without a wink :)

What I have at the moment is

Map<String, Object> favoritesMap = new HashMap<String, Object>();
and its contents can be
["Wednesdays" : "abcd"]
["Mondays" : "1234"]
["Not Categorized" : "pqrs"]
["Tuesdays" : "5678"]

I want to sort the HashMap based on keys and additional to this I need "Not Categorized" to be the last one to retrieve.

So expected while iterating over keySet is

["Mondays", "Tuesdays", "Wednesdays", "Not Categorized"] i.e. sorted on keys and "Not Categorized" is the last one

Thought of going for HashMap while creating and at the end add ["Not Categorized" : "pqrs"] but HashMap does not guarantee the order :)

Any other pointers for the solution?

http://stackoverflow.com/questions/922528/how-to-sort-map-values-by-key-in-java — RAj, Jan 31 '13 at 10:30

OldCurmudgeon · Accepted Answer · 2013-01-31T12:58:07.840

Are you specifically excluding TreeMap for some external reason? If not you could obviously use TreeMap with a specially made Comparator.

Have you considered any of the other SortedMaps?

If TreeMap is definitely out I would extend HashMap and make it look like there is always one more entry but that is certainly not a trivial piece of work. You should have a very good reason not to use a SortedMap before going down this road.

Added

Here is an example of how you can make a particular entry always sort to the end using a TreeMap:

// This key should always appear at the end of the list.
public static final String AtEnd = "Always at the end";

// A sample map.
SortedMap<String, String> myMap =
        new TreeMap<>(
        new Comparator<String>() {
          @Override
          public int compare(String o1, String o2) {
            return o1.equals(AtEnd) ? 1 : o2.equals(AtEnd) ? -1 : o1.compareTo(o2);
          }
        });

private void test() {
  myMap.put("Monday", "abc");
  myMap.put("Tuesday", "def");
  myMap.put("Wednesday", "ghi");
  myMap.put(AtEnd, "XYZ");

  System.out.println("myMap: "+myMap);
  // {Monday=abc, Tuesday=def, Wednesday=ghi, Always at the end=XYZ}
}

I wonder if you are looking for some variant of that?

No TreeMap is not ruled out just said it will sort the kys including "Not Categorised" which I want at the last while iterating :) — Satya, Jan 31 '13 at 11:09
That really solves the problem. Never the less I was thinking in different way. I had used TreeMap for sorting of all other keys (without "Not Categorised"). Then create new LinkedHashMap to maintian the order, so iterate over TreeMap get sorted keys then insert them back into LinkedHashMap and at last add the "Not Categorised" which ll be at last due to insertion order :) — Satya, Feb 04 '13 at 05:40

score 3 · Answer 2 · edited May 23 '17 at 12:29

3

You can achieve this by using LinkedHashMap as it guarantees to return results in the order of insertion.

Also check the following post to understand difference between map types.

Difference between HashMap, LinkedHashMap and TreeMap

Or just a create a custom class which holds a different key than the value. Sort according to the key of that class. For your case make the key same value as the day, and for "Not Categorized" case ensure that its key starts later than any of the other keys, for example make it "Z_Not Categorized".

public ComplexKey
{
    String key;
    String value;
}

ComplexKey monday = new ComplexKey("monday", "monday");
ComplexKey notCategorized = new ComplexKey("Z_Not Categorized", "Not Categorized");

Then you can write a custom comparator which sort the values according to the key of complexKey class.

edited May 23 '17 at 12:29

Community

1
1

answered Jan 31 '13 at 10:22

cubbuk

7,800
4
35
62

yes I can use that but I need keys to be sorted and last key should be "Not Categorised", LinkedHAshMap cannot sort the keys – Satya Jan 31 '13 at 11:02
Well can't you insert in alphabetical order in the first place? Note that once you inserted a key its place will be set and when you re-insert it the order won't change. Thus once you initialized your map correct, insertion order won't be messed up. – cubbuk Jan 31 '13 at 11:05
oh yes I never thought of inserting into Map in sorted order...was always under impression that TreeMap feature can be utilised for sorting – Satya Jan 31 '13 at 11:12

score 1 · Answer 3 · answered Jan 31 '13 at 10:25

1

In your case I would use a TreeMap:

Map<DayOfWeek, Object> favoritesMap = new TreeMap<>();

where DayOfWeek is a class you declare like:

class DayOfWeek implements Comparable<DayOfWeek> {

as it's not convenient to sort days of wooks as strings.

answered Jan 31 '13 at 10:25

jlordo

37,490
6
58
83

shuangwhywhy · Answer 4 · 2013-01-31T16:59:09.187

In fact, the keys are always sorted. If you output the map a couple of times, you will find that the result remains the same.

First I'll gossip again on hashing:

The reason is hashing. Each object has hashCode() method. The hash space is like a large array which contains all the possible hash values as indices. When a new element is inserted into a HashSet or a new pair is put into a HashMap, it is placed in the hash space according to its hash code. If two elements have the same hash code, they will be compared with equals() method, if unequal, then the new element will be placed next to it.

Then if you know what happens there, you can implement some code like below:

import java.util.*;

class MyString {
    private String str;

    public MyString (String str) {
        this.str = str;
    }

    public String toString () {
        return str;
    }

    public boolean equals (Object obj) {
        if (obj.getClass().equals(MyString.class)) {
            return obj.toString().equals(str);
        }
        return false;
    }

    public int hashCode () {
        if (str.equalsIgnoreCase("Not Categorized")) {
            return Integer.MAX_VALUE;
        } else if (str.hashCode() == Integer.MAX_VALUE) {
            return 0;
        }
        return str.hashCode();
    }
}

public class Test {
    public static void main (String args[]) {
        Map<MyString, String> m = new HashMap<MyString, String>();
        m.put(new MyString("a"), "a");
        m.put(new MyString("c"), "c");
        m.put(new MyString("Not Categorized"), "NC");
        m.put(new MyString("b"), "b");
        Set<MyString> keys = m.keySet();
        for (MyString k : keys) {
            System.out.println(m.get(k));
        }
    }
}

The result is "Not Categorized" always comes at last. The reason is simple: it's hash value is always the maximum of integer.

The reason I create a String wrapper class is String class is final, it can't be extended. So in this way, you would have your class structure a little change, but not much.

It is possible to use TreeMap, though it would be less efficient:

public static void main (String args[]) {
    Map<String, String> m = new TreeMap<String, String>(new Comparator<String>() {
        public int compare (String s1, String s2) {
            if (s1.equals(s2)) {
                return 0;
            }
            if (s1.equalsIgnoreCase("Not Categorized")) {
                return 1;
            }
            if (s2.equalsIgnoreCase("Not Categorized")) {
                return -1;
            }
            if (s1.hashCode() > s2.hashCode()) {
                return 1;
            } else if (s1.hashCode() < s2.hashCode()) {
                return -1
            } else {
                return 0;
            }
        }

        public boolean equals (Object obj) {
            return false;
        }
    });
    m.put("a", "a");
    m.put("c", "c");
    m.put("Not Categorized", "NC");
    m.put("b", "b");
    Set<String> keys = m.keySet();
    for (String k : keys) {
        System.out.println(m.get(k));
    }
}

The result is the same. It will sort all the elements, but it won't change the hashing order of other strings, it only ensures "Not Categorized" always comes to be the largest one.

Sorting of Map based on keys

4 Answers4

First I'll gossip again on hashing:

Then if you know what happens there, you can implement some code like below:

It is possible to use TreeMap, though it would be less efficient:

The result is the same. It will sort all the elements, but it won't change the hashing order of other strings, it only ensures "Not Categorized" always comes to be the largest one.