Каков наилучший способ удаления дубликатов в массиве в Java?

У меня есть массив объектов, которые нуждаются в удалении / фильтрации дубликатов. Я собирался просто переопределить equals & hachCode для элементов Object, а затем вставить их в Set ... но я решил, что мне следует хотя бы опросить stackoverflow, чтобы увидеть, есть ли другой способ, возможно, какой-нибудь умный метод какого-то другого API?

10.12.2008 20:07:08
Зачем ставить себя в это место? Почему бы не предотвратить дубликаты в первую очередь?
LeppyR64 10.12.2008 20:11:58
Задайте вопрос об удалении дубликатов ... получите кучу повторяющихся ответов. Ирония!
erickson 10.12.2008 20:19:38
То, как вы описываете, идеально.
OscarRyz 11.12.2008 00:35:46
9 ОТВЕТОВ
РЕШЕНИЕ

Я согласен с вашим подходом , чтобы переопределить hashCode()и equals()и использовать то , что орудия Set.

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

Другая причина - вы можете выбрать реализацию, которая лучше всего соответствует вашим потребностям:

и вам не нужно менять свой код, чтобы изменить реализацию в будущем.

21
10.12.2008 20:28:57

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

0
10.12.2008 20:14:08

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

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

3
11.12.2008 23:51:01
Да, LinkedHashSetбудет поддерживать порядок вставки.
Ken Gentle 10.12.2008 20:20:56
Не рекомендуется переопределять equals и hashCode «в любом случае», особенно в любом классе, который будет находиться в иерархии наследования. Смотрите Effective Java (Bloch) для более подробной информации.
McDowell 10.12.2008 21:00:52
Макдауэлл, мне не очень понятно - я имел в виду, что где-то в вашей иерархии наследования должна быть переопределенная версия , и я изменил ответ, чтобы отразить это. У меня нет копии Effective Java - это то, к чему стремится Блох?
Dan Vinton 11.12.2008 23:53:35

Я нашел это в сети

Вот два метода, которые позволяют вам удалять дубликаты в ArrayList. removeDuplicate не поддерживает порядок, тогда как removeDuplicateWithOrder поддерживает порядок с некоторыми накладными расходами.

  1. Метод removeDuplicate:

    /** List order not maintained **/
    public static void removeDuplicate(ArrayList arlList)
    {
     HashSet h = new HashSet(arlList);
     arlList.clear();
     arlList.addAll(h);
    }
  2. Метод removeDuplicateWithOrder:

    /** List order maintained **/
    public static void removeDuplicateWithOrder(ArrayList arlList)
    {
       Set set = new HashSet();
       List newList = new ArrayList();
       for (Iterator iter = arlList.iterator(); iter.hasNext();) {
          Object element = iter.next();
          if (set.add(element))
             newList.add(element);
       }
       arlList.clear();
       arlList.addAll(newList);
    }
9
10.12.2008 20:27:06
Хороший ответ, но ваш второй пример не находится в блоке формата кода
TravisO 10.12.2008 20:24:25
спасибо Кену Г ... я попробовал это пару раз, но я не мог исправить второй блог кода
Markus Lausberg 10.12.2008 20:28:57
LinkedHashSet держит его в порядке. Это может оптимизировать его дальше.
Daddy Warbox 11.12.2008 23:55:53

Исходя из общего стандарта программирования, вы всегда можете дважды перечислить коллекции, а затем сравнить источник и цель.

И если ваше внутреннее перечисление всегда начинается с одной записи после исходного кода, это довольно эффективно (псевдокод будет следовать)

foreach ( array as source )
{
    // keep track where we are in the array
    place++;
    // loop the array starting at the entry AFTER the current one we are comparing to
    for ( i=place+1; i < max(array); i++ )
    {
        if ( source === array[place] )
        {
            destroy(array[i]);
        }
    }
}

Вы можете добавить разрыв; заявление после уничтожения, но тогда вы обнаружите только первый дубликат, но если это все, что у вас когда-либо будет, то это будет хорошая небольшая оптимизация.

