Comment implémenter l'opération de déduplication de liste Java-javaDidacticiel-php.cn

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

高洛峰

Libérer： 2017-01-22 15:53:04

original

1515 Les gens l'ont consulté

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

Copier après la connexion

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

Copier après la connexion

Code d'appel : <🎜. >

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

Il. il faut noter que :

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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 !