Listen in Java können wiederholte Elemente (Hash-Code und Gleiches) enthalten. Daher gibt es zwei Möglichkeiten, Listen zu deduplizieren:
Option 1: Es kann über HashSet implementiert werden. Der Code lautet wie folgt:
Kopieren Sie den Codecode wie folgt:
Klasse Student {
private String-ID;
privater String-Name;
public Student(String id, String name) {
super();
this.id = id;
this.name = Name;
}
@Override
öffentlicher String toString() {
return „Student [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int Ergebnis = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
Ergebnis zurückgeben;
}
@Override
öffentlicher boolescher Wert gleich(Objekt 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;
}
}
Zwei Methoden, hashCode und equal, müssen implementiert werden. Wir werden gleich sehen, warum die spezifischen Operationscodes wie folgt implementiert werden müssen:
Kopieren Sie den Codecode wie folgt:
private static void removeListDuplicateObject() {
List<Student> list = new ArrayList<Student>();
for (int i = 0; i < 10; i++) {
Student student = neuer 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()));
}
Anrufcode:
Kopieren Sie den Codecode wie folgt:
public static void main(String[] args) {
removeListDuplicateObject();
}
Warum müssen wir bei der Verwendung von HashSet zur Durchführung von Deduplizierungsvorgängen die Methoden hashCode und equal überschreiben?
Lassen Sie uns den Quellcode der Add-Operation von HashSet wie folgt überprüfen:
Kopieren Sie den Codecode wie folgt:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashMap wird zur Operation aufgerufen. Schauen wir uns die Put-Operation von HashMap an:
Kopieren Sie den Codecode wie folgt:
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) {
Objekt 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);
null zurückgeben;
}
Zu beachten sind:
Kopieren Sie den Codecode wie folgt:
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
...
}
Mit anderen Worten, die Hash-Codes sind gleich und gleich(==).
Komplexität: Nur eine Seite durchqueren, O(n)
Option 2: Durchlaufen Sie die Liste direkt und implementieren Sie die Vorgänge „Contains“ und „Add“. Der Code lautet wie folgt:
Kopieren Sie den Codecode wie folgt:
private static void removeListDuplicateObjectByList() {
List<Student> list = new ArrayList<Student>();
for (int i = 0; i < 10; i++) {
Student student = neuer Student("id", "name");
list.add(student);
}
System.out.println(Arrays.toString(list.toArray()));
List<Student> listUniq = new ArrayList<Student>();
for (Student Student: Liste) {
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()));
}
Andere sind die gleichen wie oben.
Komplexität:
Beim Durchlaufen wird gleichzeitig die Methode „contains“ aufgerufen. Wir sehen den Quellcode wie folgt:
Kopieren Sie den Codecode wie folgt:
öffentlicher boolescher Wert enthält(Objekt o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
gib i zurück;
} anders {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
gib i zurück;
}
return -1;
}
Sie können sehen, dass für die neue Liste ein weiterer Durchlaufvorgang ausgeführt wurde. Das heißt, 1+2+....+n, die Komplexität ist O(n*n)
abschließend:
Lösung 1 ist hocheffizient, d. h. die Verwendung von HashSet zur Durchführung von Deduplizierungsvorgängen.
