java - 并行无锁升序 id 生成

Question

我有一个 map ，它应该将字符串与一个 id 相关联。 ID 之间必须不有间隔，并且它们必须是从 0 到 N 的唯一整数。

请求总是带有两个字符串，其中一个、两个或一个都可能已经被索引。该 map 是从 ForkJoin 池并行构建的，理想情况下我想避免显式同步块(synchronized block)。我正在寻找一种最佳方式来最大化带锁或不带锁的吞吐量。

我不知道如何使用 AtomicInteger 而不为 map 中已经存在的键按顺序创建间隙。

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() 解决。如果我对每个字符串盲目地这样做，序列中就会有间隙。需要复合 操作来检查 key 是否存在，然后才生成 id。我一直在寻找一种通过 Map API 实现此类复合操作的方法。

第二个提供的答案违背了我在问题中特别提出的要求。

Answer 1

没有办法完全按照您想要的方式进行操作 -- 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
}