HashSet vermeidliche Dublikate

fabian.wagner
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 19. Okt 2010 12:51

HashSet vermeidliche Dublikate

Beitrag von fabian.wagner »

Dieser Beitrag richtet sich an alle, die vermeidliche Dublikate in ihrer HashSet haben...
Überschreibt einfach eure hashCode()-Methoden in Point und Edge wie folgt und ihr solltet zumindest vorerst keine weiteren Problem mit Dublikaten in euren HashSets haben...

hashCode in Point:

Code: Alles auswählen

public int hashCode() {
		return (int)((this.x%1000)*10000+this.y%1000);
	}
hashCode in Edge:

Code: Alles auswählen

  @Override
	public int hashCode() {
		int p1 = 0;
		int p2 = 0;
		int t1 = 0;
		int t2 = 0;
		
		if(this.p1 != null)
			p1 = this.p1.hashCode();
		
		if(this.p2 != null)
			p2 = this.p2.hashCode();
		
		if(this.t1 != null)
			t1 = this.t1.hashCode();
		
		if(this.t2 != null)
			t2 = this.t2.hashCode();
		
		return (p1%1000)*1000+(p2%1000)*1000+(t1%1000)*100+(t2%1000);
     }
       }
Weitere Infos findet ihr unter:
http://docs.oracle.com/javase/6/docs/ap ... .Object%29
http://docs.oracle.com/javase/6/docs/ap ... Code%28%29
oder einfach mal equals/hashCode überschreiben googlen 8)
Zuletzt geändert von fabian.wagner am 29. Mai 2012 12:54, insgesamt 3-mal geändert.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: HashSet vermeidliche Dublikate

Beitrag von JannikV »

Ich will zwar nicht eine erneute Diskussion über das Thema hashCode im Framework anleiern, aber zumindest kurz darauf hinweisen dass die HashCode Methode für Edge nicht 100% korrekt ist. Die equals Methode überprüft auch ob die Triangle Referenzen übereinstimmen. Demnach muss das auch von HashCode berücksichtigt werden.

Ok, egal jetzt.

VG

fabian.wagner
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 19. Okt 2010 12:51

Re: HashSet vermeidliche Dublikate

Beitrag von fabian.wagner »

Ok...
So müsste es dann stimmen ;)

Code: Alles auswählen

  @Override
	public int hashCode() {
		int p1 = 0;
		int p2 = 0;
		int t1 = 0;
		int t2 = 0;
		
		if(this.p1 != null)
			p1 = this.p1.hashCode();
		
		if(this.p2 != null)
			p2 = this.p2.hashCode();
		
		if(this.t1 != null)
			t1 = this.t1.hashCode();
		
		if(this.t2 != null)
			t2 = this.t2.hashCode();
		
		return (p1%1000)*1000+(p2%1000)*1000+(t1%1000)*100+(t2%1000);
     }
       }
Zuletzt geändert von fabian.wagner am 29. Mai 2012 12:54, insgesamt 1-mal geändert.

bagwell
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 15. Nov 2010 09:18

Re: HashSet vermeidliche Dublikate

Beitrag von bagwell »

fabian.wagner hat geschrieben:Ok...
So müsste es dann stimmen ;)

Code: Alles auswählen

    public int hashCode() {
          return (this.p1.hashCode()%1000)*10000+(this.p2.hashCode()%1000)*1000+(this.t1.hashCode()%1000)*100+(this.t2.hashCode%1000);
       }
So schmeißt die Methode ne NullPointerException falls t1 oder t2 null sind :wink:

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: HashSet vermeidliche Dublikate

Beitrag von JannikV »

Außerdem wird Punkt1 mit 10000 multipliziert. Punkt2 mit 1000. Wenn die vertauscht sind kommt was anderes raus, obwohl sie equal sind.

VG

fabian.wagner
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 152
Registriert: 19. Okt 2010 12:51

Re: HashSet vermeidliche Dublikate

Beitrag von fabian.wagner »

bagwell hat geschrieben:
fabian.wagner hat geschrieben:Ok...
So müsste es dann stimmen ;)

Code: Alles auswählen

    public int hashCode() {
          return (this.p1.hashCode()%1000)*10000+(this.p2.hashCode()%1000)*1000+(this.t1.hashCode()%1000)*100+(this.t2.hashCode%1000);
       }
So schmeißt die Methode ne NullPointerException falls t1 oder t2 null sind :wink:
JannikV hat geschrieben:Außerdem wird Punkt1 mit 10000 multipliziert. Punkt2 mit 1000. Wenn die vertauscht sind kommt was anderes raus, obwohl sie equal sind.

VG
Aktualisierung:

Code: Alles auswählen

