List en Java peut contenir des éléments répétés (code de hachage et égaux), il existe donc deux manières de dédupliquer List :
Option 1 : il peut être implémenté via HashSet. Le code est le suivant :
Copiez le code comme suit :
Étudiant de classe {
identifiant de chaîne privé ;
nom de chaîne privé ;
public Student (ID de chaîne, nom de chaîne) {
super();
this.id = identifiant;
this.name = nom ;
}
@Outrepasser
chaîne publique toString() {
return "Étudiant [id=" + id + ", name=" + name + "]" ;
}
@Outrepasser
public int hashCode() {
final int premier = 31 ;
résultat int = 1 ;
result = prime * result + ((id == null) ? 0 : id.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
renvoyer le résultat ;
}
@Outrepasser
public booléen égal (Objet obj) {
si (ce == obj) {
renvoie vrai ;
}
si (obj == nul) {
renvoie faux ;
}
if (getClass() != obj.getClass()) {
renvoie faux ;
}
Étudiant autre = (Étudiant) obj ;
si (identifiant == nul) {
if (other.id != null) {
renvoie faux ;
}
} sinon if (!id.equals(other.id)) {
renvoie faux ;
}
si (nom == null) {
if (autre.nom != null) {
renvoie faux ;
}
} else if (!name.equals(other.name)) {
renvoie faux ;
}
renvoie vrai ;
}
}
Deux méthodes, hashCode et equals, doivent être implémentées. Nous verrons dans un instant pourquoi les codes d'opération spécifiques doivent être implémentés comme suit :
Copiez le code comme suit :
private static void removeListDuplicateObject() {
List<Étudiant> list = new ArrayList<Étudiant>();
pour (int je = 0; je < 10; i++) {
Étudiant étudiant = new Student("id", "name");
list.add(étudiant);
}
System.out.println(Arrays.toString(list.toArray()));
Set<Étudiant> set = new HashSet<Étudiant>();
set.addAll(liste);
System.out.println(Arrays.toString(set.toArray()));
list.removeAll(liste);
set.removeAll(set);
System.out.println(Arrays.toString(list.toArray()));
System.out.println(Arrays.toString(set.toArray()));
}
Code d'appel :
Copiez le code comme suit :
public static void main (String[] arguments) {
RemoveListDuplicateObject();
}
Lorsque nous utilisons HashSet pour effectuer des opérations de déduplication, pourquoi devons-nous remplacer les méthodes hashCode et equals ?
Vérifions le code source de l'opération d'ajout de HashSet comme suit :
Copiez le code comme suit :
public booléen add(E e) {
return map.put(e, PRESENT)==null;
}
HashMap est appelé pour l'opération. Regardons l'opération put de HashMap :
Copiez le code comme suit :
public V put (clé K, valeur V) {
si (clé == null)
return putForNullKey(valeur);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
pour (Entrée<K,V> e = table[i]; e != null; e = e.next) {
Objet k ;
if (e.hash == hachage && ((k = e.key) == clé || key.equals(k))) {
V oldValue = e.value ;
e.value = valeur ;
e.recordAccess(this);
retourner ancienneValeur ;
}
}
modCount++;
addEntry(hash, clé, valeur, i);
renvoie null ;
}
Les choses à noter sont :
Copiez le code comme suit :
if (e.hash == hachage && ((k = e.key) == clé || key.equals(k))) {
...
}
En d'autres termes, les codes de hachage sont égaux et égaux (==).
Complexité : il suffit de traverser d'un côté, O(n)
Option 2 : parcourir directement la liste et implémenter les opérations de contenu et d'ajout. Le code est le suivant :
Copiez le code comme suit :
private static void removeListDuplicateObjectByList() {
List<Étudiant> list = new ArrayList<Étudiant>();
pour (int je = 0; je < 10; i++) {
Étudiant étudiant = new Student("id", "name");
list.add(étudiant);
}
System.out.println(Arrays.toString(list.toArray()));
List<Étudiant> listUniq = new ArrayList<Étudiant>();
pour (Etudiant étudiant : liste) {
if (!listUniq.contains(étudiant)) {
listUniq.add (étudiant);
}
}
System.out.println(Arrays.toString(listUniq.toArray()));
list.removeAll(liste);
listUniq.removeAll(listUniq);
System.out.println(Arrays.toString(list.toArray()));
System.out.println(Arrays.toString(listUniq.toArray()));
}
D'autres sont les mêmes que ci-dessus.
Complexité:
Lors du parcours, la méthode contain est appelée en même temps. Nous visualisons le code source comme suit :
Copiez le code comme suit :
public booléen contient (Objet o) {
return indexOf(o) >= 0 ;
}
public int indexOf(Objet o) {
si (o == nul) {
pour (int i = 0; i < taille; i++)
si (elementData[i]==null)
je reviens;
} autre {
pour (int i = 0; i < taille; i++)
si (o.equals(elementData[i]))
je reviens;
}
renvoie -1 ;
}
Vous pouvez voir qu'une autre opération de parcours a été effectuée sur la nouvelle liste. Autrement dit, 1+2+....+n, la complexité est O(n*n)
en conclusion:
La solution 1 est très efficace, c'est-à-dire qu'elle utilise HashSet pour effectuer des opérations de déduplication.
