在不使用循环的情况下随机获取HashMap或HashSet中的元素

Question

我有大约420,000个元素需要轻松地存储在Set或List中。但限制条件是我需要能够快速地随机选择一个元素。

最初，我使用了ArrayList和LinkedList，但是由于元素太多，速度非常慢。当我对其进行剖析时，我发现我存储的对象的equals()方法在很短的时间内被调用了大约2100万次。

接下来，我尝试了HashSet。虽然性能得到了提高，但我失去了功能：我无法随机选择一个元素。HashSet由HashMap支持，后者又由HashMap.Entry对象的数组支持。但是当我试图暴露它们时，我受到了整个Java Collections Framework疯狂的私有和包可见性的阻碍（即使复制和粘贴该类也不起作用，JCF非常“使用我们拥有的或自己开发”）。

在HashSet或HashMap中随机选择一个元素的最佳方法是什么？由于集合的大小，我希望不使用循环。

重要编辑：我忘记了一个非常重要的细节：我如何使用集合。我在表格开始时填充整个集合。在程序执行期间，我随机选择一个元素并将其删除，然后选择并删除几个已知的元素，然后重复此过程。这种不断查找和更改是导致速度缓慢的原因。

- TheLQ

---

equals() 方法什么时候被调用了？你通常对这个集合执行哪些操作？ - Bozho

有什么要求是你没有告诉我们的，需要你在一个数组列表上调用equals()方法吗？是唯一性吗，在添加之前先调用contains()方法？ - Mark Peters

我不禁注意到，2100万是420k的50倍。我敢打赌你有一个循环100次的循环，它会在整个数组上循环，直到找到你随机选择的元素，每次平均为210k。 - corsiKa

你所说的“随机选择一个元素”具体是什么意思？是随机选择一个元素吗？还是查找特定元素？或者是查找第n个元素？ - Frank

如果你只是按索引删除，这应该不是一个问题。 - Bozho

Answer 1

没有理由让一个ArrayList或LinkedList调用equals()方法...虽然你不需要LinkedList，因为你需要通过索引快速随机访问。

使用ArrayList应该是最理想的-使用适当的容量创建它，将所有项目添加到其中，然后您只需重复选择适当范围内的随机数字，并调用get(index)以获取相关值。

HashMap和HashSet对此根本不适用。

- Jon Skeet

---

我相信这是由于删除操作引起的。我在程序开头一次性添加了所有内容，然后不断使用 remove() 和 contains()。使用 ArrayList 和 LinkedList 时，两者都被调用了数百万次，速度非常慢。 - TheLQ

@TheLQ：为什么你之前没提到呢？你完全没有说过调用contains()或remove()，这两个方法都不是选取随机元素所必需的。你一定要调用remove()吗？如果你想要所有元素以随机顺序出现，但每个元素只出现一次，你可以使用Collections.shuffle来打乱列表 - 然后你就不需要在之后修改它了。 - Jon Skeet

@Jonathon @Mark 我使用 remove(int index) 选择所有随机元素。这样做可以同时完成我想要的两个功能：删除该元素并获取索引处的元素。之后多次使用 contains()。 - TheLQ

@TheLQ：但是为什么你需要删除元素，以及为什么你需要使用“contains”？当问题听起来我们只听到了你需求的三分之一时，很难回答这个问题... - Jon Skeet

@TheLQ：我认为没有必要删除这个问题。但是你仍然没有回答为什么需要删除该元素。如果您只是提前或随时移动元素，则可以获得不重复的随机元素序列 - 这是您尝试通过删除来实现的吗？（不，这不是“误读”问题的问题 - 最初编写的问题只是没有说明所有要求的问题。） - Jon Skeet

Answer 2

如果您所需的全部只是获取大量值并随机选择一个，则ArrayList（字面上）非常适合您的需求。除非您直接使用基元数组（这里会失去抽象的好处），否则速度不会显著提高。

如果这对您来说太慢了，那是因为您还在使用其他操作。如果您在问题中更新所有集合必须服务的操作，您将得到更好的答案。

- corsiKa

Answer 3

如果你不调用contains()（这将多次调用equals()），你可以使用ArrayList.get(randomNumber)，这将是O(1)

你不能使用HashMap - 它在内部的数组中存储对象，其中索引=对象的哈希码。即使你有那个表，你也需要猜测哪些桶包含对象。因此，HashMap不适用于随机访问。

- Bozho

---

我确实多次调用contains()，除了那一行代码ArrayList.get(ranodmNumber)。 - TheLQ

Answer 4

假设你的equals()调用是因为你使用contains()来去重，那么你可能想要保留一个HashSet(用于快速查找是否已经存在)和一个ArrayList(用于快速随机访问)。或者，如果操作不交错，可以先建立一个HashSet，然后用toArray()提取它的数据，或者用后者的构造函数将其转换为ArrayList。

如果你的问题是由ArrayList上的remove()调用导致的，请不要使用它，而应该：

1. 如果你删除的不是最后一个元素，只需使用set()将被删除的元素替换为最后一个元素；
2. 将列表大小缩小1。

这当然会破坏元素顺序，但根据描述，显然你不需要它。或者，你遗漏了另一个重要细节吗？

- user319799

---

作为保持并行 ArrayList 的副作用，删除操作至少需要 O(n)。 - Mark Peters

一开始没有提到remove()。 - user319799