2012-05-25 105 views
10

¿Existe una herramienta o biblioteca para buscar entradas duplicadas en una Colección según los criterios específicos que se pueden implementar?Búsqueda de entradas duplicadas en la Colección


Para que quede claro: Quiero comparar las entradas entre sí de acuerdo a los criterios específicos. Así que creo que un Predicate que devuelva solo true o false no es suficiente.


No puedo usar equals.

+1

¿De qué manera desea especificar los criterios de deduplicación? Como un predicado binario? – NPE

+1

¿Desea * encontrar * los duplicados, o * eliminar * ellos? –

+0

@ AndyThomas-Cramer En realidad, sería suficiente solo para saber si hay duplicados. –

Respuesta

2

He creado una nueva interfaz similar a la interfaz IEqualityComparer<T> en .NET.

Tal EqualityComparator<T> Paso luego al siguiente método que detecta duplicados.

public static <T> boolean hasDuplicates(Collection<T> collection, 
     EqualsComparator<T> equalsComparator) { 
    List<T> list = new ArrayList<>(collection); 
    for (int i = 0; i < list.size(); i++) { 
     T object1 = list.get(i); 
     for (int j = (i + 1); j < list.size(); j++) { 
      T object2 = list.get(j); 
      if (object1 == object2 
        || equalsComparator.equals(object1, object2)) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

De esta manera puedo personalizar la comparación a mis necesidades.

2

Podría utilizar un mapa y al iterar sobre la colección, coloque los elementos en el mapa (los predicados formarían la clave) y si ya hay una entrada, ha encontrado un duplicado.

Para más información ver aquí: Finding duplicates in a collection

7

Depende de la semántica del criterio:

Si el criterio es siempre la misma para una clase dada, y es inherente a el concepto subyacente, debe simplemente implementar equals y hashCode y usar un conjunto.

Si su criterio depende del contexto, org.apache.commons.collections.CollectionUtils.select(java.util.Collection, org.apache.commons.collections.Predicate) podría ser la solución correcta para usted.

+0

Quiero comparar las entradas entre sí, no a criterios arbitrarios. –

4

Si desea encontrar duplicados, y no sólo la eliminación de ellos, un enfoque sería tirar la colección en una matriz, ordenar la matriz a través de un comparador que implementa sus criterios, entonces linealmente caminar a través de la matriz, mirando para duplicados adyacentes.

Aquí es un boceto (no probado):

MyComparator myComparator = new MyComparator(); 
    MyType[] myArray = myList.toArray(); 
    Arrays.sort(myArray, myComparator); 
    for (int i = 1; i < myArray.length; ++i) { 
     if (0 == myComparator.compare(myArray[i - 1], myArray[i])) { 
     // Found a duplicate! 
     } 
    } 

Editar: Desde su comentario, lo que desea saber si hay son duplicados. El enfoque anterior también funciona para esto. Pero podría simplemente crear un java.util.SortedSet con un comparador personalizado. He aquí un esbozo:

MyComparator myComparator = new MyComparator(); 
    TreeSet treeSet = new TreeSet(myComparator); 
    treeSet.addAll(myCollection); 
    boolean containsDuplicates = (treeSet.size() != myCollection.size()); 
3

Puede adaptar un conjunto de Java para la búsqueda de duplicados entre los objetos de un tipo arbitrario: envolver su clase de objetivo en un envoltorio privada que evalúa la igualdad en base a sus criterios, y construir un conjunto de envolturas .

Aquí hay un ejemplo algo largo que ilustra la técnica. Considera que dos personas con el mismo nombre son iguales, por lo que detecta tres duplicados en la matriz de cinco objetos.

import java.util.*; 
import java.lang.*; 

class Main { 
    static class Person { 
     private String first; 
     private String last; 
     public String getFirst() {return first;} 
     public String getLast() {return last;} 
     public Person(String f, String l) { 
      first = f; 
      last = l; 
     } 
     public String toString() { 
      return first+" "+last; 
     } 
    } 
    public static void main (String[] args) throws java.lang.Exception { 
     List<Person> people = new ArrayList<Person>(); 
     people.add(new Person("John", "Smith")); 
     people.add(new Person("John", "Scott")); 
     people.add(new Person("Jack", "First")); 
     people.add(new Person("John", "Walker")); 
     people.add(new Person("Jack", "Black")); 
     Set<Object> seen = new HashSet<Object>(); 
     for (Person p : people) { 
      final Person thisPerson = p; 
      class Wrap { 
       public int hashCode() { return thisPerson.getFirst().hashCode(); } 
       public boolean equals(Object o) { 
        Wrap other = (Wrap)o; 
        return other.wrapped().getFirst().equals(thisPerson.getFirst()); 
       } 
       public Person wrapped() { return thisPerson; } 
      }; 
      Wrap wrap = new Wrap(); 
      if (seen.add(wrap)) { 
       System.out.println(p + " is new"); 
      } else { 
       System.out.println(p + " is a duplicate"); 
      } 
     } 
    } 
} 

Puede jugar con este ejemplo en ideone [link].

+0

+1: ¡interesante! Simplemente no tengo idea de la eficiencia. – dragon66

+0

@ dragon66 Si su función hash es buena, la eficacia es la misma que con cualquier tabla hash, que es 'O (1)' para cada elemento, o 'O (N)' para toda la colección. – dasblinkenlight

+0

dasblinkenlight: Estoy un poco preocupado por la creación del objeto wrap aunque sé que se habrán ido fuera del ciclo. – dragon66

-2

Iterar el ArrayList que contiene duplicados y agregarlos al HashSet. Cuando el método add devuelve falso en el HashSet, solo debe registrar el duplicado en la consola.

+1

Como dice el OP, no puede usar 'equals()'. Un 'HashSet' utiliza' hashCode() 'y' equals() '. Por lo tanto, no puede usar un 'HashSet'. –

0

TreeSet le permite hacer esto fácilmente:

Set uniqueItems = new TreeSet<>(yourComparator); 
List<?> duplicates = objects.stream().filter(o -> !uniqueItems.add(o)).collect(Collectors.toList()); 

yourComarator se utiliza cuando se llama a uniqueItems.add(o), que añade el elemento al conjunto y devuelve true si el artículo es único. Si el comparador considera que el elemento es un duplicado, add(o) devolverá falso.

Tenga en cuenta que el método equals del artículo debe ser coherente con yourComarator según the TreeSet documentation para que esto funcione.

Cuestiones relacionadas