1

就性能而言，这是查找元素的最有效方法。假设我有 100 根弦。我需要查找这些批量字符串中是否有指定的字符串。我在 Arraylist 中有 contains() 方法，但出于相同目的我需要遍历 Array。任何人都可以解释，就性能而言，这是最好的方法。

4

4 回答 4

19

假设我有 100 根弦。我需要查找这些批量字符串中是否有指定的字符串。

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

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

另一种选择是排序列表，即 O(log N)。

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

于 2013-09-04T15:07:26.400 回答
4

AnArraylist使用数组作为支持数据，因此两者的性能相同

于 2013-09-04T15:07:17.123 回答
1

查看ArrayList#contains哪些调用的实现indexOf()

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

contains()如果你自己为一个数组实现了，你会做同样的事情。

于 2013-09-04T15:07:15.270 回答
0

您不必担心性能问题。不会有太大影响。其良好且易于使用contains()的方法ArrayList

于 2013-09-04T15:07:37.367 回答