• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 537
  • Last Modified:

Java how to order the elements in a hashset

Hi,

I have an hashset which contains a string as key and an integer as value. How can I order it in the most efficient way?

Furthermore, can I order the elements while I am constructing the hashset object?

Which way would be better, the do-ordering-later way or the opposite?

Thanks!
0
wsyy
Asked:
wsyy
  • 23
  • 6
  • 4
1 Solution
 
for_yanCommented:
HashSet does not support ordering - so you cannot order eleemnts in the HashSet
rread here:
http://download.oracle.com/javase/6/docs/api/java/util/HashSet.html

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time
0
 
for_yanCommented:
HashSet is even not a map - it is just set so you cannot taklk about key and value
0
 
for_yanCommented:
If you are talking about HashMap - it does not support ordering either, but is is a Map, so it can have Key and value
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
for_yanCommented:
I think LinkedHashMap is a map with predicatble iteration order:

http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html

0
 
for_yanCommented:
And iteration order of the LinkedHashMap by default is the one which you use to insert pairs

I'd think that better to use normal HashMap
and set required order when you eenedd to iterate over the HashMap
0
 
for_yanCommented:

I'd think that better to use normal HashMap
and set required order when you need to iterate over the HashMap

Frankly if the number of elements is not that dramatically huge, I'd populate
ArrayList with the keys simultaneously with the HashMap

then you use Collections.sort(arraylist);
and use your arraylist to iterate through the keys of your hashmap

This requires more memory, but very straightforward logically
way and in the case of ususl Hashmaps (not huge) memory is not essential
0
 
for_yanCommented:
Or you can do it later using keySet() method which returns enumeration and then populating TreeSet with the keys and then using TreeSet
for iterating over your HashMap
0
 
for_yanCommented:
Well, this is one way:
        HashMap<String, Integer> msi = new HashMap<String,Integer>();
        msi.put("xyz",5);
        msi.put("def",10);
        msi.put("fhj",15);

        Set<String> set = msi.keySet();

        TreeSet<String> set1 = new TreeSet<String>();

             Iterator it = set.iterator();
        while(it.hasNext())set1.add((String)it.next());

        Iterator it2 = set1.iterator();
        while(it2.hasNext()){
            String s30 = (String)it2.next();
            System.out.println(s30 + " : " + msi.get(s30) );
        }

Open in new window


Output:

def : 10
fhj : 15
xyz : 5

Open in new window

0
 
for_yanCommented:
This is another way - you actually don't need to check
if arraylist contains key, because your HashMap should have unique keys anyway:

        HashMap<String, Integer> msi = new HashMap<String,Integer>();

        ArrayList<String> ar30 = new ArrayList<String>();


        msi.put("xyz",5);
        if(!ar30.contains("xyz"))ar30.add("xyz");
        msi.put("def",10);
        if(!ar30.contains("def"))ar30.add("def");

        msi.put("fhj",15);
        if(!ar30.contains("fhj"))ar30.add("fhj");

        Collections.sort(ar30);

            for(String s35: ar30){

              System.out.println(s35 + " : " + msi.get(s35) );   

            }

Open in new window


Output:

def : 10
fhj : 15
xyz : 5

Open in new window

0
 
for_yanCommented:
Actually TreeMap is what you wnat form the very begining
http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeMap.html
This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class
0
 
for_yanCommented:
This is with TreeMap:

         TreeMap<String, Integer> msi10 = new TreeMap<String,Integer>();
            msi10.put("xyz",5);
           msi10.put("def",10);
           msi10.put("fhj",15);

               for(String s40: msi10.keySet()){

              System.out.println(s40 + " : " + msi10.get(s40) );   

            }

Open in new window


Output:

def : 10
fhj : 15
xyz : 5

Open in new window


There are too many of these collections, impossible to kep all that in mind.

Luckinly with ArrayList and Hashmap you can still accommodate all practical needs
0
 
wsyyAuthor Commented:
Thanks for_yan. I would like to order by the Integer as value. Sorry that I forgot mentioning it.
0
 
