2

我有这个地图定义：

TreeMap <String, Set<Integer>>

它可能包含数百万个条目，而且我还需要一个“自然顺序”（这就是我选择 TreeMap 的原因，尽管如果需要我可以编写一个 Comparator）。

因此，为了向地图添加元素，我必须做的是：

  1. 检查密钥是否已经存在。
  2. 如果没有，请创建一个新 Set 并添加该值。
  3. 如果存在，我必须将值添加到 Set

我有这个工作正常的实现：

private void addToMap (String key, Integer value){
    Set<Integer> vs = dataMap.get(key);
    if (vs == null){
        vs = new TreeSet<Integer>();
        dataMap.put(key,vs);
    }
    vs.add(value);
}

但是我想避免搜索键，然后如果它不存在则放置元素（它将在巨大的地图上执行新的搜索）。

我想我可以使用ConcurrentHashMap.putIfAbsent方法，但是：

  1. 我不会有键的自然排序（我需要对数百万个键执行排序）
  2. 由于 ConcurrentHashMap 上的同步，我可能会有（我不知道）额外的开销，在我的情况下，我的进程是单线程的，它可能会影响性能。

阅读这篇文章：Java map.get(key) - 如果 key 不存在，自动执行 put(key) 并返回？ 有一个关于番石榴的答案，MapMaker.makeComputingMap但看起来该方法不再存在。

在这种情况下，性能至关重要（一如既往：D），所以请告诉我您的建议。

提前致谢。

注意： 非常感谢您在几分钟内提供了如此多的帮助答案。（我不知道选哪个最好）。

我将对建议（TreeMultiMap、ConcurrentSkipListMap、TreeSet + HashMap）进行一些性能测试并更新结果。然后我会选择性能最好的一个，因为我想选择所有三个但我不能。

笔记2

因此，我对 150 万个条目进行了一些性能测试，结果如下：

  • ConcurrentSkipListMap，它没有像我预期的那样工作，因为它用我提供的新空集替换了现有值。我认为只有在密钥不存在时才设置值，所以我不能使用这个。（我的错）。

  • TreeSet + HashMap，工作正常，但不能提供最佳性能。它比单独的 TreeMap 或 TreeMultiMap 慢 1.5 倍。

  • TreeMultiMap 提供了最好的性能，但它与单独的 TreeMap 几乎相同。我会检查这个作为答案。

再次感谢您的贡献和帮助。

4

3 回答 3

2

如果性能很关键，我不会使用整数 TreeSet，我会找到更轻量级的结构，如 TIntArrayList 或包装int值的东西。我也会使用 HashMap，因为它的查找是 O(1) 而不是 O(log N)。如果您还需要对键进行排序，我会为此使用第二个集合。

我同意 ConcurrentHashMap 上的 putIfAbsent 太过分了，而在 HashMap 上获取/放置可能是最快的选择。

ConcurrentSkipListMap 可能是使用 putIfAbsent 的一个不错的选择，但我会确保它不会变慢。

顺便说一句，比做一个 get/put 更糟糕的是创建一个你不需要的 HashSet。

于 2013-11-08T11:50:57.200 回答
2

PutIfAbsent 有并发的好处，就是：如果很多线程同时调用这个，就不用等待了（内部不使用同步）。然而，这会以很小的执行速度为代价，所以如果你只工作单线程，这会减慢速度。

如果您需要这种排序，请尝试ConcurrentSkipListMap。

于 2013-11-08T11:51:18.513 回答
2
  • 并发映射不会做任何事情，它会检查是否存在，如果不存在则插入。
  • Guava 有 MultiMaps，例如TreeMultiMap可以是你需要的。
于 2013-11-08T11:54:09.847 回答