@Override
	public int hashCode() {
		int p1 = 0;
		int p2 = 0;
		int t1 = 0;
		int t2 = 0;
		
		if(this.p1 != null)
			p1 = this.p1.hashCode();
		
		if(this.p2 != null)
			p2 = this.p2.hashCode();
		
		if(this.t1 != null)
			t1 = this.t1.hashCode();
		
		if(this.t2 != null)
			t2 = this.t2.hashCode();
		
		return (p1%1000)*1000+(p2%1000)*1000+(t1%1000)*100+(t2%1000);
     }

bagwell
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 15. Nov 2010 09:18

Re: HashSet vermeidliche Dublikate

Beitrag von bagwell »

Da die Abgabefrist für getAllEdges bereits vorbei ist, denke ich ist es in Ordnung meinen Code hier zu posten.

Code: Alles auswählen

	public LinkedList<Edge> getAllEdges() {
		//TODO Task 1
		//HINT: call here getAllEdgesRec with the parameters and the return you need
		HashSet<Edge> visitedEdges = new HashSet<Edge>();
		HashSet<Triangle> visitedTriangles = new HashSet<Triangle>();
		LinkedList<Edge> saved = new LinkedList<Edge>();
		Triangle triangle = this.start;
		return getAllEdgesRec(triangle, visitedEdges, visitedTriangles, saved);
	}
	
	private LinkedList<Edge> getAllEdgesRec(Triangle triangle, HashSet<Edge> visitedEdges, HashSet<Triangle> visitedTriangles, LinkedList<Edge> saved) {
		//TODO Task 1
		
		if (triangle != null) {
			for (Edge e : triangle.getEdges()) {
				if (!visitedEdges.contains(e)) {
					visitedEdges.add(e);
					saved.add(e);
				}
				
				if (!visitedTriangles.contains(e.getT1())) {
					visitedTriangles.add(e.getT1());
					saved.addAll(getAllEdgesRec(e.getT1(), visitedEdges, visitedTriangles, saved));
				}
		
				if (!visitedTriangles.contains(e.getT2())) {
					visitedTriangles.add(e.getT2());
					saved.addAll(getAllEdgesRec(e.getT2(), visitedEdges, visitedTriangles, saved));		
				}	
						
			}
		}
		
		return saved;
	}
Die Tests laufen durch.

Aber meine zurückgegebene Liste enthält zisch Duplikate (habe hashCode() nach den Vorschlägen in diesem Thread angepasst).

Wo ist der Fehler?

Danke im Voraus!

Patrick.Lerner
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 5. Aug 2011 04:51
Wohnort: Lautertal, Kreis Bergstraße
Kontaktdaten:

Re: HashSet vermeidliche Dublikate

Beitrag von Patrick.Lerner »

Der Code ist auf jeden Fall grauenhaft zu debuggen. Was zum Beispiel ist der Unterschied zwischen saved und visitedEdges? Es wird auf den ersten Augenblick (oder auch in den ersten 100) keineswegs klar was die verschiedenen Parameter da eigentlich tun oder speichern. Plus die Hälfte davon ist eh überflüssig.

Zitat 'Clean Code':
The ideal number of arguments for a function is zero (niladic). Next comes one (monadic), followed closely by two (dyadic). Three arguments (triadic) should be avoided where possible. More than three (polyadic) requires very special justification— and then shouldn’t be used anyway.
Ich bin kein Experte in Java, deswegen kann ich dir nicht wirklich sagen warum dein HashSet nicht korrekt funktioniert, selbst mit angepassten HashCodes, aber das hier funktioniert korrekt:

Code: Alles auswählen

private LinkedList<Edge> getAllEdgesRec(Triangle triangle,
		HashSet<Edge> visitedEdges, HashSet<Triangle> visitedTriangles,
		LinkedList<Edge> saved) {
	// TODO Task 1

	if (triangle != null) {
		visitedTriangles.add(triangle); // new
		for (Edge e : triangle.getEdges()) {
			if (!visitedEdges.contains(e)) {
				visitedEdges.add(e);
				saved.add(e);
			}

			if (!visitedTriangles.contains(e.getT1())) {
				visitedTriangles.add(e.getT1());
				getAllEdgesRec(e.getT1(), visitedEdges, visitedTriangles, saved); // changed
			}

			if (!visitedTriangles.contains(e.getT2())) {
				visitedTriangles.add(e.getT2());
				getAllEdgesRec(e.getT2(), visitedEdges, visitedTriangles, saved); // changed
			}
		}
	}

	return saved;
}
Scheinbar geht dein 'saved.addAll' nicht richtig, ist aber sowieso egal, da du ja die Argumente deiner Methode eh veränderst (was an sich auch nicht der beste Stil ist, aber ist nicht super wichtig). Dann hast du irgendwie vergessen das aktuelle Triangle in deine Liste zu packen. Alles Dinge die du übrigens mittels der Stepper Funktion deines Debuggers in ~5-10 Min nachvollziehen kannst.

