Java:.contains和.equals

Question

我正在尝试执行一个程序,将两个链表中的元素相互比较.一种方法,我可以这样做是通过执行两个for循环并迭代两个列表比较list1中的每个元素与list2使用.equals().另一种方法是,只是迭代第一个列表并检查list1.contains(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++; }

Answer 1

contains将停止迭代的实现一旦equals返回true,所以如果您要查找的元素位于列表开头的某个位置,它不会迭代整个列表.如果您的版本不这样做,那就可以解释为什么它的速度较慢.

PS:无论哪种方式,运行时间仍然是二次方的.有更聪明的方法可以解决这个问题,不需要为第一个列表中的每个项目迭代第二个列表(例如,首先对两个列表进行排序或使用一组).

Answer 2

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

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