java - Java HashSet 与数组性能

Question

我有一个保证是不同的对象的集合（特别是，由唯一的整数 ID 索引）。我也确切地知道其中有多少（并且数量不会改变），并且想知道 Array 在存储/检索所述元素方面是否会比 HashSet 具有显着的性能优势。

在纸面上，Array 保证了恒定的时间插入（因为我提前知道了大小）和检索，但是 HashSet 的代码看起来更干净并且增加了一些灵活性，所以我想知道使用它是否会丢失任何性能方面的东西，至少在理论上。

Answer 1

取决于您的数据；

HashSet为您提供O(1)contains() 方法，但不保留顺序。

ArrayListcontains() 是O(n)，但您可以控制条目的顺序。

Array如果您需要在两者之间插入任何内容，最坏的情况可能是 O(n)，因为您必须将数据向下移动并为插入腾出空间。中Set，可以直接使用SortedSet which too has O(n) too but with flexible operations.

我相信 Set 更灵活。

Answer 2

选择很大程度上取决于你想用它做什么。

如果这是您的问题中提到的：

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

如果这是您需要做的，那么您不需要它们。Collection中有一个 size() 方法，您可以通过该方法获取它的大小，这意味着集合中有多少个。

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

首先，我相信有一个公平的比较，你应该考虑使用 ArrayList 而不是 Array，你不需要处理重新分配。

然后它成为 ArrayList 与 HashSet 的选择，这很简单：

你需要一个列表或集合吗？它们有不同的用途：列表为您提供索引访问，迭代按索引顺序排列。虽然 Sets 主要是为了让您保留一组不同的数据，但鉴于其性质，您将没有索引访问权限。

在您决定使用 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)。

还有很多操作可以做，不知道要做什么就讨论性能是没有意义的。

Answer 3

理论上，正如 SCJP6 学习指南所说：D

数组比集合快，并且如前所述，大多数集合主要依赖于数组（Maps 不被认为是 Collection，但它们包含在 Collections 框架中）

如果您保证元素的大小不会改变，为什么会卡在基于对象构建的对象（基于数组构建的集合）中，而您可以直接使用根对象（数组）

Answer 4

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

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

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