Sorting HashMap by values

[Jan Spengen]

Hi.

I'm trying to sort a HashMap by values. I know that it might not be "good style", but it would save a lot of work, as I wouldn't have to rewrite lots of code if I could just get the HashMap sorted.

After lots of searching and trial and error cases I'm still stuck.

I found this old topic: https://coderanch.com/t/370496/java/java/Sorting-Hashtable-values-retriving-kay

and I thought that might be it. But all I can get is a sorted System.out ..
the HashMap itself is still unsorted.
I tried using this approach, which is mentioned in the old thread.

 import java.util.* ;
public class H
{
    static HashMap first = new HashMap();
    static
    {
        first.put("20030120" , new Integer (56));
        first.put("20030118" , new Integer (19));
        first.put("20030125" , new Integer (25));
        first.put("20030122" , new Integer (32));
        first.put("20030117" , new Integer (67));
        first.put("20030123" , new Integer (34));
        first.put("20030124" , new Integer (42));
        first.put("20030121" , new Integer (19));
        first.put("20030119" , new Integer (98));
    }
    public static void main( String[] args )
    {
        ArrayList as = new ArrayList( first.entrySet() );
        
        Collections.sort( as , new Comparator() {
            public int compare( Object o1 , Object o2 )
            {
                Map.Entry e1 = (Map.Entry)o1 ;
                Map.Entry e2 = (Map.Entry)o2 ;
                Integer first = (Integer)e1.getValue();
                Integer second = (Integer)e2.getValue();
                return first.compareTo( second );
            }
        });
        
        Iterator i = as.iterator();
        while ( i.hasNext() )
        {
            System.out.println( (Map.Entry)i.next() );
        }
    }
}    

Now my qustion is, how to put those sorted Entry sets back in a HashMap?
This is probably very easy, but I'm just not seeing it.

Thanks in advance for reading. Any input is appreciated.

[Ernest Friedman-Hill]

Give up. HashMap won't store your data sorted in any order, let alone by value.

TreeMap will sort data inserted in arbitrary order, but only by the key. You can write a comparator that tries to sort by values given the key, but it's a mess and won't always work right.

LinkedHashMap, on the other hand, will store items in insertion order. So if you sort by value, as you've shown here, then insert into a LinkedHashMap in sorted order, they'll stay that way.

[Jan Spengen]

Damn, then I've got to find other solutions to deal with the problem it seems.

LinkedHashMap doesn't sound too bad.. but as I remove and insert values on the map, it will be unsorted again. (Though, I could probably repeat the process, got to think about that.)

Well anyway thanks a lot.
Just the answer that what I wanted is not going to become true saves me quite some time (even though that would have been the easiest solution).

[Peter Chase]

As EFH says, HashMap has no ordering at all, and TreeMap only orders keys. No single built-in JDK collection will do what you want.

But don't despair. All you need is two collections. Probably best to encapsulate them in a single class.

Mappings from your keys to values would be stored in an ordinary HashMap. Mappings from values to keys would be stored in a TreeMap. Your encapsulating class would need to make sure that insertions and deletions were correctly applied to both maps at all times.

If the values are not unique, you need a little extra complication. You'd probably need to make the TreeMap map from values to Lists or Sets of keys.

[Jan Spengen]

This time I'll just go with a LinkedHashMap, as the time pressure is rising, and this is for this project the easier, faster solution.(And I already coded it ) Plus I found that a sorted list is only necessary in 2 places, where I can easily work with the LinkedHashMap (and "resorting" the map is not a problem performance wise).
(And well this is for an in-house application, so code quality is not as high on the priority list, as if it were a customer project. )

Though next time I encounter this, I'll try your approach, cause it seems to be the better way to handle this.

Thanks a lot for the input though, I really appreaciate it.
[ May 25, 2007: Message edited by: Jan Spengen ]

[Devesh H Rao]

Originally posted by Ernest Friedman-Hill:
Give up. HashMap won't store your data sorted in any order, let alone by value.

Ernest, I know that we are supposed to give sound advice but I could not resist the "Give up. HashMap won't store your data sorted in any order" statement... .... sorry.... I apologise beforehand...

We can make Hashmap work on a FILO basis... it involves a bit of hack and also the capacity of the hashmap needs to be known before hand.

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

HashMap h = new HashMap([B]20[/B]);
 
KeyValue k = null;
for(int i = 0; i <20; i++){
k = new KeyValue(""+i,""+i);
h.put(k, k);
}

Iterator it = h.keySet().iterator();

