Implementazione di una LinkedHashMap simultanea

Question

Sto provando a creare una LinkedHashMap concorrente per un'architettura con multithreading.

Se utilizzo Collections#synchronizedMap(), dovrei utilizzare i blocchi sincronizzati per l'iterazione. Questa implementazione porterebbe ad un'aggiunta sequenziale di elementi.

Se utilizzo ConcurrentSkipListMap esiste un modo per implementare uno Comparator da memorizzare in sequenza, come memorizzato in Elenco o coda collegati.

Vorrei utilizzare i pacchetti integrati di java anziché di terze parti.

EDIT:

In questo concomitante LinkedHashMap, se le chiavi sono il nome, desidero mettere le chiavi in ​​sequenza del loro arrivo. Ad esempio, il nuovo valore verrebbe aggiunto all'inizio o alla fine, ma in sequenza.

Durante l'iterazione, è possibile aggiungere LinkedHashMap con nuove voci o rimosso. ma l'iterazione dovrebbe essere la sequenza in cui sono state aggiunte le voci.

Capisco che utilizzando Collections#synchronizedMap(), sarebbe necessario implementare un blocco sincronizzato per l'iterazione, ma la mappa sarebbe modificabile (le voci potrebbero essere aggiunte/rimosse) mentre viene iterata.

Answer 1

Utilizzare Collections#synchronizedMap().

Secondo la mia convinzione, se utilizzo Collections.synchronizedMap(), dovrei utilizzare blocchi sincronizzati per getter/setter.

Questo non è vero. È sufficiente sincronizzare l'iterazione su una qualsiasi delle viste (keyset, valori, entryset). Vedi anche la documentazione dell'API obsoleta.

Answer 2

Se si utilizza synchronizedMap, non è necessario sincronizzarsi esternamente, tranne che per l'iterazione. Se è necessario conservare l'ordine della mappa, è necessario utilizzare SortedMap. È possibile utilizzare ConcurrentSkipListMap, che è thread-safe, o un'altra SortedMap in combinazione con synchronizedSortedMap.

Answer 3

A LinkedHashMap Un elenco doppiamente collegato che scorre in una tabella hash. Un FIFO muta solo i link su una scrittura (inserimento o rimozione). Ciò rende l'implementazione di una versione abbastanza semplice.

1. Scrivere un LHM con solo l'ordine di inserimento consentito.
2. Passare a ConcurrentHashMap come tabella hash.
3. Proteggi/#remove() con un lucchetto.
4. Rende volatile il campo "successivo".

In iterazione, non è necessario alcun blocco in quanto è possibile seguire in sicurezza il campo "successivo". Le letture possono essere bloccate semplicemente delegando al CHM su un #get().

Answer 4

Fino ad ora, il mio progetto ha utilizzato LRUMap da Apache Collections ma è basato su SequencedHashMap. Le raccolte propongono lo ListOrderedMap ma nessuno è sicuro per i thread.

Sono passato a MapMaker da Google Guava. Puoi anche guardare allo CacheBuilder.

Answer 5

Quindi, la risposta più semplice sarebbe quella di utilizzare un fornitore di chiavi monotonicamente crescente su cui funziona il vostro Comparator. Pensa allo AtomicInteger e ogni volta che inserisci, crei una nuova chiave da utilizzare per i confronti. Se si raggruppa la propria chiave reale, è possibile creare una mappa interna di 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; 
    } 


} 

Ciò ovviare alla necessità di un comparatore personalizzato, e vi darà (1) il metodo per calcolare dimensioni (a meno che non si consente rimuove, nel qual caso, contare quelle pure, in modo da poter semplicemente sottrarre una bella O "tutti i rimossi con successo" da "tutti gli add. riusciti", dove con successo si è effettivamente creata o rimossa una voce).