ordena las entradas del mapa concurrente por valor

Question

¿Hay alguna manera de crear una implementación segura para subprocesos de Map que mantenga sus entradas ordenadas por valor? Sé que puedo crear un hilo de seguridad Map como esto

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

Y a continuación, puede obtener las entradas ordenadas por valor pasándolo a un método de utilidad como esto:

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

Pero lo que yo' m buscando es un hilo seguro Map que mantiene las entradas ordenados por valor, por lo que no tengo que llamar a un método como el anterior después de cada inserción/eliminación con el fin de mantener las entradas ordenados por valor. Supongo que estoy buscando una implementación que combine el comportamiento de ConcurrentHashMap y LinkedHashMap, pero aún no he encontrado ninguna.

ConcurrentSkipListMap casi proporciona lo que quiero, pero solo parece ser compatible con la clasificación por valor clave.

Answer 1

Considere crear una estructura de datos compuesta para esto. En un nivel alto, haz lo siguiente.

Primero, implemente Map.Entry para mantener los pares clave-valor. El orden de la pareja sería primero por valor, y luego por clave.

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

La entrada completa se puede utilizar como la clave de un mapa ordenado.

Pero ese mapa no admite la búsqueda eficiente de valor por clave. Para lograr eso, introduzca otro mapa, que asigna claves a las entradas.

La estructura compuesta se ve así:

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

en cuenta que no hemos suministrado todo el código necesario para implementar un mapa completo - que me haga saber si necesita ayuda con los otros métodos.

También necesita hacer un código de caso especial en la implementación de comparación de InternalEntry si es necesario admitir claves/valores nulos.