Java HashSet与数组的性能对比

Question

我有一个对象集合，保证各不相同（特别是按唯一整数ID索引）。我也知道它们的确切数量（数量不会改变），想知道对于存储/检索这些元素，Array是否比HashSet具有明显的性能优势。

在理论上，Array保证了常数时间插入（因为我提前知道大小）和检索，但HashSet的代码更加清晰简洁，并且增加了一些灵活性，所以我想知道是否在性能方面失去了什么，至少从理论上来说。

- donnyton

---

你的数据集是稀疏的还是密集的？ - Oliver Charlesworth

HashSet旨在具有预期的常数时间“添加”，“包含”和“删除”操作，这意味着时间不会因集合中有多少元素而发生太大变化。数组对于所有这些都有线性操作，但开销较低。这意味着对于小型集合，数组通常会更好。我不久前在我的机器上进行了一些ArraySet实现测试，并发现在大约150个元素以下使用数组而不是哈希通常更好（但这有点取决于实现和操作：例如迭代速度要快得多）。 - Ghostkeeper

这个问题有很多不同的意见。请参考以下链接：http://www.javacodegeeks.com/2010/08/java-best-practices-vector-arraylist.html 和 http://www.ibm.com/developerworks/library/j-jtp02183/。 - sathish_at_madison

根据您拥有的项目数量，EnumSet或类似的东西可能是一个选项。 - Viktor Seifert

请查看https://dev59.com/aWkw5IYBdhLWcg3wBV7j。 - Aliti

Answer 1

取决于你的数据；

HashSet提供了一个O(1)的contains()方法但不保留顺序。

ArrayList的contains()是O(n)，但是你可以控制条目的顺序。

Array如果你需要在其中插入任何东西，最坏的情况可能是O(n)，因为你必须向下移动数据并为插入腾出空间。在Set中，你可以直接使用SortedSet，它也具有O(n)，但具有灵活的操作。

我相信Set更加灵活。

- JNL

---

但是 TreeSet（SortedSet 的实现）具有对数时间复杂度的插入/查找能力... - Oliver Charlesworth

@OliCharlesworth 谢谢。我强调了集合比数组更具灵活性的观点。 - JNL

Answer 2

选择完全取决于你想用它做什么。

如果你需要的是你问题中提到的内容：

我有一组保证不同的对象（特别是由唯一整数ID索引），我也知道确切地有多少个它们。

如果这正是你需要做的事情，那么你两者都不需要。集合中有一个size()方法，可以获取其大小，这意味着集合中有多少个对象。

如果你所说的“对象集合”并不是真正的集合，并且你需要选择一种类型的集合来存储你的对象以进行进一步处理，那么你需要知道，对于不同类型的集合，有不同的功能和特点。

首先，我认为为了公平比较，你应该考虑使用ArrayList而不是Array，因为你不需要处理重新分配问题。

然后就变成了ArrayList与HashSet的选择，这很直观：

你需要List还是Set？它们是为不同的目的而设计的：列表提供索引访问，迭代按索引顺序进行。而集合主要用于保持一组不同的数据，并且根据其性质，你将没有索引访问。

在你决定使用List或Set之后，就是选择List/Set实现，通常对于Lists，你可以从ArrayList和LinkedList中选择，而对于Sets，你可以在HashSet和TreeSet之间进行选择。

所有的选择都取决于你想用那个数据集合做什么。它们在不同的操作中表现不同。

例如，在ArrayList中进行索引访问是O（1），在HashSet中（虽然没有意义）是O（n），（只是为了你的兴趣，在LinkedList中是O（n），在TreeSet中是O（nlogn））。

对于添加新元素，ArrayList和HashSet都是O（1）操作。在ArrayList中插入中间是O（n）的操作，而在HashSet中则没有意义。它们两个都会受到重新分配的影响，并且它们两个都需要O（n）来重新分配（HashSet通常在重新分配时更慢，因为它涉及到再次计算每个元素的哈希值）。

要查找某个元素是否存在于集合中，ArrayList是O（n），而HashSet是O（1）。

还有很多其他的操作可以进行，所以在不知道你想做什么的情况下，讨论性能是相当无意义的。

- Adrian Shum

Answer 3

理论上来说，正如SCJP6学习指南所说的那样：数组比集合更快。而且，大多数集合主要依赖于数组（虽然Map不被视为集合，但它们包含在集合框架中）。

如果您保证元素的大小不会改变，为什么要陷入基于对象构建的对象（基于数组构建的集合）中呢？而不是直接使用根对象（数组）。

- Ahmed Adel Ismail

---

因为如果你需要O(1)的查找（包含），你将需要编写大量非平凡的代码。这种情况下，问题就变成了：为什么要重复造轮子呢？ - assylias

如果我需要存储5个字符串常量并在其中一个循环中解析它们，根据上面的评论，我认为数组更合适。请告诉我。 - srinivas

Answer 4

看起来你需要一个HashMap，将id映射到计数。特别是，

HashMap<Integer,Integer> counts=new HashMap<Integer,Integer>();
counts.put(uniqueID,counts.get(uniqueID)+1);

通过这种方式，您可以获得摊销的O(1)添加、包含和检索。本质上，具有每个对象关联的唯一ID的数组就是HashMap。通过使用HashMap，您还可以获得额外的好处，即无需管理数组的大小，也无需自己将键映射到数组索引，并且具有恒定的访问时间。

- anguyen

---

或者使用 HashSet，如果他使用的对象具有返回其唯一标识符的 hashCode 方法。请注意，实际上这几乎没有什么变化，因为 HashSet 在内部使用了 HashMap 的一个实例... - Nicolas Rinaudo