Quelle est la meilleure façon de supprimer les doublons dans un tableau en Java?

Question

J'ai un tableau d'objets qui ont besoin les doublons supprimés / filtrés. J'allais simplement passer outre égaux et hachCode sur les éléments d'objets, puis les coller dans un ensemble ... mais je me suis dit que je devrais au moins stackoverflow sondage pour voir s'il y avait une autre façon, peut-être une méthode intelligente d'une autre API?

Answer 1

Je suis d'accord avec votre approche pour passer outre et hashCode() et utiliser quelque chose equals() qui implémente Set.

Cela rend également tout à fait clair pour tout autre développeurs que la caractéristique non-double est nécessaire.

Une autre raison - vous pouvez choisir une implémentation qui répond mieux à vos besoins maintenant:

• HashSet
• TreeSet
• LinkedHashSet

et vous ne devez pas changer votre code pour changer la mise en œuvre à l'avenir.

Answer 2

J'ai trouvé dans le web

Voici deux méthodes qui vous permettent de supprimer les doublons dans un ArrayList. removeDuplicate ne maintient pas l'ordre où que removeDuplicateWithOrder maintient l'ordre avec certains frais généraux de performance.

1. Le removeDuplicate Méthode:

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

2. Le removeDuplicateWithOrder Méthode:

   /** 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

Redéfinition et equals et la création d'un hashCode ensemble a été ma première pensée aussi. Il est bon d'avoir une version surchargée de ces méthodes de toute façon dans votre hiérarchie d'héritage.

pense que si vous utilisez un LinkedHashSet vous aurez Préservez même ordre d'éléments uniques ...

Answer 4

En gros, vous voulez une implémentation qui prend en charge l'LinkedHashSet<T> l'interface pour l'accès aléatoire List<T>. Par conséquent, voici ce dont vous avez besoin:

  

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

     

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

     

}

La mise en œuvre des méthodes accéderait <=> et manipuler le sous-jacent <=>. L'astuce est d'avoir correctement se comporter de cette classe quand on tente d'ajouter des doublons via les méthodes add (lancer <=> une exception ou re-ajouter l'élément à un autre indice serait des options: que vous pouvez choisir l'une ou faire configurable par les utilisateurs de la classe).

Answer 5

Utilisez une liste à l'élément distinctList enregistrement à la première fois en elle trébuche iterator, retourne la distinctList liste supprimé tous les doublons

 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

Je voudrais réitérer la remarque de Jason dans les commentaires:

Pourquoi placez-vous à ce moment-là du tout?

Pourquoi utiliser un tableau pour une structure de données qui ne doivent pas contenir des doublons du tout?

Utilisez un Set ou un SortedSet (lorsque les éléments ont un ordre naturel aussi) en tout temps pour maintenir les éléments. Si vous avez besoin de garder l'ordre d'insertion, vous pouvez utiliser comme il l'a LinkedHashSet été signalé.

Le fait de devoir post-traitement une structure de données est souvent une indication que vous avez choisi un différent pour commencer.

Answer 7

Bien sûr, le message original pose la question suivante: « Comment avez-vous ce tableau (qui contient des entrées en double) en premier lieu? »

Avez-vous besoin le tableau (avec doublons) à d'autres fins, ou pourriez-vous utiliser simplement un ensemble dès le début?

Alternativement, si vous avez besoin de connaître le nombre d'occurrences de chaque valeur, vous pouvez utiliser un compte pour suivre Map<CustomObject, Integer>. En outre, le définition Collections Google des classes Multimap peut être utile.

Answer 8

est sans aucun doute votre Set meilleur pari. La seule façon de supprimer les choses d'un tableau (sans créer un nouveau) est de les null sur, puis vous vous retrouvez avec beaucoup de contrôles nuls plus tard.

Answer 9

En parlant d'une norme de programmation générale vous pouvez toujours deux énumérer les collections puis comparer la source et la cible.

Et si votre énumération intérieure commence toujours une entrée après la source, il est assez efficace (code pseudo à suivre)

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

Vous pouvez sans doute ajouter une pause; déclaration après la détruis mais vous découvrez que le premier doublon, mais si c'est tout ce que vous aurez jamais, alors ce serait une belle petite optimisation.