map für spielerpaarungen

[sowieso]

Hi!

Ich brauche einen Speicher für Spielerpaarungen - eine Art Map vom Typ <String, String> also.

Allerdings muss diese Map mehrfach gleiche Keys annehmen, also auch sowas:

Alex, Paul
Alex, Markus
Alex, Otto
Paul, Markus
Paul, Otto
...


gibts da was?

 

[Janus]

hab mal ne beispielimplementierung hierhin gepackt: http://rafb.net/p/5KEuug33.html

son ding benutz ich normalerweise für sowas.

 

[sowieso]

ähm danke, aber leider funktioniert dein link nicht.

Kann mir vielleicht noch jemand sagen, wie ich mein map problem lösen kann?

 

[Marco13]

Ganz spontan-subjektiv würde ich sagen, dass das keine Map ist, sondern eine Liste von Paaren.

Aber wenn du es unbedingt als Map machen willst, brauchst du eine Multimap. Dort kann (wie das halt so ist) AUCH kein Key merhfach vorkommen, aber EIN Key kann mehrere Values haben:

Map<Player, Collection<Player>> map = ...

void put(Player a, Player b)
{
    Collection<Player> coll = map.get(a);
    if (coll == null) 
    {
        coll = new ArrayList<Player>();
        map.put(a, coll);
    }
    coll.add(b);
}

(Analog bei "remove" - dran denken, die Collection aus der Map zu nehmen, wenn sie leer wird!)

 

[sowieso]

Nee, wenns nicht als Map geht, gehts nicht als Map. Und ich muss gleiche Keys haben können.

Dann mache ich es also als Liste von Paaren:

notPlayed = new LinkedList <Entry <String, String>>();

nur jetzt frage ich mich, wie ich das Paar ("Paul"/"Hanna") der List hinzufügen kann, wenn ich die beiden Strings "Paul" und "Hanna" habe. Es gibt zwar die add Methode, aber ich müsste ja die Klasse Map.Entry instanziieren um eine Entry zu erhalten und den dann hinzuzufügen. Das geht aber leider nicht.

Wie mach ich das?

 

[sowieso]

Wäre es legitim einfach eine eigene Klasse zu schreiben:

public class Pair <A, B>
{
	private A a;
	private B b;
	
	public Pair(A a, B b)
	{
		this.a = a;
		this.b = b;
	}
	
	public A getA()
	{
		return a;
	}
	
	public B getB()
	{
		return b;
	}	
}

für das:

notPlayed = new LinkedList <Pair <String, String>>();

?

 

[Janus]

klar, wieso nicht? was ich da gepostet hatte war der code einer multimap. die klasse benutzt intern ne map auf listen und bietet nen gängiges interface für manipulationen an. gehört zu meinen standard utilities, weil man es doch halt öfter mal braucht.

 

[sowieso]

ja, könntest du es vielleicht bitte nochmal posten, der link funktioniert leider nicht

wäre nett!

 

[Marco13]

