Map<String, Integer> and Map<Integer ,String> sorting

Question

I am trying to resolve sorting a map , which contains huge data(1000K). Is there any efficient way than this to sorting these maps ? below is the code snippet.

    Map<Integer, String> myMap1 = new HashMap<Integer, String>();
    Map<String,Integer>  myMap2 = new HashMap< String,Integer>();

    List <Entry<Integer,String>> lst1 = new ArrayList<Entry<Integer,String>>(myMap1.entrySet());
    Collections.sort(lst1, new Comparator<Entry<Integer,String>>(){
        @Override
        public int compare(Entry e1, Entry e2)
        {
            return ((String) e1.getValue()).compareTo((String) e2.getValue());
        }}
    );


    List <Entry<String,Integer>> lst2 = new ArrayList<Entry<String,Integer>>(myMap2.entrySet());        
    Collections.sort(lst2, new Comparator<Entry<String,Integer>>(){
        @Override
        public int compare(Entry e1, Entry e2)
        {
            return ((Integer) e1.getValue()).compareTo((Integer) e2.getValue());
        }}
    );

Sounds like an XY problem. Why do you need to sort so much data in memory? — Reimeus
– Reimeus, Commented May 11, 2015 at 16:15
And what exactly do you mean by "1000K"? 1 million entries? — Jon Skeet
– Jon Skeet, Commented May 11, 2015 at 16:18
@NarayanaSai I don't know who told you this, but if the field is indexed then it will be better to do the sorting in database rather than in the app, unless the sorting algorithm is more complex than a simple data comparison, which is not in this case. — Luiggi Mendoza
– Luiggi Mendoza, Commented May 11, 2015 at 16:30
If you obtain the data from database, obtain it sorted already. Only sort on app when: 1) the field to sort is not indexed and the database may take lot of time doing the sort by itself, or 2) the sorting algorithm is more complex than a single field comparison. — Luiggi Mendoza
– Luiggi Mendoza, Commented May 11, 2015 at 16:45

akhil_mittal · Accepted Answer · 2015-05-11 16:23:28Z

1

IMO a priority queue can also be a good approach:

Map<Integer, String> myMap1 = new HashMap<Integer, String>();
PriorityQueue<Entry<Integer, String>> pq = new PriorityQueue<Map.Entry<Integer,String>>(myMap1.size(), new Comparator<Entry<Integer, String>>() {
    @Override
    public int compare(Entry<Integer, String> arg0, Entry<Integer, String> arg1) {
        return arg0.getValue().compareTo(arg1.getValue());
    }
});
pq.addAll(myMap1.entrySet());
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

Also Google Guava can be a good option as it provides a BiMap implementations which can be inversed, and then just sort on inversed map keys.

 Map<Integer, String> myMap1 = new HashMap<Integer, String>();
    // insert values in myMap
    Map<String,Integer>  myMap2 = myMap1.inverse();
    SortedMap<Integer, Character> sortedInversed = new TreeMap<Integer, Character>(myMap2 );

edited May 11, 2015 at 16:23

answered May 11, 2015 at 16:18

akhil_mittal

24.3k8 gold badges99 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Luiggi Mendoza Over a year ago

You will be better by using a TreeMap rather than HashMap. TreeMap is already sorted.

akhil_mittal Over a year ago

In TreeMap insertion will be O(lg n) where as it would be O(1) in Map. Also IMO Set and Map do not handle duplicates well.

Luiggi Mendoza Over a year ago

IMO Set and Map do not handle duplicates well looks like you haven't used them in the right way then, but that's aside of the problem. Also, inserting in the PriorityQueue will take time O(lg n), so you have to pay that price in order to sort, regardless of the data structure you choose.

Luiggi Mendoza Over a year ago

A map doesn't allow duplicates. And TreeMap uses a red black tree, which is a balanced tree so you won't have the LinkedList situation as you describe. I really don't know what you're talking about.

akhil_mittal Over a year ago

Sorry I meant they don't handle duplicates well in case of keys.

|

Collectives™ on Stack Overflow

Map<String, Integer> and Map<Integer ,String> sorting

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related