我有一个映射，它应该将字符串与id关联起来。id之间必须有而不是间隙，并且它们必须是从0到N的唯一整数。
请求总是带有两个字符串，其中一个字符串、两个字符串或没有字符串可能已经被索引。该映射是从ForkJoin池并行构建的，理想情况下我希望避免显式同步块。我正在寻找一种优化的方式来最大限度地提高吞吐量，无论是否锁定。
我看不出如何在不按顺序为映射中已经存在的键创建间隙的情况下使用AtomicInteger。
public class Foo {
private final Map<String, Integer> idGenerator = new ConcurrentHashMap<>();
// invoked from multiple threads
public void update(String key1, String key2) {
idGenerator.dosomething(key, ?) // should save the key and unique id
idGenerator.dosomething(key2, ?) // should save the key2 and its unique id
Bar bar = new Bar(idGenerator.get(key), idGenerator.get(key2));
// ... do something with bar
}
}
我认为size()方法与merge()相结合可能会解决这个问题，但我不能完全说服自己。有人能提出解决这个问题的方法吗？
编辑
关于重复标志，这不能用链接答案中建议的AtomicInteger.incrementAndGet()来解决。如果我对每个字符串都盲目地这样做，那么序列中就会有间隙。需要复合操作来检查密钥是否存在，然后才生成id。我正在寻找一种通过MapAPI实现这种复合操作的方法。
提供的第二个答案违背了我在问题中特别提出的要求。
没有一种方法可以完全按照您想要的方式进行操作——ConcurrentHashMap本身并不是无锁的。但是，通过使用java.util.Map.computeIfAbsent函数，您可以在不必执行任何显式锁管理的情况下以原子方式执行此操作。
下面是一个代码示例，它与您所提供的样式一样，应该会让您开始工作。
ConcurrentHashMap<String, Integer> keyMap = new ConcurrentHashMap<>();
AtomicInteger sequence = new AtomicInteger();
public void update(String key1, String key2) {
Integer id1 = keyMap.computeIfAbsent(key1, s -> sequence.getAndIncrement());
Integer id2 = keyMap.computeIfAbsent(key2, s -> sequence.getAndIncrement());
Bar bar = new Bar(id1, id2);
// ... do something with bar
}
我不确定你能不能随心所欲。不过，您可以批处理一些更新，或者与枚举/添加分开进行检查。
很多答案都是假设顺序不重要：你需要所有给定数字的字符串，但即使在一对中重新排序也是可以的，对吧？并发可能已经导致对的重新排序，或者对的成员无法获得连续的数字，但重新排序可能会导致对中的第一个获得更高的数字。
延迟并没有那么重要。这个应用程序应该咀嚼大量的数据并最终产生输出。大多数时候，地图中应该有搜索命中
如果大多数搜索都命中，那么我们主要需要地图上的读取吞吐量。
一个编写器线程可能就足够了。
因此，并发读取器可以检查它们的输入，而不是直接添加到主映射中，如果不存在，则将它们添加到要枚举的队列中，并添加到主ConcurrentHashMap中队列可以是一个简单的无锁定队列，也可以是另一个ConCurrentHashMap，用于从尚未添加的候选中筛选重复项。但可能一个没有锁的队列是好的。
然后，您就不需要原子计数器，也不需要两个线程在看到相同的字符串时将计数器递增两次，然后再将其添加到映射中。(因为除此之外，这是一个大问题。)
如果有一种方法可以让编写器锁定ConcurrentHashMap，从而提高一批更新的效率，那就太好了。但是，如果命中率预计会很高，那么你真的希望其他阅读器线程在我们增长它的同时尽可能多地过滤重复内容，而不是暂停。
为了减少主前端线程之间的争用，可以有多个队列，比如每个线程都有一个生产者/消费者队列，或者在一对物理核心上运行的一组4个线程共享一个队列。
枚举线程从所有这些线程中读取。
在读卡器不与写入器争用的队列中，枚举线程没有争用。但是多个队列减少了写入程序之间的争用。(写入这些队列的线程是以只读方式访问主ConcurrentHashMap的线程，如果命中率很高，则大部分CPU时间将花费在该线程上。)
如果Java具有某种读拷贝更新(RCU)数据结构，则这种数据结构可能是好的。它可以让读者保持全速过滤掉重复项，而枚举线程在构建新表时构建一个新表，并完成一批插入，而没有争用。
在90%的命中率下，一个编写器线程可能能跟上10个左右的读取器线程，这些线程根据主表过滤新密钥。
您可能需要设置一些队列大小限制，以允许来自单个编写器线程的背压。或者，如果您的核心/线程比一个编写器能跟上的数量多得多，那么在编号之前，某种并发设置可以让多个线程消除重复，这可能会有所帮助。
或者说真的，如果你能等到最后再给所有的东西编号，我想这会简单得多。
我想也许可以在比赛条件下为失误留出空间，然后回去解决问题，但这可能不会更好。