for_yanCommented:
Why do you need to order the map in this way?
Then just make it opposite - make HashMap with the integers and keys and strings as values
If your values are not unique then make HashMap Itneger - ArrayList of strings
0
 
for_yanCommented:

Why do you need to order the map in this way?
Then just make it opposite - make HashMap with the integers as keys and strings as values
If your values - same integers can correspond to more than one strings -   then make HashMap Integer - ArrayList of strings
0
 
for_yanCommented:
This will sort the way you want:

public class  InvertSort{
public static void main(String[] args){
        msi.put("xyz",5);
        if(!ar30.contains("xyz"))ar30.add("xyz");
        msi.put("def",10);
        if(!ar30.contains("def"))ar30.add("def");

        msi.put("fhj",15);
        if(!ar30.contains("fhj"))ar30.add("fhj");


        Set<Map.Entry<String, Integer>> setm = msi.entrySet();

        ArrayList <Map.Entry<String, Integer>> arme = new ArrayList<Map.Entry<String, Integer>>();

        arme.addAll(setm);
        Collections.sort(arme, new MyComp1());

        for(Map.Entry<String, Integer> me : arme){
            System.out.println("result:  " + me.getKey() + " : " + me.getValue());


        }
}

}

class MyComp1 implements Comparator<Map.Entry<String, Integer>>
{

    public int compare(Map.Entry<String,Integer> me1, Map.Entry<String,Integer> me2 ) {
          return me1.getValue().compareTo(me2.getValue());
    }
}

Open in new window


Output:
result:  xyz : 5
result:  def : 10
result:  fhj : 15

Open in new window

0
 
for_yanCommented:
This should work (previous code had remnants of my other tests, so it may not complile):

public class  InvertSort{


public static void main(String[] args){
      HashMap<String, Integer> msi = new HashMap<String,Integer>();

    
        msi.put("xyz",5);
               msi.put("def",10);
     
        msi.put("fhj",15);
     

        Set<Map.Entry<String, Integer>> setm = msi.entrySet();

        ArrayList <Map.Entry<String, Integer>> arme = new ArrayList<Map.Entry<String, Integer>>();

        arme.addAll(setm);
        Collections.sort(arme, new MyComp1());

        for(Map.Entry<String, Integer> me : arme){
            System.out.println("result:  " + me.getKey() + " : " + me.getValue());


        }
}

}

class MyComp1 implements Comparator<Map.Entry<String, Integer>>
{

    public int compare(Map.Entry<String,Integer> me1, Map.Entry<String,Integer> me2 ) {
          return me1.getValue().compareTo(me2.getValue());
    }
}

Open in new window



result:  xyz : 5
result:  def : 10
result:  fhj : 15

Open in new window

0
 
wsyyAuthor Commented:
I am confused by the two statements:

ArrayList <Map.Entry<String, Integer>> arme = new ArrayList<Map.Entry<String, Integer>>();

        arme.addAll(setm);

1. What is setm?
2. Why should I turn a map into an arraylist of map?
0
 
for_yanCommented:
setm is a set of Map.Entry objects.
You can sort this set using the comparator which sorts them by the value of Integers (not the keys but values)
In order to order the set using Collections.sort(list, Comparator) method you need to make a list of it.
addAll() is the simplest way to do it
So we make a list then order it using the comparator which orders the entry by values

Then you can iterate through this list or you can turn this list int LinkedHashMap which will maintain order of Enttries and Entries will be added
in the order of growing values

0
 
for_yanCommented:
you rather explain what is your purpose, maybe it will be more natural just to reverse keys and values and make map with integers as keys
0
 
wsyyAuthor Commented:
my purpose is to turn the map into an ordered list of some structure which contains the key and the integer value.

the integer can't be used as key, as some are the same.
0
 
wsyyAuthor Commented:
Also I want to output something like an arraylist of which contains the keys and the values.
0
 
for_yanCommented:
That is exactly what this arme list is - it is ArrayList of MapEntry objects (each object is a pair of key values) ordered by values
0
 
for_yanCommented:

otherwise how you want both keys and values in one arraylist ?
0
 
for_yanCommented:

This is another nice way to turn your initial HashMap
into TreeMap with required ordering:

