2009-11-28 15 views
61

In Java, ConcurrentHashMap è disponibile per una soluzione migliore multithreading. Allora quando dovrei usare ConcurrentSkipListMap? È una ridondanza?Quando dovrei usare ConcurrentSkipListMap?

Gli aspetti di multithreading tra questi due sono comuni?

risposta

57

Queste due classi variano in alcuni modi.

ConcurrentHashMap non garantisce * il runtime delle sue operazioni come parte del suo contratto. Permette anche la messa a punto di determinati fattori di carico (all'incirca, il numero di thread che lo modificano contemporaneamente).

ConcurrentSkipListMap, d'altra parte, garantisce prestazioni O (log (n)) su una vasta gamma di operazioni. Inoltre non supporta l'ottimizzazione per la concorrenza. ConcurrentSkipListMap ha anche un numero di operazioni che ConcurrentHashMap non include: ceilingEntry/Key, floorEntry/Key, ecc. Mantiene anche un ordinamento, che altrimenti dovrebbe essere calcolato (a spese considerevoli) se si stesse utilizzando uno ConcurrentHashMap.

In sostanza, vengono fornite diverse implementazioni per diversi casi d'uso. Se è necessaria l'aggiunta rapida di una singola chiave/coppia di valori e la ricerca rapida della chiave singola, utilizzare HashMap. Se hai bisogno di una traversata in ordine più veloce e puoi permetterti il ​​costo aggiuntivo per l'inserimento, usa lo SkipListMap.

* Anche se mi aspetto che l'implementazione sia approssimativamente in linea con le garanzie generali di hash-map di O (1) inserimento/ricerca; ignorando ri-hashing

+0

Ok. Log (n) va bene ma ConcurrentSkipListMap è efficiente nello spazio? – DKSRathore

+1

Gli elenchi di salto sono necessariamente più grandi di Hashtables, ma la natura sintonizzabile di ConcurrentHashMap consente di costruire un Hashtable che è maggiore dell'equivalente ConcurrentSkipListMap. In generale, mi aspetto che l'elenco dei salti sia più grande ma dello stesso ordine di grandezza. –

+0

"Inoltre non supporta l'ottimizzazione per la concorrenza" .. Perché? Qual è il link? – Pacerier

12

Vedere Skip List per una definizione della struttura dati. Una ConcurrentSkipListMap memorizza la mappa nell'ordine naturale delle sue chiavi (o in un altro ordine chiave definito dall'utente). Quindi avrà operazioni di get/put/contiene più lente di una HashMap, ma per compensare ciò supporta le interfacce SortedMap e NavigableMap.

3

In termini di prestazioni, skipList quando viene utilizzato come Mappa - sembra essere 10-20 volte più lento. Ecco il risultato del mio test (Java 1.8.0_102-B14, vincere x32)

Benchmark     Mode Cnt Score Error Units 
MyBenchmark.hasMap_get  avgt 5 0.015 ? 0.001 s/op 
MyBenchmark.hashMap_put  avgt 5 0.029 ? 0.004 s/op 
MyBenchmark.skipListMap_get avgt 5 0.312 ? 0.014 s/op 
MyBenchmark.skipList_put  avgt 5 0.351 ? 0.007 s/op 

E in aggiunta a questo - utilizzare caso in cui il confronto uno-a-un altro fa davvero senso. Implementazione della cache degli ultimi oggetti usati di recente usando entrambe queste collezioni. Ora l'efficienza di skipList sembra essere un evento più dubbio.

MyBenchmark.hashMap_put1000_lru  avgt 5 0.032 ? 0.001 s/op 
MyBenchmark.skipListMap_put1000_lru avgt 5 3.332 ? 0.124 s/op 

Qui è il codice per JMH (eseguito come java -jar target/benchmarks.jar -bm avgt -f 1 -wi 5 -i 5 -t 1)

static final int nCycles = 50000; 
static final int nRep = 10; 
static final int dataSize = nCycles/4; 
static final List<String> data = new ArrayList<>(nCycles); 
static final Map<String,String> hmap4get = new ConcurrentHashMap<>(3000, 0.5f, 10); 
static final Map<String,String> smap4get = new ConcurrentSkipListMap<>(); 

static { 
    // prepare data 
    List<String> values = new ArrayList<>(dataSize); 
    for(int i = 0; i < dataSize; i++) { 
     values.add(UUID.randomUUID().toString()); 
    } 
    // rehash data for all cycles 
    for(int i = 0; i < nCycles; i++) { 
     data.add(values.get((int)(Math.random() * dataSize))); 
    } 
    // rehash data for all cycles 
    for(int i = 0; i < dataSize; i++) { 
     String value = data.get((int)(Math.random() * dataSize)); 
     hmap4get.put(value, value); 
     smap4get.put(value, value); 
    } 
} 

@Benchmark 
public void skipList_put() { 
    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentSkipListMap<>(); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      map.put(key, key); 
     } 
    } 
} 

@Benchmark 
public void skipListMap_get() { 
    for(int n = 0; n < nRep; n++) { 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      smap4get.get(key); 
     } 
    } 
} 

@Benchmark 
public void hashMap_put() { 
    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      map.put(key, key); 
     } 
    } 
} 

@Benchmark 
public void hasMap_get() { 
    for(int n = 0; n < nRep; n++) { 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      hmap4get.get(key); 
     } 
    } 
} 

@Benchmark 
public void skipListMap_put1000_lru() { 
    int sizeLimit = 1000; 

    for(int n = 0; n < nRep; n++) { 
     ConcurrentSkipListMap<String,String> map = new ConcurrentSkipListMap<>(); 

     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      String oldValue = map.put(key, key); 

      if((oldValue == null) && map.size() > sizeLimit) { 
       // not real lru, but i care only about performance here 
       map.remove(map.firstKey()); 
      } 
     } 
    } 
} 

@Benchmark 
public void hashMap_put1000_lru() { 
    int sizeLimit = 1000; 
    Queue<String> lru = new ArrayBlockingQueue<>(sizeLimit + 50); 

    for(int n = 0; n < nRep; n++) { 
     Map<String,String> map = new ConcurrentHashMap<>(3000, 0.5f, 10); 

     lru.clear(); 
     for(int i = 0; i < nCycles; i++) { 
      String key = data.get(i); 
      String oldValue = map.put(key, key); 

      if((oldValue == null) && lru.size() > sizeLimit) { 
       map.remove(lru.poll()); 
       lru.add(key); 
      } 
     } 
    } 
} 
Problemi correlati