Comment implémenter l'opération de déduplication de liste Java

La liste en Java peut contenir des éléments répétés (code de hachage et égaux), il existe donc deux façons de dédupliquer la liste :
Option 1 : elle peut être implémentée via HashSet, le code est le suivant :

class Student { 
private String id; 
private String name; 
public Student(String id, String name) { 
super(); 
this.id = id; 
this.name = name; 
} 
@Override 
public String toString() { 
return "Student [id=" + id + ", name=" + name + "]"; 
} 
@Override 
public int hashCode() { 
final int prime = 31; 
int result = 1; 
result = prime * result + ((id == null) ? 0 : id.hashCode()); 
result = prime * result + ((name == null) ? 0 : name.hashCode()); 
return result; 
} 
@Override 
public boolean equals(Object obj) { 
if (this == obj) { 
return true; 
} 
if (obj == null) { 
return false; 
} 
if (getClass() != obj.getClass()) { 
return false; 
} 
Student other = (Student) obj; 
if (id == null) { 
if (other.id != null) { 
return false; 
} 
} else if (!id.equals(other.id)) { 
return false; 
} 
if (name == null) { 
if (other.name != null) { 
return false; 
} 
} else if (!name.equals(other.name)) { 
return false; 
} 
return true; 
} 
}

Les méthodes hashCode et equals doivent être implémentées. Nous verrons pourquoi elles doivent être implémentées dans un instant
Le code d'opération spécifique est le suivant :

private static void removeListDuplicateObject() { 
List<Student> list = new ArrayList<Student>(); 
for (int i = 0; i < 10; i++) { 
Student student = new Student("id", "name"); 
list.add(student); 
} 
System.out.println(Arrays.toString(list.toArray())); 
Set<Student> set = new HashSet<Student>(); 
set.addAll(list); 
System.out.println(Arrays.toString(set.toArray())); 
list.removeAll(list); 
set.removeAll(set); 
System.out.println(Arrays.toString(list.toArray())); 
System.out.println(Arrays.toString(set.toArray())); 
}

Code d'appel : <🎜. >

public static void main(String[] args) { 
removeListDuplicateObject(); 
}

Lorsque nous utilisons HashSet pour effectuer des opérations de déduplication, pourquoi devons-nous remplacer les méthodes hashCode et equals ?

Nous examinons le code source de l'opération d'ajout de HashSet comme suit :

public boolean add(E e) { 
return map.put(e, PRESENT)==null; 
}

HashMap est appelé pour l'opération Regardons l'opération put de HashMap :

public V put(K key, V value) { 
if (key == null) 
return putForNullKey(value); 
int hash = hash(key.hashCode()); 
int i = indexFor(hash, table.length); 
for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
Object k; 
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
V oldValue = e.value; 
e.value = value; 
e.recordAccess(this); 
return oldValue; 
} 
} 
modCount++; 
addEntry(hash, key, value, i); 
return null; 
}

Il. il faut noter que :

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
...... 
}

C'est-à-dire que les codes de hachage sont égaux et égaux(==).

Complexité : il suffit de parcourir d'un côté, O(n)
Option 2 : parcourir la liste directement et l'implémenter via des opérations de contenu et d'ajout
Le code est le suivant :

private static void removeListDuplicateObjectByList() { 
List<Student> list = new ArrayList<Student>(); 
for (int i = 0; i < 10; i++) { 
Student student = new Student("id", "name"); 
list.add(student); 
} 
System.out.println(Arrays.toString(list.toArray())); 
List<Student> listUniq = new ArrayList<Student>(); 
for (Student student : list) { 
if (!listUniq.contains(student)) { 
listUniq.add(student); 
} 
} 
System.out.println(Arrays.toString(listUniq.toArray())); 
list.removeAll(list); 
listUniq.removeAll(listUniq); 
System.out.println(Arrays.toString(list.toArray())); 
System.out.println(Arrays.toString(listUniq.toArray())); 
}

D'autres sont équivalents à ce qui précède.

Complexité :
Lors du parcours, la méthode contain est appelée en même temps. Nous visualisons le code source comme suit :

public boolean contains(Object o) { 
return indexOf(o) >= 0; 
} 
public int indexOf(Object o) { 
if (o == null) { 
for (int i = 0; i < size; i++) 
if (elementData[i]==null) 
return i; 
} else { 
for (int i = 0; i < size; i++) 
if (o.equals(elementData[i])) 
return i; 
} 
return -1; 
}

Vous pouvez voir qu'une autre opération de parcours est effectuée sur le nouveau. liste. Soit 1 2 .... La complexité de n est O(n*n)

Conclusion :
Le schéma 1 est très efficace, c'est-à-dire qu'il utilise HashSet pour effectuer des opérations de déduplication

Plus de java Pour des articles connexes sur la façon d'implémenter l'opération de déduplication de liste, veuillez faire attention au site Web PHP chinois !