0
10.12.2008 20:25:17

Я хотел бы повторить замечание, высказанное Джейсоном в комментариях:

Зачем вообще себя ставить?

Зачем использовать массив для структуры данных, которая вообще не должна содержать дубликаты?

Всегда используйте a Setили a SortedSet(когда элементы имеют естественный порядок) для хранения элементов. Если вам нужно сохранить порядок вставки, то вы можете использовать, LinkedHashSetкак было указано.

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

1
10.12.2008 21:41:29
Я согласен со всеми комментариями относительно проблем, связанных с исходной структурой данных, являющейся массивом. Я пытаюсь лоббировать разработчика для рефакторинга в набор. Спасибо всем за ваши отзывы и мудрость!
Liggy 11.12.2008 15:10:05

Конечно, в оригинальном посте напрашивается вопрос: «Как вы получили этот массив (который может содержать дублированные записи) в первую очередь?»

Вам нужен массив (с дубликатами) для других целей, или вы могли бы просто использовать Set с самого начала?

В качестве альтернативы, если вам нужно знать количество вхождений каждого значения, вы можете использовать Map<CustomObject, Integer>для отслеживания количества. Кроме того, определение Google Collections для классов Multimap может быть полезным.

1
10.12.2008 22:03:39

По сути, вы хотите LinkedHashSet<T>реализацию, которая поддерживает List<T>интерфейс для произвольного доступа. Следовательно, это то, что вам нужно:

public class LinkedHashSetList<T> extends LinkedHashSet<T> implements List<T> {

// Implementations for List<T> methods here ...

}

Реализация List<T>методов позволит получить доступ к базовому объекту и манипулировать им LinkedHashSet<T>. Хитрость заключается в том, чтобы этот класс вел себя корректно, когда кто-то пытается добавить дубликаты с помощью List<T>методов добавления (выбрав исключение или повторно добавив элемент с другим индексом, вы можете выбрать один из них или сделать его настраиваемым пользователями класс).

2
11.12.2008 00:28:56

Используйте List distinctList для записи элемента, когда в первый раз iteratorнаткнетесь на него, вернете значение DifferentList, поскольку список удаляет все дубликаты.

 private List removeDups(List list) {
        Set tempSet = new HashSet();
        List distinctList = new ArrayList();
        for(Iterator  it = list.iterator(); it.hasNext();) {
            Object next = it.next();
            if(tempSet.add(next)) {
                distinctList.add(next);
            } 
        }
        return distinctList;
   } 

2
3.10.2018 13:37:03
сложность очень высока, так как List.contains имеет O (n) временную сложность, поэтому сложность O (N ^ 2)
Filip Luchianenco 25.09.2018 04:33:59
@FilipLuchianenco вы правы, я обновил свою реализацию
didxga 25.09.2018 07:08:58
Тогда вам нужно только продолжать добавлять новое значение, если оно существует, оно просто вернет false. В результате вы получите итератор и набор, в который вы продолжаете добавлять уникальные значения. Единственным недостатком является порядок, так как Set не сохраняет его из-за изменения размера. Тогда другое решение состоит в том, чтобы иметь список и набор, и если ваш set.add (объект) возвращает true, вы также добавляете его в новый список; затем верните список.
Filip Luchianenco 27.09.2018 15:52:09
Почему нам нужно заботиться о порядке набора, поскольку мы собираемся изменить список, передаваемый в функцию, которую мы используем итератором для удаления дубликатов, который не меняет внутренний порядок списка
didxga 30.09.2018 14:15:56
ListЧто ж , удаление элемента из a очень неэффективно, поскольку List.remove () должен будет каждый раз создавать новый список и копировать все элементы, поэтому ваша сложность теперь равна O (n ^ k), где k - размер списка. Поэтому я даже не хотел рассматривать это как вариант.
Filip Luchianenco 1.10.2018 03:45:08