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

Question

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

Answer 1

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

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

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

• Хэш - набор
• Набор деревьев
• LinkedHashSet - набор ссылок

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

Answer 2

Я нашел это в Интернете

Вот два метода, которые позволяют вам удалять дубликаты в 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);
   }
   

Answer 3

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

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

Answer 4

По сути, вы хотите 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> добавить методы (выбрасывание исключения или повторное добавление элемента с другим индексом были бы вариантами:который вы можете либо выбрать один из них, либо настроить пользователями класса).

Answer 5

Используйте список distinctList для записи элемента в первый раз iterator наткнувшись на это, возвращает distinctList, поскольку список удалил все дубликаты

 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;
   } 

Answer 6

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

Зачем вообще ставить себя в такое положение?

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

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

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

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]);
        }
    }
}

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