java - 使用巨大的 map (putIfAbsent)

Question

我有这个 map 定义:

TreeMap <String, Set<Integer>>

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

所以，为了向 map 添加元素，我必须做的是:

1. 检查 key 是否已存在。
2. 如果不是，则创建一个新的 Set 并添加值。
3. 如果存在，我必须将值添加到集合中

我有这个运行良好的实现:

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);
}

但我想避免搜索键然后在元素不存在时放置该元素(它将在巨大的 map 上执行新的搜索)。

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

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

阅读这篇文章:Java map.get(key) - automatically do put(key) and return if key doesn't exist?有一个关于 Guava MapMaker.makeComputingMap 的答案，但看起来该方法已不复存在。

在这种情况下性能至关重要(一如既往:D)，所以请让我知道您的建议。

提前致谢。

注意:非常感谢您在短短几分钟内提供这么多有用的答案。(我不知道选哪个最好)。

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

注2

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

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

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

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

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

Answer 1

• Concurrent map 不会变魔术，它会检查是否存在，如果不存在则插入。
• Guava 有 MultiMaps，例如 TreeMultiMap 可以满足您的需要。