java - Arraylist vs Array 用于查找元素？

Question

在性能方面，这是查找元素的最有效方法。假设我有 100 根弦。我需要查找指定的字符串是否在这些批量字符串中可用。我在 Arraylist 中有 contains() 方法，但出于同样的目的，我需要遍历 Array。任何人都可以解释一下，这是在性能方面做到这一点的最佳方式。

Answer 1

Say I have 100's of strings. I need to find whether a specified string is available in those bulk strings.

听起来你想要一个 HashSet<String> - 不是列表或数组。至少，如果每次要搜索的数百个字符串都是相同的，情况就是如此。如果您每次都在一组不同的字符串中进行搜索，那么如果您以任意顺序接收该组，您将不会比 O(N) 做得更好。

一般来说，检查列表/数组中的包含是一个 O(N) 操作，而在基于散列的数据结构中它是 O(1)。当然，还有执行散列和相等性检查的成本，但那是另一回事。

另一种选择是排序列表，其复杂度为 O(log N)。

如果您关心顺序，您可能需要考虑 LinkedHashSet<String> ，它保持插入顺序但仍然具有 O(1) 访问权限。 (它基本上是一个链表结合了一个哈希集。)