对arraylist调用contains()是否效率低下?

new HashSet<>(arrayList) 拿 o(n)时间 和 O(n)空间 建立一个 HashSet .

hashSet.contains("something") 拿 O(1)时间 找到一个元素。

arrayList.contains("something") 拿 O(N)时间 找到一个元素。

结果是:

(new HashSet<>(arrayList)).contains("something") 拿 O(n)+O(1)=O(n)时间+O(n)空间 复杂性

数组列表包含(“某物”)。 拿 o(n)时间+0空间 复杂性

这意味着根据 大O 符号,两个表达式都有 o(n)时间 复杂性,但 数组列表包含(“某物”)。 不占用额外空间,而不是新创建的 哈希表 .

附笔。

我没有对其他情况做出任何预测,因为我不知道您的应用程序的其他相关方面。我只分析给定的代码段。

潜在地。要检查元素是否在列表中,我们必须按顺序检查每个元素。

元素0是我们要查找的元素吗?是/否
元素1是我们要寻找的元素吗?是/否
…
等。

显然,一旦找到它,就可以停止迭代。

复杂性:

• 最佳案例:这是第一个元素。这是一个固定时间的查找。 O(1)
• 一般情况:在中间的某个地方。O(N/2)
• 最坏情况: 这是最后一个元素。我们必须对每个元素进行比较。 o(n)

哈希集总是一个固定的时间查找。你只需计算散列码并调用 Object::equals .

至于您是否应该使用集合,它实际上取决于您使用它的其他用途。如果你只是在做 contains 一套是最合适的。否则,请参见 Which Java Collection should I use?