java - 实现非阻塞线程安全列表

Question

是否可以使用 ConcurrentHashMap 作为支持来实现非阻塞线程安全列表，其中使用索引作为键，元素作为值？

Answer 1

可能吗？

答案是，这取决于您需要什么列表功能。

• 如果您只是想在“列表”上执行类似数组的操作(例如，获取或设置给定索引处的元素)，那么就可以完成。

• 如果您想要执行诸如插入或删除元素或按顺序迭代列表元素之类的操作，则该操作必须是阻塞的，并且通常会很昂贵。

为了说明这一点，请考虑在位置 P 处插入元素的问题。为此，您需要更改 P 及以后所有现有元素的位置。对于每一个，您需要从 HashMap 中删除该元素，然后重新插入它。假设随机选择 P，则重新编号为 O(N)，其中 N 是“列表”长度。此外，重新编号必须以原子方式完成，因此它必须阻塞其他操作......相当长的时间。