Простой способ найти, если два разных списка содержат одинаковые элементы?

Как проще всего найти, если два списка содержат абсолютно одинаковые элементы в стандартных библиотеках Java?

Не должно иметь значения, являются ли два списка одинаковым экземпляром или нет, и не должно иметь значения, отличаются ли параметры типа списков.

например

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

Там, наверное, что-то смотрит мне в лицо, я знаю :-)

РЕДАКТИРОВАТЬ: Чтобы уточнить, я искал точно так же элементы и количество элементов, по порядку.

Если вы заботитесь о порядке, просто используйте метод equals:

list1.equals(list2)

От Javadoc:

Сравнивает указанный объект с этим списком на равенство. Возвращает true тогда и только тогда, когда указанный объект также является списком, оба списка имеют одинаковый размер, и все соответствующие пары элементов в двух списках равны. (Два элемента e1 и e2 равны, если (e1 == null? E2 == null: e1.equals (e2)).) Другими словами, два списка определяются как равные, если они содержат одинаковые элементы в одинаковом порядке. , Это определение гарантирует, что метод equals работает правильно в разных реализациях интерфейса List.

Если вы хотите проверить независимость от порядка, вы можете скопировать все элементы в Sets и использовать equals в результирующих наборах:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

Ограничением этого подхода является то, что он не только игнорирует порядок, но и частоту повторяющихся элементов. Например, если list1было ["A", "B", "A"] и list2было ["A", "B", "B"], то Setподход будет считать их равными.

Если вам нужно быть нечувствительным к порядку, но чувствительным к частоте дублирования, вы можете:

• отсортируйте оба списка (или копии) перед их сравнением, как это сделано в этом ответе на другой вопрос
• или скопируйте все элементы в мультисеть

Я разместил кучу вещей в комментариях, думаю, это оправдывает свой ответ.

Как все говорят здесь, использование equals () зависит от порядка. Если вы не заботитесь о заказе, у вас есть 3 варианта.

Опция 1

Использование containsAll(). Этот вариант, на мой взгляд, не идеален, потому что он предлагает производительность в худшем случае, O (n ^ 2).

Вариант 2

Есть два варианта этого:

2a) Если вы не хотите поддерживать порядок в своих списках ... используйте Collections.sort()оба списка. Тогда используйте equals(). Это O (nlogn), потому что вы делаете два вида, а затем сравниваете O (n).

2b) Если вам нужно поддерживать порядок списков, вы можете сначала скопировать оба списка. Затем вы можете использовать решение 2а в обоих скопированных списках. Однако это может быть непривлекательно, если копирование очень дорого.

Это ведет к:

Вариант 3

Если ваши требования такие же, как в части 2b , но копирование слишком дорого. Вы можете использовать TreeSet, чтобы выполнить сортировку за вас. Дамп каждого списка в свой собственный TreeSet. Он будет отсортирован в наборе, а исходные списки останутся нетронутыми. Затем проведите equals()сравнение на обоих TreeSetс. В TreeSetsы могут быть встроены в O (NlogN) времени, и представляет equals()собой О (п).

Сделайте ваш выбор :-).

РЕДАКТИРОВАТЬ: Я почти забыл ту же оговорку, на которуюуказывает Лоуренс Гонсалвес . Реализация TreeSet устранит дубликаты. Если вы заботитесь о дубликатах, вам понадобится какой-то сортированный мультимножество.

Если вы используете (или с удовольствием используете) Коллекции Apache Commons, вы можете использовать CollectionUtils.isEqualCollection, который «возвращает истину, если данные Коллекции содержат абсолютно одинаковые элементы с одинаковым количеством элементов».

Очень поздно на вечеринку, но хотел добавить эту нулевую безопасную проверку:

Objects.equals(list1, list2)

Я знаю, что это старая ветка, но ни один из других ответов полностью не решил мой вариант использования (я думаю, что Guava Multiset может сделать то же самое, но здесь нет примера). Пожалуйста, извините за мое форматирование. Я все еще новичок в размещении на стеке обмена. Дополнительно сообщите мне, если есть какие-либо ошибки

Допустим, у вас есть List<T>a и List<T>b, и вы хотите проверить, соответствуют ли они следующим условиям:

1) O (n) ожидаемое время выполнения.
2) Равенство определяется как: Для всех элементов в a или b число раз, когда элемент встречается в a, равно числу раз, которое элемент встречается в b. Равенство элементов определяется как T.equals ()

private boolean listsAreEquivelent(List<? extends Object> a, List<? extends Object> b) {
    if(a==null) {
        if(b==null) {
            //Here 2 null lists are equivelent. You may want to change this.
            return true;
        } else {
            return false;
        }
    }
    if(b==null) {
        return false;
    }
    Map<Object, Integer> tempMap = new HashMap<>();
    for(Object element : a) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            tempMap.put(element, 1);
        } else {
            tempMap.put(element, currentCount+1);
        }
    }
    for(Object element : b) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            return false;
        } else {
            tempMap.put(element, currentCount-1);
        }
    }
    for(Integer count : tempMap.values()) {
        if(count != 0) {
            return false;
        }
    }
    return true;
}