while(it.hasNext()){
System.out.print(" "+it.next());
}
 
}
 
}
 
class KeyValue{
public String key = "0";
public String value= "0";

public KeyValue(String key, String value){
this.key= key;
this.value = value;
}
public String toString(){
return value;
}

[B]public int hashCode() {
return 0;
}[/B]
}
 

Output - >

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Disclaimer : The above is not recomended absolutely in any circumstances as overriding hashcode in the above fashion is a strict no-no.... It is not only bad programatic practise but also its usage could lead to further issues.

Originally posted by Ernest Friedman-Hill:


LinkedHashMap, on the other hand, will store items in insertion order. So if you sort by value, as you've shown here, then insert into a LinkedHashMap in sorted order, they'll stay that way.

LinkedHash is the best way to go about what you want, second option could be a custom container with a comparater built in to contain you sorting criteria. but then with the project pressure it is better if you do what Ernest has advised....

[Jesper de Jong]

Disclaimer : The above is not recomended absolutely in any circumstances as overriding hashcode in the above fashion is a strict no-no.... It is not only bad programatic practise but also its usage could lead to further issues.

Argh, that is a terrible and ugly hack, which does not only heavily rely on the internal implementation details of HashMap, it also defeats the whole HashMap mechanism! By making hashCode() return 0, the HashMap will store all data in one bucket. This effectively makes the HashMap a List, with linear lookup time (instead of logarithmic lookup time).

Why do you even suggest such a solution if you already know how bad and ugly it is?

Jan, or anyone else, please forget about this immediately!

[Peter Chase]

Originally posted by Devesh H Rao:
involves a bit of a hack

It's more than a bit of a hack. By having the same hashcode for all entries, you have disabled the whole hashed-ness of the collection. Even when this has been done, it only happens to give ordered data because of the particular implementation of HashMap.

So it's purely a curiosity, not any sort of solution at all. Not for any application whatsoever.

I'm sure the original poster understood that, but just in case any others didn't...

[Ernest Friedman-Hill]

Originally posted by Jesper Young:

Why do you even suggest such a solution if you already know how bad and ugly it is?

Sometimes, ugliness can be so extreme as to become beauty. I'm not sure this is one of those cases, but in fact it's rather lovely to be able to write something like this precisely because you do understand the underlying implementation. Deep knowledge is always something to appreciate, even when it is used for evil...

[Devesh H Rao]

Originally posted by Ernest Friedman-Hill:


Give up. HashMap won't store your data sorted in any order, let alone by value.

I wrote it just coz of this ..

"Give up. HashMap won't store your data sorted in any order"

And I guess I took extra care to make sure the person who asked for the solution didn't even think of taking the code I wrote to be even close to a solution

Disclaimer : The above is not recomended absolutely in any circumstances as overriding hashcode in the above fashion is a strict no-no.... It is not only bad programatic practise but also its usage could lead to further issues.

I also seconded what ernest wrote as that is what I would do or for that matter a better approach.

Originally posted by Jesper Young:


By making hashCode() return 0, the HashMap will store all data in one bucket.

You have got it wrong buddy.... try replacing the initial capacity in my code to 10 and rerun the code, it fails...

Hashmap stores the key based on two things.

1> Hash
2> capacity of the Container

The hash returned by the hashcode is run through another set of operations to randomize the code and hence if we return anything else than 0, hashing still works.

Then it takes into consideration the capacity of the hashmap to calculate the index, in case the initial capacity being less than the total number of records being put in indexing again will randomize as we have more than one bucket and hence no order.

so to get the data in an ordered fashion we need to turn off the hashing feature which i did by returning 0 and then make sure only one bucket is in scope which I did by initilizing the hashmap with 20... turn off anyone of this and hashmap rules apply again ....

Originally posted by Ernest Friedman-Hill:


even when it is used for evil...

Maybe I have not learnt my lessons in questioning the fundamentals of java....private static void main(String [] args)
[ May 25, 2007: Message edited by: Devesh H Rao ]

[Sandeep Gabhale]

LinkedHashMap, on the other hand, will store items in insertion order. So if you sort by value, as you've shown here, then insert into a LinkedHashMap in sorted order, they'll stay that way.


Hi Ernest,

Thanks for the update!
This is basic, but very valuable information about all the Maps

[Campbell Ritchie]

Not quite. A LinkedHashMap stores the items in any old order, but it also stores the keys in insertion order. Its Iterator follows the linked list, and retrieves Map.Entries in insertion order.