按值排序并发映射条目

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

但我” m寻找的是一个线程安全的Map保持条目按值排序，这样我就不必在每次插入/删除后调用上述方法，以保持条目按值排序。我想我正在寻找一种结合ConcurrentHashMap和LinkedHashMap的行为的实现，但还没有找到。

ConcurrentSkipListMap几乎提供了我想要的，但它似乎只支持按键值排序。

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

请注意，我还没有提供所有必要的代码来实现一个完整的地图 - 让我知道，如果你需要用其他方法帮助。

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