ComputeIfAbsent错误的映射大小

Question

我已经尝试了下面的代码，以便为每个jj有一个唯一的id。

据我所知，computeIfAbsent是线程安全的，但是:

public static void main(String[] args) throws InterruptedException {
ExecutorService executorService =
Executors.newFixedThreadPool(4);
final Map<String, ConcurrentHashMap<String, Short>> threadSafeMap = new ConcurrentHashMap<>();
threadSafeMap.put("0", new ConcurrentHashMap<>());
threadSafeMap.put("1", new ConcurrentHashMap<>());
for (int i = 1; i <= 10; i++) {
final int jj = i;
executorService.submit(() -> {
int                                key              = jj % 2;
final ConcurrentMap<String, Short> idByName = threadSafeMap.get(String.valueOf(key));
return idByName.computeIfAbsent(String.valueOf(jj), x -> (short) idByName.size());
});
}
executorService.shutdown();
executorService.awaitTermination(5, TimeUnit.SECONDS);
System.out.println(threadSafeMap);
}

实际值:{0 = {2 = 0, 4 = 0, 6 = 2, 8 = 3, 10 = 4}, 1 = {1 = 0, 3 = 0, 5 = 2, 7 = 3, 9 = 4}}

期望值例如(由于并发性):{0 = {2 = 0, 4 = 1, 6 = 2, 8 = 3, 10 = 4}, 1 = {1 = 1, 3 = 0, 5 = 2, 7 = 3, 9 = 4}}

的问题是，我有2=0和4=0，这是错误的值应该是唯一的!

btw使用整数代替短解决问题!你能帮帮我吗?

Answer 1

您的假设是错误的，因为许多不同的线程可能同时对不同的键执行相同的映射函数。

ConcurrentHashMap是线程安全的，但允许并发更新映射。一些正在访问底层映射表的类似部分的调用者可能会在等待另一个线程完成时阻塞。

您不会发现computeIfAbsent(someKey,mapFunc)对同一个键运行两次映射函数，因为它是对该键的原子操作。因此第二个或并发调用者将看到第一个调用的值。然而，另一个computeIfAbsent(anotherKey,mapFunc)可以在完全相同的时间运行，这就是为什么您的映射函数可能评估size()为多个键相同的值。

javadoc声明:

如果键不存在，则提供的函数在每次调用此方法时只调用一次，否则根本不调用。

当计算正在进行时，其他线程对该map的一些尝试更新操作可能会被阻塞，因此计算应该简短而简单。

如果你希望有唯一的值，你可以使用AtomicInteger计数器。

Answer 2

ConcurrentHashMap需要注意的是如何计算地图的大小:

public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] cs = counterCells;
long sum = baseCount;
if (cs != null) {
for (CounterCell c : cs)
if (c != null)
sum += c.value;
}
return sum;
}

这些"计数单元";在内部调用addCount时更新。在#computeIfAbsent方法的末尾，我们有:

if (val != null)
addCount(1L, binCount);
return val;

然而，在到达此代码之前，您传递的lambda表达式将已经在方法的前面计算过了。例如，当我们第一次添加值时，它们将在ReservationNode: 上同步。

Node<K,V> r = new ReservationNode<K,V>();
synchronized (r) {
if (casTabAt(tab, i, null, r)) { //compare-and-swap
binCount = 1;
Node<K,V> node = null;
try {
if ((val = mappingFunction.apply(key)) != null) //runs the mapping function
node = new Node<K,V>(h, key, val);
} finally {
setTabAt(tab, i, node);
}
}
}
}

src: ConcurrentHashMap # computeIfAbsent

上面的代码对我来说很可疑，并且让我认为在这里的创建阶段不会真正阻塞/同步。稍后在方法中(一旦表条目存在)，您将看到它执行synchronized(f)(散列桶)以计算/放置新值，然后导致您在上面看到的顺序插入。

因此，开始时的并发更新(当我们第一次初始化map时)不仅能够并行运行，而且即使有适当的同步，也可能在#computeIfAbsent调用结束之前为map的大小检索0。