Sollte jedenfalls gehen, hab's nicht ausführlich getestet, aber Tests laufen noch und bei der simple-Version sind keine Duplikate drin.

Hier zum vergleich meine Variante:

Code: Alles auswählen

/**
 * Task 1
 * 
 * @return a list of all edges in the triangulation
 */
public LinkedList<Edge> getAllEdges() {
	return this.getAllEdgesRec(this.start, new LinkedList<Edge>());
}

/**
 * Looks recursively to collect all possible edges
 * 
 * @param current
 *            the current triangle we are looking at
 * @param result
 *            the edges we already have
 * @return the edges that we had plus those added recursively from the
 *         current edge
 */
private LinkedList<Edge> getAllEdgesRec(Triangle current, LinkedList<Edge> result) {
	// go through all edges of current triangle
	for (Edge e : current.getEdges())
		// do we already have that edge? if so, good ~> move along then
		if (!result.contains(e)) {
			result.add(e); // otherwise: add it and if there's a neighbor
			               // there, visit him
			if (current.getNeighbor(e) != null)
				result = this.getAllEdgesRec(current.getNeighbor(e), result);
		}
	// finally give the result back to the caller
	return result;
}
'result = this.getAllEdgesRec(current.getNeighbor(e), result);' ist bei mir auch eher optional, nur 'this.getAllEdgesRec(current.getNeighbor(e), result);' wuerde es auch tun, sieht aber besser aus imho und es hat in diesem konkreten Fall (private method, die nur von einer public method aufgerufen wird bei der results neu initialisiert wird) auch keine unerwünschten bzw. unerwarteten Nebeneffekte.
:() { :|:& }; :

bagwell
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 15. Nov 2010 09:18

Re: HashSet vermeidliche Dublikate

Beitrag von bagwell »

Zunächst ein Mal Danke, dass du dich meinem Problem angenommen hast.

Zugegebenermaßen, würden ein paar Kommentare meinem Code gut tun, diesen Kritikpunkt kann ich ja nachvollziehen.
Aber deine Moralpredigten a la "Clean Code" und den herablassenden Tonfall kannste dir echt schenken :roll:

Patrick.Lerner
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 5. Aug 2011 04:51
Wohnort: Lautertal, Kreis Bergstraße
Kontaktdaten:

Re: HashSet vermeidliche Dublikate

Beitrag von Patrick.Lerner »

bagwell hat geschrieben:Zunächst ein Mal Danke, dass du dich meinem Problem angenommen hast.

Zugegebenermaßen, würden ein paar Kommentare meinem Code gut tun, diesen Kritikpunkt kann ich ja nachvollziehen.
Aber deine Moralpredigten a la "Clean Code" und den herablassenden Tonfall kannste dir echt schenken :roll:
Sorry, war bei mir gestern auch schon ein langer Tag, war nicht meine Absicht "herablassend" zu klingen, ich hoffe du kannst mir die Art und Weise wie ich meinen Beitrag formuliert habe verzeihen.

Ich denke aber, dass das grundlegende Problem bei dir gerade der Fall war, dass dein Code etwas "zusammengewuchert" aussieht: nichts für Ungut, aber er sieht so aus als hättest du Sachen hinzugefügt bis eben die Tests durchgelaufen sind und dann Schluss gemacht hast, was ja ok ist, wenn das dein einziges Ziel war (kann ich auch verstehen, ist ja nur eine Uni-Aufgabe, nichts wofür du bezahlt wirst :wink: ).

Wenn du jedoch Quellcode erzeugen möchtest, der nicht nur grad so läuft, sondern korrekt ist (und zu einem gewissen Grad ist derartiger Perfektionismus gewollt), gut zu warten und zu debuggen ist und der weitestgehend fehlerfrei ist, dann ist es gerade wichtig auf "Clean Code" zu achten.
:() { :|:& }; :

bagwell
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 109
Registriert: 15. Nov 2010 09:18

Re: HashSet vermeidliche Dublikate

Beitrag von bagwell »

Patrick.Lerner hat geschrieben: Ich denke aber, dass das grundlegende Problem bei dir gerade der Fall war, dass dein Code etwas "zusammengewuchert" aussieht: nichts für Ungut, aber er sieht so aus als hättest du Sachen hinzugefügt bis eben die Tests durchgelaufen sind und dann Schluss gemacht hast, was ja ok ist, wenn das dein einziges Ziel war (kann ich auch verstehen, ist ja nur eine Uni-Aufgabe, nichts wofür du bezahlt wirst :wink: ).
:oops: erwischt
:mrgreen:

Antworten

Zurück zu „Archiv“