按值对并发映射条目进行排序

Question

有没有办法创建一个线程安全的Map实现，同时保持其值按排序方式进行排序？我知道可以创建一个像这样的线程安全的Map：

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

然后，我可以通过将其传递给像这样的实用程序方法来按值对条目进行排序：

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

但是我需要的是一个线程安全的Map，它能够通过值来维护条目的排序，这样我就不必在每次插入/删除后调用上述方法以保持条目按值排序。我猜我正在寻找一种将ConcurrentHashMap和LinkedHashMap的行为结合起来的实现，但还没有找到。 ConcurrentSkipListMap几乎提供了我想要的功能，但似乎只支持按键值排序。

- Dónal

---

在您的使用情况中，您能否将问题限制为唯一值，或者有时会出现重复值？如果您确实有重复值，那么您是否有进一步的排序约束条件？ - Dilum Ranatunga

另外，请澄清一下——您想要“排序”还是“有序”？LinkedHashMap 可以给您有序，但不是排序。 - Dilum Ranatunga

嗯……sorted和ordered有什么区别吗？ - Dónal

@Dilum 如果需要的话，我可以消除重复的映射值的可能性。 - Dónal

假设您按顺序将“three”、“two”、“one”添加到空的LinkedHashSet中。如果您遍历这些元素，它们将以相同的顺序返回。这是有序的--它们以某种可预测的、有意义的方式返回。如果您使用默认比较器将它们添加到TreeSet中，则它们将作为“one”、“three”、“two”返回。再次可预测和有意义，但也排序，因为插入顺序没有影响。如果您将元素添加到HashSet中，则元素的顺序将无法预测。 - Dilum Ranatunga

Answer 1

考虑构建一个复合数据结构来完成这个任务。在高层次上，按照以下步骤进行：

首先，实现Map.Entry来保持键值对。该对的排序将首先按值排序，然后按键排序。

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

整个条目可以用作有序映射的键。

但是该映射不支持通过键有效查找值。为了实现这一点，引入另一个映射，将键映射到条目。

组合结构如下所示：

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

请注意，我没有提供实现完整Map所需的所有代码 - 如果您需要其他方法的帮助，请告诉我。

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

- Dilum Ranatunga

---

@Dave，我已经让你自己决定是否将TreeMap、LinkedHashMap与它们的并发版本进行切换。 - Dilum Ranatunga