값순 정렬 맵핑 항목

Question

값으로 정렬 된 항목을 유지 관리하는 Map의 스레드 안전 구현을 만드는 방법이 있습니까? 나는이

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

같은 스레드 안전 Map를 만들 수 있습니다 그리고 다음과 같은 유틸리티 메소드에 전달하여 값으로 분류 항목을 얻을 수 있습니다 알고

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은 내가 원하는 것을 거의 제공하지만 키 값순으로만 정렬 할 수 있습니다.

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

주 전체지도를 구현하는 - 당신이 다른 방법으로 도움이 필요하면 알려주세요.

null 키/값을 지원해야하는 경우 InternalEntry의 비교 구현에서 특수 사례 코드를 수행해야합니다.