eine Frage zu hashCode()

[Timo]

also ich fange mal von vorne an:

ich habe eine abstrakte Klasse Function, die eine mathematische Funktion x --> f(x) repäsentiert und wollte ihr die methode equals spendieren. nun ist mir aber aufgefallen, dass das nicht ganz einfach ist, da z.b. die beiden funktionen:
f(x) = x^2 * (3x+4) <--ein Produkt
g(x) = 3*x^3 + 4*x^2 <-- eine Summe
gleich sind, also sollte equals auf die beiden funktionen angewendet true ergeben. deswegen hab ich es mir leicht gemacht und definiere es einfach so: Zwei Funktionen sind genau dann gleich, wenn sie in den Funktionswerten an 3 zufällig gewählten Stellen im Intervall [-100;100] übereinstimmen. sollte eigentlich in 99,9% aller Fälle klappen, nur jetzt kommt das Problem mit der Konsistenz von equals() und hashCode(). ich muss ja auch hashCode() überschreiben, sodass 2 Funktionen die laut equals() gleich sind auch den selben hashCode() zurückgeben. hier habe ich es mir wieder einfach gemacht und habe die methode hashCode() einfach folgendermaßen überschrieben:

public int hashCode(){
    return 1;
}

klappt natürlich, aber jetzt meine frage: wann ist es denn relevant, dass hashCode() "vernünftige" werte zurückgibt?

PS: um die funktionen zu repräsentieren benutze ich übrigens das Composite Pattern (abstrakte Klasse Function mit den methoden getValue(double x) und getDerivate(), dann viele Klassen die von ihr erben, wie z.b. Konstante, Potenzfunktion, Summe, Produkt, Verkettung, etc., aus denen ich dann funktionen zusammensetzen kann.). vielleicht hat ja jmd eine idee wie ich equals() anders realisieren könnte als mit dem "Zufallsverfahren"?

 

[Wildcard]

Jede Klasse die Hashs verwendet wird von einer solchen Implemenierung gestört.
Die HashMap zum Beispiel hat nichts anderes mehr zu tun als Kollisionen aufzulösen und wird praktisch unbenutzbar.

 

[Ariol]

du könntest die funktion als tree schreiben und diesen dann sortieren lassen (mit der Bedingung, das ein Operator nur Operatoren oder nur Zahlen als Kinder haben darf) Root ist rechts:

---------------------------------------------
f(x):

(x)\
    (*)\
(x)/     \
            \  
              \         
                \
                 \
                 (*)          
(3)\            /
    (*)\       /
(x)/    \     /
         (+)/
(4)\    /
    (*)/
(1)/

-------------------------------------------------
g(x):

(3)\            
    (*)\       
(x)/    \     
         (*)\
(x)\    /    \
    (*)/       \
(x)/            \
                 (+)
(4)\            /
    (*)\       /
(x)/    \     /
         (*)/
(x)\    /
    (*)/
(1)/

lässt sich umformen zu (ausklammern von x²):

(x)\
    (*)\
(x)/     \
            \  
              \         
                \
                 \
                 (*)          
(3)\            /
    (*)\       /
(x)/    \     /
         (+)/
(4)\    /
    (*)/
(1)/

und das ist wiederum der gleiche tree wie der von f(x). Dieser Tree lässt sich dann auch über equal vergleichen und Hash sollte auch gehen.


Nur eine Idee. ist mir gerade so eingefallen und hab auch keine Idee wie man den Tree implementieren soll bzw. ihn sortieren.

EDIT: codetags gesetzt

 

[Timo]

danke für den tipp. ich werde mir gedanken drüber machen, dass so zu versuchen zu realisieren

ich muss dann wohl jeder klasse die von Function erbt noch ne methode simplify geben, die z.b. distributivgesetz anwendet, terme rauskürzt (wobei hier beachtet werden muss, dass der term nicht null werden kann, wieder ein problem ) und sachen wie *1 oder +0 entfernt.

 

[Der Müde Joe]

Vielleicht hilft dir da Antlr ein wenig

http://www.antlr.org/

und der passende Einstieg
http://www.cs.usfca.edu/~parrt/course/652/lectures/antlr.html

 

[-frank]

deswegen hab ich es mir leicht gemacht und definiere es einfach so: Zwei Funktionen sind genau dann gleich, wenn sie in den Funktionswerten an 3 zufällig gewählten Stellen im Intervall [-100;100] übereinstimmen.

also WENN du es (doch) so einfach machen willst: wähle die werte nicht zufällig. denn ein equals() könnte dann einmal true geben und das nächste mal nicht. nimm immer dieselben werte. dann ist auch hashCode() leicht zu implementieren, denn der hashCode sollte genau von den werten abhängen, die in equals() verglichen werden. du könntest also die 3 in equals() verglichenen werte einfach zusammenzählen und returnen.

 

[WieselAc]

wieso definierst du den hashcode nicht einfach als die Summe der Funktionswerte (gerundet) die auch für equals verwendest?

