Quand devrais-je utiliser ConcurrentSkipListMap?

Question

En Java, ConcurrentHashMap est présent pour une meilleure solution multithreading . Alors quand devrais-je utiliser ConcurrentSkipListMap ? Est-ce une redondance?

Les aspects multithreading entre ces deux aspects sont-ils communs?

Answer 1

Ces deux classes varient de plusieurs manières.

ConcurrentHashMap fait ne pas garantir * la durée d'exécution de ses opérations dans le cadre de son contrat. Il permet également d’ajuster certains facteurs de charge (en gros, le nombre de threads qui le modifient simultanément).

ConcurrentSkipListMap , sur le D'autre part, garantit des performances moyennes en O (log (n)) sur une grande variété d'opérations. En outre, il ne prend pas en charge le réglage pour des raisons de concurrence. ConcurrentSkipListMap comporte également un certain nombre d'opérations que ConcurrentHashMap ne fait pas: ceilingEntry / Key, floorEntry / Key, etc. Il conserve également un ordre de tri, qui devrait sinon être calculé (à un coût notable) si vous utilisiez un ConcurrentHashMap .

En principe, différentes implémentations sont fournies pour différents cas d'utilisation. Si vous avez besoin d'ajouter rapidement une paire clé / valeur unique et de rechercher une clé unique, utilisez HashMap . Si vous avez besoin d'une traversée dans l'ordre plus rapide et que vous pouvez vous permettre un coût supplémentaire pour l'insertion, utilisez SkipListMap .

_{* Bien que je s’attende à ce que l’implémentation soit à peu près conforme aux garanties générales de la carte de hachage de l’insertion / recherche O (1); ignorer le re-hachage}

Answer 2

Voir Ignorer la liste pour une définition de la structure de données. ConcurrentSkipListMap stocke la carte dans l'ordre naturel de ses clés (ou dans un autre ordre de clés que vous définissez). Donc, il aura des opérations get / put / contient plus lentes qu’un HashMap, mais pour compenser cela, il supporte les interfaces SortedMap et NavigableMap.

Answer 3

En termes de performances, skipList lorsqu'il est utilisé en tant que carte - semble être 10 à 20 fois plus lent. Voici le résultat de mes tests (Java 1.8.0_102-b14, win 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

Et en plus de cela - le cas d’utilisation où comparer un à un autre a vraiment du sens. Implémentation du cache des éléments récemment utilisés en utilisant ces deux collections. Maintenant, l'efficacité de skipList semble être plus discutable.

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

Voici le code pour JMH (exécuté en tant que java -jar cible / 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);
            }
        }
    }
}

Answer 4

ConcurrentHashMap: lorsque vous voulez obtenir / mettre en place un index multithread, seules les opérations basées sur un index sont prises en charge. Get / Put are of O (1)

ConcurrentSkipListMap: Plus d'opérations que juste obtenir / mettre, comme trier les n premiers / derniers éléments par clé, obtenir la dernière entrée, récupérer / traverser la carte entière triée par clé, etc. La complexité est de O (log (n)), donc les performances ne sont pas aussi bonnes que ConcurrentHashMap. Ce n'est pas une implémentation de ConcurrentNavigableMap avec SkipList.

Pour résumer, utilisez ConcurrentSkipListMap lorsque vous souhaitez effectuer plus d'opérations sur la carte nécessitant des fonctionnalités triées plutôt que de simples opérations d'obtention et de mise.