在Java中，
这两种数据结构的多线程方面是否相同？
ConcurrentHashMap用于实现更好的多线程解决方案。那么我什么时候应该使用ConcurrentSkipListMap呢？这是一种多余的做法吗？这两种数据结构的多线程方面是否相同？
6个回答
84
这两个类在某些方面有所不同。
ConcurrentHashMap在其合同中未保证其操作的运行时间。同时，它允许为特定负载因子（大致上是同时修改它的线程数）进行调整。
另一方面，ConcurrentSkipListMap保证广泛操作的平均O(log(n))性能。它也不支持为了并发而进行调整。 ConcurrentSkipListMap还有一些ConcurrentHashMap没有的操作：ceilingEntry/Key、floorEntry/Key等。它还维护一个排序顺序，如果你使用ConcurrentHashMap，则需要计算（付出显著的代价）。
基本上，为不同的用例提供了不同的实现。 如果您需要快速添加单个键/值对和快速查找单个键，则使用HashMap。 如果您需要更快的有序遍历，并且可以承担插入的额外成本，则使用SkipListMap。
*虽然我预计实现大致符合一般哈希映射的保证：O(1)插入/查找；忽略重新哈希。
- Kevin Montrose
6
好的。Log(n) 是可以接受的，但 ConcurrentSkipListMap 是否空间有效呢？ - DKSRathore
1跳表比哈希表必然更大，但ConcurrentHashMap的可调性使得构建一个比等效的ConcurrentSkipListMap更大的哈希表成为可能。一般来说，我预计跳表会更大，但数量级相同。 - Kevin Montrose
它也不支持为了并发而进行调整。为什么？这有什么关联吗？ - Pacerier
2@Pacerier - 我的意思不是说它支持调整并发性能，而是说它不允许你调整影响其并发性能的参数（而ConcurrentHashMap则可以）。 - Kevin Montrose
@KevinMontrose 我明白了，你的意思是“它也不支持并发调整”。 - Pacerier
我觉得很奇怪，每个人都喜欢在没有必要的空间的情况下比较时间复杂度。跳表（SkipLists）具有更高的内存效率（这是值得注意的一点）。 - Robert
18
已排序，可导航和并发
有关数据结构的定义，请参见跳表。
ConcurrentSkipListMap 按其键的自然顺序（或您定义的其他键顺序）存储 Map。因此，它的 get/put/contains 操作速度比 HashMap 慢，但为了弥补这一点，它支持 SortedMap、NavigableMap 和 ConcurrentNavigableMap 接口。
- Jim Ferrans
13
那么什么时候应该使用ConcurrentSkipListMap？
当你需要保持键按顺序排列和/或需要可导航映射的第一个/最后一个，头/尾和子映射功能时。
ConcurrentHashMap类实现了ConcurrentMap接口，ConcurrentSkipListMap也实现了这个接口。但是如果你还想要SortedMap和NavigableMap的行为，则应该使用ConcurrentSkipListMap。
ConcurrentHashMap
- ❌ 排序
- ❌ 可导航
- ✅ 并发
ConcurrentSkipListMap
- ✅ 排序
- ✅ 可导航
- ✅ 并发
以下表格指导您了解Java 11中捆绑的各种Map实现的主要特点。点击/轻触可放大。
请注意，您可以从其他来源（如Google Guava）获取其他Map实现和类似的数据结构。
- Basil Bourque
2
这张图片很棒。你是否有类似的图片适用于普通集合和并发集合中的一些或全部？ - AnV
1@Anv 谢谢，制作那张图表花费了相当多的工作。它是我为Java用户组准备的演示文稿的一部分：Java Maps地图。而且，不，我只做了另一个类图用于
String相关的类和接口。 - Basil Bourque9
就性能而言，当skipList用作Map时，似乎要慢10-20倍。以下是我的测试结果（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
此外，比较两个集合的用例也很重要。使用这两种集合来实现最近最少使用（LRU）缓存的功能。现在跳表的效率看起来更加可疑。
MyBenchmark.hashMap_put1000_lru avgt 5 0.032 ? 0.001 s/op
MyBenchmark.skipListMap_put1000_lru avgt 5 3.332 ? 0.124 s/op
这里是 JMH 的代码（作为 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);
}
}
}
}
- Xtra Coder
6
2我认为应该将ConcurrentSkipListMap与它们的非并发对应物TreeMap进行比较。 - abbas
2正如阿巴斯所评论的那样，将性能与ConcurrentHashMap进行比较似乎有些愚蠢。ConcurrentSkipListMap的目的是(a)提供并发性和(b)在键之间维护排序顺序。ConcurrentHashMap可以实现a，但不具备b。将特斯拉和垃圾车的0到60速度进行比较是毫无意义的，因为它们服务于不同的目的。 - Basil Bourque
1当您不知道性能指标时，您就不知道哪个是特斯拉，哪个是“倒垃圾车” :) 另外...如果没有指标，您也不知道“b”的价格。因此-比较性能通常是一件有用的事情。 - Xtra Coder
1也许可以加一个与树图的比较！ :D - simgineer
跳表比较节省内存。对我来说，这比查找中的几毫秒更重要。 - Robert
对于一个专为并发访问而设计的数据结构进行性能基准测试只使用单线程会感觉有些奇怪。如果使用更多的线程（即使只是
-tc 1,2,4,8 来查看在 1、2、4、8 线程下的性能），这将更加有趣。我预计并发哈希映射表（即使使用默认配置）将击败并发跳表映射表，但垂直可扩展性曲线可能会很有趣。 - Alec1
根据工作负载，如果需要范围查询，则ConcurrentSkipListMap可能比具有同步方法的TreeMap慢，例如KAFKA-8802。
- Anurag Sharma
1
谢谢分享。我正在考虑在我的一个项目中将TreeMap替换为ConcurrentSkipListMap，所以了解这一点很好！您是否有更多关于为什么ConcurrentSkipListMap较慢的上下文，并且有关性能比较的更多细节？ - yusong
0
ConcurrentHashMap：当您需要多线程索引式的get/put时，只支持索引式操作。Get/Put的时间复杂度为O(1)。
ConcurrentSkipListMap：除了get/put之外，还有更多的操作，例如按键排序的前/后n个项目、获取最后一个条目、按键排序获取/遍历整个映射等。时间复杂度为O(log(n))，因此put性能不如ConcurrentHashMap。它是使用SkipList实现的ConcurrentNavigableMap。
总之，当您需要在地图上执行更多需要排序功能的操作而不仅仅是简单的get和put时，请使用ConcurrentSkipListMap。
- spats
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接