public class NewSorting {
public static void main(String [] args){

        HashMap<String, Integer> msi20 = new HashMap<String, Integer>();

        msi20.put("xyz",10);
        msi20.put("def",5);
        msi20.put("abc",20);
        msi20.put("gfhs",13);

                               MyComp2 cmp = new MyComp2();

           cmp.setMap(msi20);


         TreeMap<String, Integer> msi25 = new TreeMap<String,Integer>(cmp);

        msi25.putAll(msi20);

        for(String s40: msi25.keySet()){

            System.out.println(s40 + " : " + msi25.get(s40));

        }

}
}


class MyComp2 implements Comparator<String>{

    public HashMap<String, Integer> m;

    public void setMap(HashMap<String, Integer> m){
        this.m = m;
    }



    public int compare(String s0, String s1){
        return(m.get(s0).compareTo(m.get(s1)));
    }


}

Open in new window


output:

def : 5
xyz : 10
gfhs : 13
abc : 20

Open in new window

0
 
for_yanCommented:

The method above actually uses constructor of TreeSet
which uses comparator for the keys as the argument.
The comparator however is based on the existing HashMap and compares
the keys by first determining the corresponding values and
and comparing these values (so it actually returns that one key is bigger than another,
if corresponding value for th first key is bigger than for the second)
So when we putall entries of HashMap to the  TreeMap created
with such comparator they become ordered the way we needed.
Really looks nice to me.
0
 
wsyyAuthor Commented:
for_yan, thanks for quick response.

Two questions:

1. Is arme an arraylist of map objects or a data structure containing key-value pairs?

2. What is the performance of the TreeMap compared to the first solution?

The TreeMap is easier to understand, but performance prevails.
0
 
for_yanCommented:
arme is an arraylist of Map.Entry objects.

You can easily convert it to LinkedHashMap (you cannot convert it to HashMap as you'll lose ordering, as HashMap does not maintain ordering).

LinkedHashMap<String,Integer> lhs = new LinkedHashMap<String, Integer>();

   for(Map.Entry<String, Integer> me : arme){

lhs.put(me.getKey(),me.getValue());
}


LinkedHashMap will preserve the order in which we populated it


Performance is always subject to testing - depends on particular situation.

TreeMap population may be an issue,
but sorting of this ArrayList may also take time

I tend to believe that for huge lists
one time sorting will be better than every time rather slow adding to TreeMap
but it is difficult to predict.

Are you really talking about huge collections?

If so, I would also still consider making
HashMap with Integer as key and ArrayList of your strings (your current keys) as values.
I kind of believe that such structure is apt to suit all your conceivable needs
and probably will be more agile for handling in terms of performance.
Again, there can be no guarantee, but this is my feeling.

However, all that will really matter for really huge collections.
In many cases people tend to think about performance issues, when in fact
all these things will not be bottlenecks
and the real issues will be I/O stuff.







0
 
CEHJCommented:
>>I have an hashset which contains a string as key and an integer as value. How can I order it in the most efficient way?

In what way do you want it ordered? btw, i think you mean HashMap - HashSet doesn't have keys - just values
0
 
wsyyAuthor Commented:
Sorry, I do mean HashMap with a string key and a numberic value. I want the elements ordered by the numeric value.
0
 
CEHJCommented:
You can't sort/order a Map by its values - only by its keys. You can turn it into a List ordered in that way, but what are you going to do with it then, since you won't any longer be able to use it as a Map?
0
 
CEHJCommented:
If you can show some demo code of your Map, we might be able to do something practical
0
 
for_yanCommented:
wsyy,
You have at least two very practical methods how to do it with working and tested code. What is your concern ?
 
0
 
CEHJCommented:
>>the integer can't be used as key, as some are the same.

So you wanted if possible to use that to look up the values?
0

Featured Post

[Webinar] Database Backup and Recovery

Does your company store data on premises, off site, in the cloud, or a combination of these? If you answered “yes”, you need a data backup recovery plan that fits each and every platform. Watch now as as Percona teaches us how to build agile data backup recovery plan.

  • 23
  • 6
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now