Java: тест на дубликаты объектов в коллекции

Question

Учитывая List из MyClass объектов (и пользовательский Comparitor myComparitor при необходимости), какие есть хорошие варианты для проверки, если List содержит два "равных" объекта?

Редактировать: если есть дубликаты, вернуть ссылку на один или несколько дубликатов.

Переопределение MyClass.equals(MyClass) в этом случае не вариант.

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

SortedSet mySet = new TreeSet(myComparitor);
mySet.addAll(myList);
// Find duplicates in a sorted set in O(N) time

P.S. Есть хорошая ссылка на уценку?

Answer 1

Если метод элемента equals(Object) не дает необходимой вам семантики, тогда HashMap или HashSet не являются опциями.Ваш выбор:

• Используйте TreeMap для дедупликации.Это O(NlogN).
• Сортировать ArrayList или копию, затем выполнить итерацию для поиска элемента i, равного элементу i + 1. Это O(NlogN).
• Найдите альтернативную реализацию хеш-наборов, которая позволяет вам предоставлять отдельный объект для реализации равенства и хеширования.(Ни Apache, ни коллекции Google не поддерживают это, поэтому вам нужно смотреть дальше.)
• Создать класс-оболочку для вашего типа элемента, который переопределяет equals(Object) и hashCode(), и дедуплицировать, используяHashSet обернутых предметов.Это O(N), но константа пропорциональности будет больше, чем простая HashSet из-за создания объектов-оболочек.

При дедупликации с Set, вероятно, лучшеиспользуйте цикл вместо addAll.Это необходимо, если вам нужно знать, что такое все дубликаты.Если вам не нужно это знать, то использование цикла позволяет вам остановиться, когда вы найдете первый дубликат.Единственный случай, когда addAll может работать лучше, это когда дубликатов не будет.

Answer 2

если у вас уже есть отсортированный список , вы можете просто посмотреть на любой элемент и следующий элемент, и если они одинаковы, у вас есть дубликаты.

в своем вопросе вы используете TreeSet, который бы уже отбирал дубликаты, поэтому, если вам просто нужно знать, есть ли у вас дубликаты , просто проверьте размер mySet по сравнению с размером myList. если они не одинаковые, у вас есть дупли.