sort concurrent map entries by value

Question

Is there any way to create a thread-safe implementation of Map that maintains it's entries sorted by value? I know I can create a thread-safe Map like this

ConcurrentMap<String, Double> rankings = new ConcurrentHashMap<String, Double>();

And I can then get the entries sorted by value by passing it to a utility method like this:

public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });

    Map<K, V> result = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : list) {
        result.put(entry.getKey(), entry.getValue());
    }
    return result;
}

But what I'm looking for is a thread-safe Map that maintains the entries sorted by value, so that I don't have to call a method such as the above after every insertion/removal in order to keep the entries sorted by value. I guess I'm looking for an implementation that combines the behavior of ConcurrentHashMap and LinkedHashMap, but haven't found one yet.

ConcurrentSkipListMap almost provides what I want, but it only seems to support sorting by key value.

Answer 1

Consider building a composite data structure for this. At a high level, do the following.

First, implement Map.Entry to keep key-value pairs. The pair's ordering would be first by value, and then by key.

private static class InternalEntry<K extends Comparable<K>,
                                   V extends Comparable<V>>
        implements Comparable<InternalEntry<K, V>>,
                   Map.Entry<K, V> {
    private final K _key;
    private final V _val;

    InternalEntry(K key, V val) {
        _key = key;
        _val = val;
    }

    public K getKey() {
        return _key;
    }

    public V getValue() {
        return _val;
    }

    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public int compareTo(InternalEntry<K, V> o) {
        int first = _val.compareTo(o._val);
        if (first != 0) {
            return first;
        }
        return _key.compareTo(o._key);
    }
}

The entire entry can be used as the key of an ordered map.

But that map does not support efficient lookup of value by key. To achieve that, introduce another map, which maps keys to entries.

The composite structure looks like this:

class OrderedByValue<K extends Comparable<K>, V extends Comparable<V>> {
    private final Map<InternalEntry<K, V>, Boolean> _ordering = 
        new TreeMap<InternalEntry<K, V>, Boolean>();

    private final Map<K, InternalEntry<K, V>> _lookup = 
        new HashMap<K, InternalEntry<K, V>>();

    public V put(K key, V val) {
        InternalEntry<K, V> entry = new InternalEntry<K, V>(key, val);
        InternalEntry<K, V> old = _lookup.put(key, entry);
        if (old == null) {
            _ordering.put(entry, Boolean.TRUE);
            return null;
        }
        _ordering.remove(old);
        _ordering.put(entry, Boolean.TRUE);
        return old.getValue();
    }

    @SuppressWarnings({"unchecked"})
    public Iterable<Map.Entry<K, V>> entrySet() {
        Iterable entries = Collections.unmodifiableSet(_ordering.keySet());
        return (Iterable<Map.Entry<K, V>>) entries;
    }
}

Note that I've not supplied all the necessary code to implement a full Map -- let me know if you need help with the other methods.

You also need to do some special case code in the InternalEntry's comparison implementation if null keys/values need to be supported.