Qual è il modo migliore per rimuovere i duplicati in un array in Java?

Question

Ho una matrice di oggetti che devono i duplicati rimossi / filtrati. Stavo andando a sovrascrivere solo eguali e hachCode sugli elementi oggetto, e poi incollarle in un set ... ma ho pensato che avrei dovuto almeno sondaggio StackOverflow per vedere se ci fosse un altro modo, forse qualche metodo intelligente di qualche altra API?

Answer 1

Sono d'accordo con il vostro approccio di ignorare hashCode() e equals() e usare qualcosa che implementa Set.

In questo modo rende anche assolutamente chiaro a tutti gli altri sviluppatori che è necessaria la caratteristica non duplicati.

Un altro motivo - si arriva a scegliere un'implementazione che soddisfi le vostre esigenze migliori ora:

• HashSet
• TreeSet
• LinkedHashSet

e non c'è bisogno di modificare il codice per modificare l'implementazione in futuro.

Answer 2

Ho trovato questo nel web

Qui ci sono due metodi che consentono di rimuovere i duplicati in un ArrayList. removeDuplicate non mantiene l'ordine in cui come removeDuplicateWithOrder mantiene l'ordine con un po 'sovraccarico di prestazioni.

1. Il Metodo removeDuplicate:

   /** List order not maintained **/
   public static void removeDuplicate(ArrayList arlList)
   {
    HashSet h = new HashSet(arlList);
    arlList.clear();
    arlList.addAll(h);
   }
   

2. Il Metodo 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

Override equals e hashCode e la creazione di un set è stato il mio primo pensiero troppo. E 'buona pratica per avere una qualche versione override di questi metodi comunque nella gerarchia di ereditarietà.

I pensare che se si utilizza un LinkedHashSet Potrai anche mantenere l'ordine degli elementi unici ...

Answer 4

In sostanza, si vuole un'implementazione LinkedHashSet<T> che supporta l'List<T> interfaccia per l'accesso casuale. Quindi, questo è quello che vi serve:

  

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

     

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

     

}

L'attuazione dei metodi <=> sarebbe accedere e manipolare il sottostante <=>. Il trucco è quello di avere questa classe si comportano correttamente quando si tenta di aggiungere i duplicati tramite i <=> aggiungere metodi (gettando un'eccezione o ri-aggiungendo l'elemento in un diverso indice sarebbe opzioni: che è possibile scegliere uno dei o di rendere configurabile dagli utenti della classe).

Answer 5

Utilizzare un elenco distinctList all'elemento record la prima volta iterator inciampare in esso, restituisce l'distinctList come lista rimosso tutti i duplicati

 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

Mi piacerebbe ribadire il punto fatto da Jason nei commenti:

Perché porsi a questo punto a tutti?

Perché utilizzare un array per una struttura di dati che non dovrebbe contenere duplicati a tutti?

Utilizzare un Set o un SortedSet (quando gli elementi hanno un ordine naturale e) in qualsiasi momento per contenere gli elementi. Se è necessario mantenere l'ordine di inserimento, quindi è possibile utilizzare il LinkedHashSet come è stato sottolineato.

Avere a post-processo di qualche struttura dati è spesso un suggerimento che si dovrebbe hai scelto uno diverso per cominciare.

Answer 7

Naturalmente il post originale pone la domanda: "Come hai fatto a tale matrice (che potrebbe contenere le voci duplicate), in primo luogo?"

Avete bisogno l'array (con i duplicati) per altri scopi, o potrebbe semplicemente utilizzare un set dall'inizio?

In alternativa, se avete bisogno di conoscere il numero di occorrenze di ogni valore, è possibile utilizzare un Map<CustomObject, Integer> per monitorare i conteggi. Inoltre, il Google Collezioni definizione delle classi MultiMap può essere utile.

Answer 8

Un Set è sicuramente la soluzione migliore. L'unico modo per rimuovere le cose da un array (senza creare uno nuovo) è a null fuori, e poi si finisce con un sacco di nulli controlli in seguito.

Answer 9

Parlando da uno standard di programmazione generale, si può sempre fare doppio enumerare le collezioni poi il confronto l'origine e la destinazione.

E se il vostro enumerazione interna inizia sempre una voce dopo che la fonte, è abbastanza efficace (pseudo codice per seguire)

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

Si potrebbe forse aggiungere una pausa; dichiarazione dopo la distruggi, ma poi si scopre solo il primo duplicato, ma se questo è tutto si potrà mai avere, allora sarebbe una bella piccola ottimizzazione.