Vielleicht nicht so akut wichtig, aber ... du solltest bei deiner "Pair"-Klasse auch die Methoden "equals" und "hashCode" so implementieren, wie man das erwarten würde. Sonst kannst du nämlich nicht sowas machen wie
if (list.contains(new Pair("Hallo", "Welt")) {...}

 

[sowieso]

ah, gut, dass du das sagst!

Ich wollte contains() benutzen und es hat nicht geklappt

Meine equal Methode sorgt dafür, dass (x, y) und (x, y) aber auch (x, y) und (y, x) gleich sind:

public boolean equals(Pair <A, B> p1, Pair <A, B> p2)
	{
		boolean aEqualsA = false;
		boolean bEqualsB = false;
		boolean aEqualsB = false;
		boolean bEqualsA = false;
		if (p1.getA() == p2.getA())
		{
			aEqualsA = true;
		}
		if (p1.getB() == p2.getB())
		{
			bEqualsB = true;
		}
		if (p1.getA() == p2.getB())
		{
			aEqualsB = true;
		}
		if (p1.getB() == p2.getA())
		{
			bEqualsA = true;
		}
		if ((aEqualsA && bEqualsB) || (aEqualsB && bEqualsA))
		{
			return true;
		}
		return false;
	}

Jetzt frage ich mich aber, ob ich auch das Interface comparator implementieren muss?

Außerdem weiß ich leider nicht, wie ich eine hashCode() Funktion schreiben muss

 

[Marco13]

Ne, du mußt die equals- und hashCode Methoden überschreiben, die von der Klasse "Object" angeboten werden.

class Pair<A, B>
{
    public boolean equals(Object object)
    {
        ... dein job...
    }

    public int hashCode()
    {
        ... dito ...
    }
}

Für die equals-Methode darfst du die Objekte aber NICHT mit "==" vergleichen! Stattdessen musst du dort das "equals" der jeweiligen Objekte verwenden (wenn sie nicht null sind). Bei HashCode kannst du einfach sowas zurückgeben wie
return a.hashCode() ^ b.hashCode();
(wenn a und b nicht null sind)

 

[Janus]

man sollte schon den check auf identität mit einbeziehen. das übliche pattern für equals sieht ungefähr so aus

class K ...
public boolean equals(Object object)
{
  if( object == null )
    return false;

  if( object == this )
    return true; // identität ist erschlagend

  if( ! ( object instanceof K ) )
    return false;

  // ab hier die teuren methoden beginnen
}

 

[sowieso]

gut vielen Dank erst mal!

Das probiere ich dann morgen.

 

[sowieso]

so, es klappt :wink: Aber ein Problem bleibt doch noch:

public class Pair<A, B>
{
	private A a;
	private B b;

	public Pair(A a, B b)
	{
		this.a = a;
		this.b = b;
	}

	public A getA()
	{
		return a;
	}

	public B getB()
	{
		return b;
	}

	@Override
	public boolean equals(Object o)
	{
		if (!(o instanceof Pair))
		{
			return false;
		}
		Pair <A, B> p = (Pair <A, B>) o;
		boolean aEqualsA = false;
		boolean bEqualsB = false;
		boolean aEqualsB = false;
		boolean bEqualsA = false;
		if (getA() == p.getA())
		{
			aEqualsA = true;
		}
		if (getB() == p.getB())
		{
			bEqualsB = true;
		}
		if (getA() == p.getB())
		{
			aEqualsB = true;
		}
		if (getB() == p.getA())
		{
			bEqualsA = true;
		}
		if ((aEqualsA && bEqualsB) || (aEqualsB && bEqualsA))
		{
			return true;
		}
		return false;		
	}	
	
	@Override
	public int hashCode()
	{
		return a.hashCode() + b.hashCode();
	}
}

Wenn ich eine LinkedList von Pairs habe, und "System.out.println(list)" sage, wird nur sowas ausgegeben:

[Pair@6036a1f, Pair@68ab28a, Pair@5e7a9c, Pair@c2c9bad, Pair@60063bf, Pair@687ac2a]

Ich schätze mal, da muss ich noch eine Funktion überschreiben oder? Aber welche?

 

[Gast]

na vielleicht die toString - Methode!?
In der Liste sind Objekte und wenn du die Attribute des Objekts in der überschriebenen toString() MEthode hälst...sollte es gehen....glaub ich

 

[sowieso]

Jup, das klappt!

Danke!

Was ist eigentlich der Unterschied zwischen "+" und "^" ?

 

[Gast]

"^" kenn ich gar nicht^^

 

[Marco13]

Für die equals-Methode darfst du die Objekte aber NICHT mit "==" vergleichen! Stattdessen musst du dort das "equals" der jeweiligen Objekte verwenden (wenn sie nicht null sind)

Und eine schöne toString fehlt halt noch

public String toString()
{
    return "("+a+", "+b+")";
}

 

[sowieso]

Es wurde mir doch angeboten, meine hashCode() Funktion so returnen zu lassen:

return a.hashCode() ^ b.hashCode();

Das funktioniert auch, aber irgendwie verhält sich das Zeichen wie "+"...

Wo ist da bloß der Unterschied?

 

[Marco13]

Der Unterschied zwischen + und ^ ist, dass das eine ein "plus" ist, und das andere ein "bitweises exklusives OR" (d.h. ein bitweises XOR)

Bei
c = a ^ b
werden in c genau an den Stellen die Bits gesetzt sein, an denen ENTWEDER in a ODER in b Bits gesetzt sind (aber nicht in beiden)

http://de.wikipedia.org/wiki/XOR

Eigentlich ist "fast egal", was man dort zurückgibt (nur sollte es nicht konstant 0 sein :wink: ). Welche Hashfunktion die günstigste ist, läßt sich bei generischen Typen nicht sagen. (Bei nicht-generischen ist es schon schwierig genug).

 

[sowieso]

also, ich glaube, dann belass ich es mal bei

public int hashCode()
{
	return a.hashCode() + b.hashCode();
}

:wink: danke aber für die Erklärung.

Meine toString-Methode hab ich jetzt so wie bei der HashMap gemacht:

public String toString()
{
	return a + "=" + b;		
}

Und die equals hab ich eingesetzt! Vielen Dank dafür, die hatte ich ganz vergessen...


Jetzt ist die Klasse echt praktisch! Verstehe nicht, warum es sowas nicht schon längst gibt?!

Etwas ungefähr vergleichbares ist doch nur Map.Entry und die Klasse lässt sich ja nicht instantiieren...