Sorting a concurrent hash map by value

Question

I am new to java. I want to sort a concurrent hash map by value. I found a way of doing it here - sort concurrent map entries by value

Is there a simpler way of doing it? Can someone please explain it with an example ?

Thanks.

Answer 1

Another solution would be to switch to using the ConcurrentSkipListMap which was added in Java 6. To quote from the Javadocs:

This class implements a concurrent variant of SkipLists providing expected average log(n) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads. Iterators are weakly consistent, returning elements reflecting the state of the map at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Ascending key ordered views and their iterators are faster than descending ones.

SkipLists are probabilistic replacements for balanced trees. They have the same O as trees but usually their implementation is markedly simpler. If most of your operations are hash-table lookups (O(1) by definition) then you will see a performance different for decent table sizes, but if you require sorting often, this may be a better solution.

I just wish Java provided a non-concurrent version of this great data structure.

Answer 2

Depending on your use case I would create another class representing your data structure that is composed of a hashmap and a list say for maintaining ordering of values.

More details about this here:
Sort a Map<Key, Value> by values (Java)
Sorting HashMap by values
http://www.coderanch.com/t/382750/java/java/Sorting-HashMap-values

You can also extend ConcurrentHashMap to override entrySet and keySet methods to return entries/keys in the order of your values.

public class OrderedValueHashMap<K,V extends Comparable<V>> extends ConcurrentHashMap<K, V> {

@Override
public Set<Map.Entry<K, V>> entrySet() {
    Set<Map.Entry<K, V>> orderedValueEntrySet = new TreeSet<Map.Entry<K,V>>(new Comparator<Map.Entry<K,V>>() {

        @Override
        public int compare(java.util.Map.Entry<K, V> o1,
                java.util.Map.Entry<K, V> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    orderedValueEntrySet.addAll(super.entrySet());
    return orderedValueEntrySet;
}

@Override
public Set<K> keySet() {
    Set<K> orderedKeySet = new LinkedHashSet<K>();
    for(Map.Entry<K, V> e : entrySet()) {
        orderedKeySet.add(e.getKey());
    }
    return orderedKeySet;
}

}

The above solution is not optimal if you are calling the methods keySet/entrySet very often as it sorts entries on each call. You may want to cache these results to avoid re-computation while the internal state of the map has not changed.

An example run of the above is as follows:

public static void main(String[] args) {
    ConcurrentHashMap<String,Integer> map = new OrderedValueHashMap<String,Integer>();
    map.put("a", 3);
    map.put("b", 7);
    map.put("c", 1);
    map.put("q", 2);

    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry);
    }

    for (String key : map.keySet()) {
        System.out.println(key);
    }

}

Output:

c=1
q=2
a=3
b=7
c
q
a
b

Answer 3

Is there a simpler way of doing it?

As far as I know, No.

Certainly, there is no way to do an in-place sort of a concurrent hash map. A CHM is inherently unordered so you have to put the entries into a different data structure to represent the orderedness of the entries.

If you told us what your requirements were, perhaps we could suggest an alternative strategy.