1

目前，我有一个存储自定义节点类的 LinkedList。当前按顺序删除节点并进行评估，这通常会将更多节点添加回 LinkedList，将其视为队列。

但实际上我并不关心维护节点的顺序，因为它们被添加或删除的顺序并不重要。您可以从列表中删除第 1 个、第 54 个或第 1032 个节点，这没关系。重要的是节点正在被快速处理，这意味着一个被删除（随机），变异，然后连同它的几个变体一起添加回来（再一次，顺序无关紧要）。

由于我一直无法找到 Java Bag 实现，那么维护这种类型的集合最有效的方法是什么？提前致谢。

PS出于懒惰，我避免使用数组，因为理论上节点集合的大小范围可以从 1 个节点到 3^64 个节点，尽管它更有可能保持在一百万以下。

4

1 回答 1

1

JavaHashSet或TreeSet类型在这里可能很好，因为它们表示支持快速插入和删除元素的无序元素集合。也就是说，你不可能在内存中保存 3 64 个值，因为这大约是 3.4336838 × 10 30，这个数字远远大于我所知道的任何 RAM 可以容纳的数量。

编辑：根据所描述的用例（支持有效插入和删除随机元素），您可能希望采用这个较早的问题中描述的方法来构建一个可以做到这一点的数据结构。直观地说，您将使用 a ArrayList，然后通过将元素交换到 the 的末尾ArrayList并删除它们来删除它们。这使得 O(1) 插入和 O(1) 删除具有极低的开销。

希望这可以帮助！

于 2013-05-08T03:01:12.383 回答