Implementando un LinkedHashMap concurrente

Question

Estoy tratando de crear un LinkedHashMap concurrente para una arquitectura multiproceso.

Si uso Collections#synchronizedMap(), tendría que usar bloques sincronizados para la iteración. Esta implementación llevaría a la adición secuencial de elementos.

Si uso ConcurrentSkipListMap hay alguna manera de implementar un Comparator para almacenar secuencialmente, como se almacena en la Lista enlazada o en la cola.

Me gustaría utilizar los paquetes integrados de Java en lugar de los de terceros.

EDIT:

En este concurrente LinkedHashMap, si las claves son el nombre, deseo dejar las llaves en la secuencia de su llegada. es decir, se agregará un nuevo valor al inicio o al final, pero de forma secuencial.

Al iterar, el LinkedHashMap podría agregarse con nuevas entradas o eliminarse. pero la iteración debería ser la secuencia en la que se agregaron las entradas.

Entiendo que al usar Collections#synchronizedMap(), debería implementarse un bloque sincronizado para la iteración, pero el mapa podría ser modificable (las entradas podrían agregarse/eliminarse) mientras se está iterando.

Answer 1

Use Collections#synchronizedMap().

Según mi creencia, si uso Collections.synchronizedMap(), tendría que usar bloques sincronizados para getter/setter.

Esto no es cierto. Solo necesita sincronizar la iteración en cualquiera de las vistas (keyset, values, entryset). También vea la documentación de la API sobreenlace.

Answer 2

Si usa synchronizedMap, no tiene que sincronizar externamente, a excepción de la iteración. Si necesita conservar el orden del mapa, debe usar un SortedMap. Puede usar ConcurrentSkipListMap, que es seguro para subprocesos, u otro SortedMap en combinación con synchronizedSortedMap.

Answer 3

A LinkedHashMap tiene una lista doblemente vinculada que se ejecuta a través de una tabla hash. Un FIFO solo muta los enlaces en una escritura (inserción o eliminación). Esto hace que la implementación de una versión sea bastante sencilla.

1. Escriba un LHM con solo el orden de inserción permitido.
2. Cambie a un ConcurrentHashMap como la tabla hash.
3. Proteger #put()/#putIfAbsent()/#remove() con un candado.
4. Haga que el campo "siguiente" sea volátil.

En la iteración, no se necesita bloqueo ya que puede seguir con seguridad el campo "siguiente". Las lecturas pueden estar libres de bloqueo simplemente delegando en el CHM en un #get().

Answer 4

Hasta ahora, mi proyecto utilizaba LRUMap de Apache Collections pero está basado en SequencedHashMap. Las colecciones proponen ListOrderedMap pero ninguna es segura para subprocesos.

He cambiado a MapMaker de Google Guava. Puedes mirar CacheBuilder también.

Answer 5

Um, la respuesta simple sería usar un proveedor de claves monótonamente creciente en el que opera su Comparator. Piense en AtomicInteger, y cada vez que inserta, crea una nueva clave que se utilizará para las comparaciones. Si agrupa su clave real, puede hacer un mapa interno de OrderedKey<MyRealKeyType>.

class OrderedKey<T> implements Comparable<OrderedKey<T>> { 
    T realKey; 
    int index; 
    OrderedKey(AtomicInteger source, T key) { 
    index = source.getAndIncrement(); 
    realKey = key; 
    } 
    public int compareTo(OrderedKey<T> other) { 
    if (Objects.equals(realKey, other.realKey)) { 
     return 0; 
    } 
    return index - other.index; 
    } 


} 

Esto obviaría la necesidad de un comparador personalizado y le dará un buen O (1) Método para calcular el tamaño (a menos que permita elimina, en cuyo caso, cuente esos también, por lo que sólo puede restar "todo exitoso elimina" de "todas las adiciones exitosas", donde el éxito significa que realmente se creó o eliminó una entrada).