Java: .contains and .equals

Question

我正在尝试执行一个程序，用于比较两个链表中的元素。一种方法是使用两个for循环遍历这两个列表，并使用.equals()方法比较list1中的每个元素与list2中的对应元素。另一种方法是仅遍历第一个列表，并检查list1是否包含list1.get(i)。Java文档显示.contains在内部使用.equals进行比较。如果是这样，为什么前者的运行时间比后者长？我是否误解了文档？如果是，那么当我使用.contains时内部比较会如何进行？

            using equals:
            for (int i = 0; i < list_one.size(); i++) {
              for (int j = 0; j < list_one.size(); j++) {
                  if (list_one.get(i).equals(list_two.get(j))) { count++; }

            using contains:
            for (int i = 0; i < list_one.size(); i++) {
                 if (list_two.contains(list_one.get(i)) == true) { count++; }

- madCode

---

考虑查看源代码。 - Dave Newton

不需要使用for循环来检查列表中是否存在元素。 - KV Prajapati

我需要检查第一个列表中的每个元素是否在第二个列表中存在。基本上是挑选出重叠的元素。 - madCode

Answer 1

实现contains方法时，一旦equals返回true，它将停止迭代，因此如果你要查找的元素位于列表开头的某个位置，它就不会迭代整个列表。如果你的版本没有这样做，那么这就解释了为什么它较慢。

另外，无论哪种方式，运行时间仍将是平方级别的。有更聪明的方法来解决这个问题，而不需要对第一个列表中的每个项目都迭代第二个列表（例如通过先对两个列表排序或使用集合）。

- sepp2k

---

有道理。如果你看到我的代码，是的...我猜那可能是运行时间更长的原因。是的，我知道还有其他各种方法，但我特别想尝试这种情况。 - madCode

Answer 2

我认为，看到你在两个循环中都使用了get(j)，这在链表中是低效的。for (String s1 : list1) for (String s2 : list2) ...应该与contains具有相同的速度。

例如，get(3)需要从第一个元素开始，连续跟随链接三次。而for-each使用指向下一个元素的迭代器。

- Joop Eggen