java - 只访问一次 ConcurrentHashMap<Element, Boolean> 的每个元素的可扩展方式

Question

我有 32 个机器线程和一个 ConcurrentHashMap<Key,Value> map ，其中包含很多键。 Key 定义了一个公共(public)方法 visit() 。我想使用我可用的处理能力和可能的某种线程池对 map 的每个元素进行一次 visit()。

我可以尝试的事情:

我可以使用 map.keys() 方法。生成的 Enumeration<Key> 可以使用 nextElement() 进行迭代，但由于对 key.visit() 的调用非常简短，我无法让线程保持忙碌。枚举本质上是单线程的。

我可以使用同步的 HashSet<Key> 代替，调用方法 toArray() 并将数组上的工作拆分为所有 32 个线程。我严重怀疑这个解决方案，因为 toArray() 方法很可能是单线程瓶颈。

我可以尝试从 ConcurrentHashMap 继承，获取其内部 Segment<K,V> 的实例，尝试将它们分成 32 个组并分别处理每个组。不过，这听起来像是一种硬核方法。

或类似的魔法与 Enumeration<Key> 。

理想情况下:

理想情况下，ConcurrentHashMap<Key, Value> 将定义一个方法 keysEnumerator(int approximatePosition) ，这可能会给我一个缺少大约前 1/32 个元素的枚举器，即 map.keysEnumerator(map.size()/32)

我错过了什么明显的东西吗？有没有人遇到过类似的问题？

编辑

我尝试了分析，看看这个问题是否真的会影响实践中的性能。由于我目前无法访问集群，因此我使用笔记本电脑并尝试将结果外推到更大的数据集。在我的机器上，我可以创建一个 200 万个键 ConcurrentHashMap，它需要大约 1 秒的时间来迭代它，在每个键上调用 visit() 方法。该程序应该扩展到 8500 万个 key (及更多)。集群的处理器稍微快一点，但它仍然需要大约 40 秒来迭代整个 map 。现在简单介绍一下程序的逻辑流程。呈现的逻辑是顺序的，即在上一步中的所有线程都完成之前，不允许任何线程进行下一步:

创建哈希映射，创建键并填充哈希映射

遍历访问所有键的整个哈希映射。

做一些数据混洗，即并行插入和删除。

重复步骤 2 和 3 几百次。

该逻辑流程意味着 40 秒的迭代将重复数百次，比如 100 次。这使我们 仅在访问节点上花费了一个多小时。使用一组 32 个并行迭代器，它可以缩短到几分钟，这是一个显着的性能改进。

现在谈谈 ConcurrentHashMap 的工作原理(或者我认为它是如何工作的)。每个 ConcurrentHashMap 由段组成(默认为 16)。对哈希映射的每次写入都在相关段上同步。因此，假设我们试图将两个新键 k1 和 k2 写入哈希映射，并且它们将被解析为属于同一段，例如 s1。如果尝试同时写入它们，其中一个将首先获取锁，然后在另一个之前添加。两个元素被解析为属于同一段的机会是多少？如果我们有一个好的散列函数和 16 个段，它是 1/16。

我相信 ConcurrentHashMap 应该有一个方法 concurrentKeys() ，它会返回一个枚举数组，每个段一个。我有一些如何通过继承将它添加到 ConcurrentHashMap 的想法，如果我成功了，我会告诉你的。至于现在的解决方案似乎是创建一个 ConcurrentHashMaps 数组并预​​先散列每个键以解析为此类数组的一个成员。一旦准备好，我也会分享该代码。

编辑

这是不同语言中的相同问题:

Parallel Iterators

Answer 1

I could try to inherit from ConcurrentHashMap, get my hands on the instances of its inner Segment, try to group them into 32 groups and work on each group separately. This sounds like a hardcore approach though.

确实是铁杆，但我认为唯一可行的方法。 toArray() 通过进行枚举来构建数组，因此没有获胜。我不敢相信同步的 HashSet 会更好，除非 visit() 运行与其他 map 操作的比率非常高。

使用 Segment s 的问题是您必须非常小心您的代码是有弹性的，因为我假设其他线程可能会在您访问节点的同时更改表，并且您需要避免不可避免的竞争条件。精致是肯定的。

我心中最大的问题是这是否有必要？分析器或计时运行是否向您显示在一个线程中对每个键进行 visit() 花费的时间太长？您是否尝试为每个 visit() 调用做一个线程池，并让一个线程进行枚举，池线程执行 visit() ？