Время выполнения - O (n), потому что мы делаем O (2 * n) вставки в hashmap и O (3 * n) выбирает hashmap. Я не полностью протестировал этот код, так что будьте осторожны :)

//Returns true:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A"));
listsAreEquivelent(null,null);
//Returns false:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),null);

Попробуйте эту версию, которая не требует, чтобы порядок был одинаковым, но поддерживает наличие нескольких одинаковых значений. Они совпадают, только если у каждого одинаковое количество любого значения.

public boolean arraysMatch(List<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}

Метод equals в List сделает это, списки упорядочены, поэтому для того, чтобы они равнялись, два списка должны иметь одинаковые элементы в одинаковом порядке.

return list1.equals(list2);

Решение для случая, когда два списка имеют одинаковые элементы, но разный порядок:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}

Том отвечает отлично, я полностью согласен с его ответами!

Интересный аспект этого вопроса заключается в том, нужен ли вам сам Listтип и его внутреннее упорядочение.

Если нет, вы можете понизить Iterableили Collectionполучить некоторую гибкость при передаче структур данных, отсортированных по времени вставки, а не во время, когда вы хотите проверить.

Если порядок не имеет значения (и у вас нет дублирующих элементов), рассмотрите возможность использования Set.

Если порядок имеет значение, но определяется временем вставки (и у вас нет дубликатов), рассмотрите a, LinkedHashSetкоторый похож на TreeSet, но упорядочен по времени вставки (дубликаты не учитываются). Это также дает вам O(1)амортизированный доступ O(log n).

Образец кода:

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (sizeNewList == -1)) {
        return false;
    }

    if (sizeNewList != sizePrevoisList) {
        return true;
    }

    List n_prevois = new ArrayList(previousList);
    List n_new = new ArrayList(newList);

    try {
        Collections.sort(n_prevois);
        Collections.sort(n_new);
    } catch (ClassCastException exp) {
        return true;
    }

    for (int i = 0; i < sizeNewList; i++) {
        Object obj_prevois = n_prevois.get(i);
        Object obj_new = n_new.get(i);
        if (obj_new.equals(obj_prevois)) {
            // Object are same
        } else {
            return true;
        }
    }

    return false;
}

В дополнение к ответу Лоуренса, если вы также хотите сделать его нуль-безопасным:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

list1.equals(list2);

Если ваш список содержит пользовательский класс MyClass, этот класс должен переопределить equalsфункцию.

 class MyClass
  {
  int field=0;
  @0verride
  public boolean equals(Object other)
        {
        if(this==other) return true;
        if(other==null || !(other instanceof MyClass)) return false;
        return this.field== MyClass.class.cast(other).field;
        }
  }

Примечание: если вы хотите проверить равно на java.util.Set, а не на a java.util.List, тогда ваш объект должен переопределить hashCode функцию.

List.equals ()

http://java.sun.com/j2se/1.5/docs/api/java/util/List.html#equals(java.lang.Object)

Вы можете использовать библиотеку Apache org.apache.commons.collections: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)

Проверьте, что оба списка не являются нулевыми. Если их размеры разные, то эти списки не равны. Создайте карты, состоящие из элементов списков в качестве ключей и их повторений в качестве значений, и сравните карты.

Предположения, если оба списка равны нулю, я считаю их равными.

private boolean compareLists(List<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(mapSize);

    for (Object o : list) {
        Integer count = map.get(o);
        if (count == null) {
            map.put(o, 1);
        } else {
            map.put(o, ++count);
        }
    }

    System.out.println(map);
    return map;
}

Пожалуйста, обратите внимание, метод equals должен быть правильно определен для этих объектов. https://stackoverflow.com/a/24814634/4587961

Это зависит от того, какой конкретный класс List вы используете. У абстрактного класса AbstractCollection есть метод containsAll (Collection), который принимает другую коллекцию (List - это коллекция) и:

Возвращает true, если эта коллекция содержит все элементы в указанной коллекции.

Таким образом, если ArrayList передается внутрь, вы можете вызвать этот метод, чтобы увидеть, точно ли они совпадают.

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

Причина для метода containsAll () заключается в том, что он перебирает первый список в поисках совпадения во втором списке. Поэтому, если они вышли из строя, функция equals () не поднимет их.

РЕДАКТИРОВАТЬ: Я просто хочу прокомментировать здесь амортизированное время выполнения различных предлагаемых опций. Важно ли время бега? Конечно. Это единственное, что вы должны рассмотреть? Нет.

Стоимость копирования КАЖДОГО отдельного элемента из ваших списков в другие списки требует времени, а также занимает значительную часть памяти (фактически удваивая объем используемой памяти).

Таким образом, если память в вашей JVM не имеет значения (как это обычно и должно быть), вам все равно нужно учитывать время, необходимое для копирования каждого элемента из двух списков в два TreeSets. Помните, что он сортирует каждый элемент по мере его поступления.

Мой последний совет? Вам необходимо рассмотреть ваш набор данных и количество элементов в вашем наборе данных, а также размер каждого объекта в вашем наборе данных, прежде чем вы сможете принять правильное решение. Поиграйте с ними, создайте один из них и посмотрите, какой из них работает быстрее. Это хорошее упражнение.