按值排序并发映射条目 [英] sort concurrent map entries by value

问题描述

有没有办法创建一个线程安全的实现 Map ，维护它的条目按值排序？我知道我可以创建一个线程安全映射像这样

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>();

然后，我可以通过将值传递给像这样的实用程序方法， / p>

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;
}

但我要找的是线程安全的映射以维持按值排序的条目，因此在每次插入/移除之后，我不必调用诸如上述的方法，以便保持按值排序的条目。我想我正在寻找一个实现，结合了 ConcurrentHashMap 和 LinkedHashMap 的行为，但没有找到一个然而。

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 几乎提供了我想要的，但它似乎只支持按键值排序。

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

推荐答案

数据结构。在高级别，执行以下操作。

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

首先，实现Map.Entry以保持键值对。

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.

复合结构如下所示：

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.

您还需要在InternalEntry的比较实现中做一些特殊的情况代码如果null键/值需要支持。

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

这篇关于按值排序并发映射条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！