Aber ganz am Rande es gibt unendlich viele Funktionen die an drei oder auch beliebig vielen Stellen den gleichen Funtionswert haben, aber dennoch nicht gleich sind (Auf diesem Prinzip basieren alle numerischen Approximationen).

Um mal zu verdeutlichen, dass es garnicht so unwahrscheinlich ist so etwas zu erhalten:

Durch drei Punkte ist ein Funktion mit mindestens drei unbekannten bestimmt (a*x^2 + b*x + c), also z.B. eine Parabel. Um einfach zu bleiben sind die drei Punkte der Extremwert und die Nullstellen. Dann kannst du durch stauchen und strecken beliebig viel Funktionen erstellen die die gleichen Nullstellen und den gleichen Extremwert besitzten. Soetwas läuft in der Mathematik unter dem Namen "Funktionschar".


Von daher sei vorsichtig wo du das einsetzt!

 

[Timo]

deswegen hab ich es mir leicht gemacht und definiere es einfach so: Zwei Funktionen sind genau dann gleich, wenn sie in den Funktionswerten an 3 zufällig gewählten Stellen im Intervall [-100;100] übereinstimmen.

also WENN du es (doch) so einfach machen willst: wähle die werte nicht zufällig. denn ein equals() könnte dann einmal true geben und das nächste mal nicht. nimm immer dieselben werte. dann ist auch hashCode() leicht zu implementieren, denn der hashCode sollte genau von den werten abhängen, die in equals() verglichen werden. du könntest also die 3 in equals() verglichenen werte einfach zusammenzählen und returnen.

ja aber wenn ich es so mache, ist es halt zu einfach zwei funktionen zu erstellen, die nicht gleich sind, aber per equals() gleich seien.

z.b. wenn ich die stellen a, b und c betrachte, erstelle ich einfach zwei funktionen:
f(x) = (x-a)(x-b)(x-c)*K
g(x) = (x-a)(x-b)(x-c)*G
mit K != G
f und g schneiden sich nun in den stellen a, b und c, sie wären also laut equals() gleich, obwohl sie sich (je nach K und G) voneinander in allen anderen relevanten Stellen unterscheiden können.

die zufällige wahl sorgt dafür, dass die wahrscheinlichkeit, dass mal zwei ungleiche funktionen als gleich gelten, nahezu 0 ist.

 

[Leroy42]

die zufällige wahl sorgt dafür, dass die wahrscheinlichkeit, dass mal zwei ungleiche funktionen als gleich gelten, nahezu 0 ist.

Na bravo!

Wenn diese Wahrscheinlichkeit gleich p (z.B. 99.99%) ist kannst du
sie dann leicht auf 1-(1-p)² (99,999999%) steigern, wenn du schreibst

if (a.equals(b) && b.equals(a))

(aber mach dann deinen Code ja niemanden zugänglich)

 

[WieselAc]

der ist gut !! (sorry für spam)

 

[Lim_Dul]

Ob zufällig oder fest gewählt hat auf die Wahrscheinlichkeit erstmal keinen großen Einfluß. Dafür müsste man zusätzlich wissen, um was für Funktionen es sich handelt.

Die zufällige Wahl hat aber einen Nachteil, sie ist nicht stabil. Und es sobald du Listen zum abspeichern nutzt, indexOf, contains aufrufst, kannst du mit Bugs konfrontiert werden, die sich letztendlich darauf zurückführen lassen, aber derartig selten und versteckt sind, dass man sie nie wirklich erkennt.

Und das Argument, dass man bei fester Wahl, leicht zwei Funktionen erstellen kann, die equal sind, aber nicht gleich sind, zieht auch nicht. Dafür müsste jemand böswillig sein. Wenn die Funktionen zufällig sind, dann ist eine feste Wahl genausogut wie eine zufällige.


Mein persönlicher Vorschlag wäre, im Konstruktor der Funktion drei Zufallszahlen zu definieren und die dann in equals immer als Testzahlen zu nehmen. Dadurch hast die Garantie, dass equals stabil ist und dennoch die Zufallskomponente drin.

 

[Ariol]

noch eine Idee: über Postfix-screibweise auflösen:

f(x) = xx*3x*4+*
g(x) = 3xxx***4xx**+

dann von hinten suchen ob ein man ein +*, -*, +/ oder -/ findet und das ganze dann dementsprechend ändern (also die 2 davorstehenden Zahlengruppen(samt Operatoren) mit dem 3 davorstehenden Wert(samt Operatoren) verknüpfen (* oder / dranhängen) und den anderen Operator (+ oder -) hinten anhängen)

Also: (g(x) ist schon korrekt)

f(x) = xx*3x*4+*

+* gefunden

3x und 4 um xx* erweitern:

3xxx***4xx**+

und das ist gleich g(x)

musst halt noch + und - und * und / aufeinander abstimmen also, dass xxx*/ = x wird

ist vermutlich nicht so einfach wie das mit den Zufallszahlen, aber wenn du es richtig implementierst ist die erfolgsrate 100%