# equals() - hashCode() - Contract



## Spacerat (28. Mrz 2009)

Hallo...
Ich bin zwar kein Anfänger mehr, poste mein Anliegen aber mal hier, damits auch die gleich mitbekommen können...
Mein Anliegen ist folgendes:[highlight=java]
public boolean equals(Object obj)
{
  if(obj == this) return true;
/*  try {
    Vertex v = (Vertex) obj;
    boolean rc = true;
    for(int n = 0; n < d.length && rc; n++) rc &= v.d[n] == d[n];
    return rc;
  } catch(ClassCastException e) {
    return false;
  }*/
  if(obj == null) return false;
  if(obj instanceof Vertex) {
    Vertex v = (Vertex) obj;
    boolean rc = true;
    for(int n = 0; n < d.length && rc; n++) rc &= v.d[n] == d[n];
    return rc;
  }
  return false;
}

public int hashCode()
{
  return toString().hashCode();
}

public String toString()
{
  return "X: " + d[0] + "; Y: " + d[1] + "; Z: " + d[2];
}[/highlight]Wie langjährige Forennutzer wissen stehe ich mit folgendem auf "Kriegsfuss":
Wenn man "equals()" überschreibt, sollte man auch "hashCode()" überschreiben, und zwar so, das inhaltlich gleiche Instanzen den selben Hash erhalten.
In meiner Klasse gibts allerdings ein winziges Problem: Da es sich bei meiner Klasse um eine Klasse handelt ("Vertex" -> in etwa Point3D) die in 3D-Anwendungen exessiv verwendet wird, ist es unvermeidlich, das inhaltlich verschiedene Vertices den selben Hash erhalten (logisch: Es können ja 3x soviele Instanzen existieren, wie Hashcodes zur Verfügung stehen). Aufgefallen ist mir dies, als sich eine rein logisch implementierte "equals()"-Methode[highlight=java]public boolean equals(Object object)
{
  if(this == object) return true;
  if(object == null) return false;
  if(object instanceof Vertex) return hashCode() == object.hashCode();
  return false;
}[/highlight]als grausam FATAL erwies. Welche Bewandnis hat es also mit diesem Contract? Wenn man hier also nur "equals()" überschreibt, kann die Klasse doch immer noch (wenn auch nicht so exessiv, lediglich das 1. Drittel aller möglichen Instanzen) in einer HashMap, -Table und oder -Set verwendet werden, oder sehe ich das falsch?


----------



## Gelöschtes Mitglied 5909 (28. Mrz 2009)

> 3D-Anwendungen exessiv verwendet wird, ist es unvermeidlich, das inhaltlich verschiedene Vertices den selben Hash erhalten logisch: Es können ja 3x soviele Instanzen existieren, wie Hashcodes zur Verfügung stehen)



du hast 3x Integer.MAX_VALUE Vertex Objekte ? Das will ich sehn 

Dein equals und hashCode sind aber nicht gerade das gelbe vom ei. Lass sie dir am besten von Eclipse generieren wenn du nicht weißt was du tust (sieht für mich so aus)


} catch(ClassCastException e) {


hab ich noch nie gesehn in ner equals() methode


----------



## Spacerat (28. Mrz 2009)

Tja... ich schon... Dekompiliertes "javax.vecmath". ist offenbar die kompilierte Form vom eigentlichen[highlight=java]if(object instanceof Vertex)[/highlight]Kann man natürlich noch ändern, aber wozu? Wäre nur zusätzlicher Schreibkram zu Eingangs ohnehin schon zuviel davon... ;-)
... aus wievielen Punkten bestehen den deine Welten? Nein... Ich hab' nicht 3x MaxInteger, wäre aber möglich...


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> [highlight=java]
> public boolean equals(Object obj)
> {
> if(obj == this) return true;
> ...


Dieses try-catch ist schon etwas seltsam, wie raiL schon gesagt hat... Auch wenn es zum selben kompiliert, verschleiert es imho den sinn der ganzen sache. Außerdem: vielleicht will das ein anderer Compiler irgendwie anders kompilieren, oder jemand will es später irgendwohin portieren, und mit instanceof geht es dann effizienter, wer weiß... :bahnhof:

toString().hashCode() ist zwar an Kürze nicht zu übertreffen, aber diese ganzen ziffern hinzuschreiben ist eine riesige menge an (hier eigentlich sinnfreier) divisionen, ich würde daher vielleicht eine TODO-bemerkung dranschreiben, dass man den hashwert vielleicht lieber doch durch einen haufen shift- und xor-operationen erzeugen sollte, das ist irgendwie näher am wesen des Problems... 


> Wie langjährige Forennutzer wissen stehe ich mit folgendem auf "Kriegsfuss":


jetzt weiß ich es :bae:


> Wenn man "equals()" überschreibt, sollte man auch "hashCode()" überschreiben, und zwar so, das inhaltlich gleiche Instanzen den selben Hash erhalten.


genau. "equals==true  =>  hash==hash" muss gelten.



> ist es unvermeidlich, das inhaltlich verschiedene Vertices den selben Hash erhalten


Das gilt doch so ziemlich für ALLES was nicht boolean,short,byte,char oder integer ist. Da alles andere zumindest mal aus diesen, oder komplexeren datentypen aufgebaut ist, haben alle anderen objekte sicherlich mehr verschiedene mögliche zustände, also kann es keinen einzigartigen integer-hashcode für jedes solches objekt geben.



> Aufgefallen ist mir dies, als sich eine rein logisch implementierte "equals()"-Methode[highlight=java]public boolean equals(Object object)
> {
> if(this == object) return true;
> if(object == null) return false;
> ...


Whooow :autsch: Was war denn an diesem Stunt "logisch"????:L
Was du hier implementiert hast, ist
"hash==hash <=> equals==true" was natürlich völlig ungeeignet ist, da es ja (wie oben bemerkt) fast immer mehr verschiedene objektzustände gibt, als integer darstellen kann. Deine equals schmeißt sehr viele unterschiedliche Objekte in einen Topf, wie eine hash-funktion eben...


> Welche Bewandnis hat es also mit diesem Contract? Wenn man hier also nur "equals()" überschreibt, kann die Klasse doch immer noch (wenn auch nicht so exessiv, lediglich das 1. Drittel aller möglichen Instanzen) in einer HashMap, -Table und oder -Set verwendet werden, oder sehe ich das falsch?


Implikation "equals wahr => hash gleich" muss unbedingt gelten, ansonsten können HashMaps und HashTables nicht mehr korrekt funktionieren.
Einfaches beispiel: HashSet mit 2 buckets, zwei objekte A und B für die gilt:
[highlight=Java]A.equals(B)==true
A.hashCode==0
B.hashCode==1 //gegen contract![/highlight]

da A und B dasselbe objekt darstellen, würde man doch erwarten, dass bei
[highlight=Java]set=new HashSet();
set.add(A);
set.remove(B);
set.size()==0[/highlight]
gilt, weil man ja etwas reingepackt, und "dasselbe" wieder rausgenommen hat. Da die hashCode-methode aber den vertrag nicht erfüllt, geht der set wie folgt vor:
[highlight=Java]set=new HashSet(2); //allokiert 2 Listen, beide leer [0->[],1->[]]
set.add(A);  //A.hash()==0, okay, in die erste speicherzelle packen: [0->[A],1->[]]
set.remove(B); //B.hash()==1, okay, in der zweiten liste nachschauen: 1->[], nix drin, also ist B nicht im set, also nichts zu tun... 0->[A] bleibt
System.out.println(set.size());//1 ? [/highlight]
was soll denn da sonst passieren...:bahnhof:

Ein konkretes Beispiel des Versagens von HashMap bei inkorrekt implementierten hashCode-methode:
[highlight=Java]
import java.util.*;

public class _ {
    private static class F_2{
        int value;
        public F_2(int value){
            this.value=value;
        }
        @Override
        public boolean equals(Object other){
            return other instanceof F_2    &&    (this.value-((F_2)other).value)%2==0;
        }
        @Override
        public int hashCode(){
            return value;
        }
    }

    public static void main(String[] args){
        Set<F_2> set=new HashSet<F_2>(2);
        F_2 zero=new F_2(8);
        F_2 one=new F_2(137);
        System.out.println("equals: "+zero.equals(one));
        System.out.println("zero.hash(): "+zero.hashCode());
        System.out.println("one.hash(): "+one.hashCode());
        set.add(zero);
        set.remove(one);
        System.out.println("set.size(): "+set.size());
    }
}
[/highlight]
F_2 steht hier für eine sehr miese implementierung des restklassenringes modulo 2, also dem einzigen Körper mit 2 elementen (0 und 1), wo gelten muss:
0+0=0
0+1=1+0=1
1+1=0

0*0=0
0*1=1*0=0
1*1=1
was für's beispiel allerdings völlig egal ist...


----------



## Spacerat (28. Mrz 2009)

0x7F800000 hat gesagt.:


> Dieses try-catch ist schon etwas seltsam, wie raiL schon gesagt hat... Auch wenn es zum selben kompiliert, verschleiert es imho den sinn der ganzen sache. Außerdem: vielleicht will das ein anderer Compiler irgendwie anders kompilieren, oder jemand will es später irgendwohin portieren, und mit instanceof geht es dann effizienter, wer weiß... :bahnhof:


OK... ist ein Argument... werd's noch ändern.





			
				0x7F800000 hat gesagt.:
			
		

> toString().hashCode() ist zwar an Kürze nicht zu übertreffen, aber diese ganzen ziffern hinzuschreiben ist eine riesige menge an (hier eigentlich sinnfreier) divisionen


Ich selbst verwende es ja nicht... von daher: Hauptsache HashCode 


			
				0x7F800000 hat gesagt.:
			
		

> Das gilt doch so ziemlich für ALLES was nicht boolean,short,byte,char oder integer ist.


Auch Klar: Der Vertex war im Gegensatz zu Strings bzw. Texten da noch recht harmlos (deswegen habe ich das auch mit "toString().hashCode()" gemacht). Der Vertex sollte auch nur als Beispiel dienen (wegen der exessiven Nutzung bei z.B. NonLV-Morph-Objekten *)





			
				0x7F800000 hat gesagt.:
			
		

> Whooow :autsch: Was war denn an diesem Stunt "logisch"????:L


Äh... Reversierung einer mathematischen Gleichung? So ergehts einem, wenn man den Contract andersherum interpretiert (Wenn der hashCode gleich ist, soll das Objekt equal sein). Wie gesagt: Grausam FATAL 

So alles in allem: Ist es also durchaus legitim, bei Digen die exessiv genutzt werden, "hashCode()" mal aussen vor zu lassen, wenn man nur eine Vergleichs-Methode braucht?

* LV: LowVertex <- LowVertexObject


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> So alles in allem: Ist es also durchaus legitim, bei Digen die exessiv genutzt werden, "hashCode()" mal aussen vor zu lassen, wenn man nur eine Vergleichs-Methode braucht?


wie mein beispiel zeigt, ist es nicht legitim, ist es nur legitim, wenn man alle und jeden ausdrücklich darauf hinweist, dass mit diesen objekten weder HashSets noch HashMaps funktionieren... (das würde imho ziemlich albern aussehen). wie willst du denn garantieren, dass du niemals bei keinem algorithmus ein Set mit O(1) zugriffzeit von solchen objekten brauchst? Das ist doch unrealistisch... Bei einer sehr kleinen Sache, die man nie wiederverwendet, kann man das vielleicht machen, aber sonst... :noe:

Bei der implementierung von equals sollte man hashCode nirgends verwenden, das hat da nichts verloren.

<offtopic> jetzt hast du mich übrigens auf ein sehr schwieriges problem aufmerksam gemacht: was tun, wenn equals() gar nicht kanonisch gegeben ist? Also kein haufen == und member.equals() vergleiche...?</offtopic> Hmm... ???:L


----------



## Spacerat (28. Mrz 2009)

0x7F800000 hat gesagt.:
			
		

> <offtopic> jetzt hast du mich übrigens auf ein sehr schwieriges problem aufmerksam gemacht: was tun, wenn equals() gar nicht kanonisch gegeben ist? Also kein haufen == und member.equals() vergleiche...?</offtopic> Hmm... ???:L


Wenn ich genau wüsste was du mit "kanonisch gegeben" meinst würde ich sagen: nicht Offtopic. Denn im Prinzip geht's mir ja genau darum, das "Object.equals()", "==" entspricht, was beim Vergleich von Vertices viel fataler als die Tatsache ist, das ich, um das zu ändern "hashCode()" gleich mit überschreiben muss (der Grund, warum ich mit diesem Contract auf "Kriegsfuss" stehe). Deswegen kam ja auch die Annahme, das es "legitim" sei, "hashCode()" ganz einfach mal zu vergessen. Letzendlich bringt man ja nur Collections aus dem Tritt die auf "hashCode()" beruhen.
Fakt ist, das bei meinem Morph-Objekt die Punkte so "dämlich" zu liegen scheinen (hat man bei importierten Objekten ja auch nicht immer Einfluss drauf), das, wenn ich "hashCode()" verwende (HashSet statt ArrayList), das Morphing selber nicht mehr korrekt funktioniert, selbst wenn es sich nur um eine Vertex-Anzahl, die nicht mal annäherd MaxShort (also noch weit unterhalb von MaxInteger) ist, handelt.


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> Wenn ich genau wüsste was du mit "kanonisch gegeben" meinst würde ich sagen: nicht Offtopic.


Naja, wenn man zB. sowas gegeben hat:
[highlight=Java]
class X{
   private int a,b,c;
   private String x,y,z;
   private SomeClass r,s,t;

   @Override
   public boolean equals(Object other){
       if(other instanceof X){
           X o=(X)other;
           return
               other.a==this.a
           ...
           && other.c==this.c
           && other.x.equals(this.x)
           ...
           && other.t.equals(this.t);
   }

   @Override
   public int hashCode(){
        //some very tricky hashCode-formula
   }
}
[/highlight]
dann ist equals halt "kanonisch gegeben": man vergleich einfach alle elemente und fertig.

Was tun, wenn man komplexere Strukturen hat?
Wenn man zum beispiel eine Kontextfreie Sprache durch eine Grammatik gegeben hat: okay, man kann chomsky-normalform der grammatiken bilden, guggen ob sie gleich sind. Das ist zwar heftig aber machbar. Um gleichen Hashcode für alle Grammatiken zu garantieren, müsste man sie also von vornrein in CNF aufbewahren.

Was wenn man Ideale in Plynomringen vergleichen will? Okay, neulich habe ich gelernt, dass es dazu reicht die reduzierten Gröbnerbasen auszurechnen, und diese zu vergleichen, damit ist auch alles klar. Ist zwar evtl bisschen viel zu rechnen, aber hier gibt es auch _die_ Darstellung, die man in hash verwenden könnte.

Wenn man Graphen in Klassen mit der gleichen Topologie unterteilen will, kriegt man das wohl auch noch irgendwie hin, irgendeine eindeutige standarddarstellung zu wählen...

Aber was mache ich aber zB. mit richtig abgefahrenen verschachtelten Ausdrücken mit vielen Wurzeln und trigonometrischen funktionen und solchen kram?
Mal angenommen, wenn ich zwei solche terme gegeben habe, könnte ich sie durch äquivalenzumformungen irgendwie so umschreiben, dass ich am ende 1=1 oder 1=0 da stehen habe, und eindeutig beantworten kann: "ja, sind gleich", oder "nein, sind ungleich". Was aber wenn ich ein einzelnes solches Ding gegeben habe? :bahnhof: Gibt es da auch irgendeine "normalform"? Ich weiß es nicht...

Das war jetzt das Problem, das ich angesprochen habe.



> Denn im Prinzip geht's mir ja genau darum, das "Object.equals()", "==" entspricht


Ja, das ist unbrauchbar. Überschreib's doch einfach, bei einem Vertex ist das zum Glück völlig unproblematisch, eben "Kanonisch"... Einfach alle komponenten nacheinander vergleichen.


> ...was beim Vergleich von Vertices viel fataler als die Tatsache ist, das ich, um das zu ändern "hashCode()" gleich mit überschreiben muss


Wo ist denn da jetzt was "fatal"? Du hattest kurz irgendeinen denkfehler bei der implementierung von equals gehabt, hast da aus irgendeinem grund hash darin verbaut... Jetzt bist du auf den Denkfehler aufmerksam geworden, hast ihn auch behoben, ist das Problem nicht weg? Wenn nicht: was ist denn das Problem dann überhaupt noch?


> Deswegen kam ja auch die Annahme, das es "legitim" sei, "hashCode()" ganz einfach mal zu vergessen.


imho nicht Legitim...


> Letzendlich bringt man ja nur Collections aus dem Tritt die auf "hashCode()" beruhen.


Ja, das wäre HashMap und HashSet. DIE einzigen Arten von Maps /Sets die in konstanter amortisierter zeit INSERT/REMOVE/FIND ausführen können. Wenn das nicht grund genug ist, evtl das halbe programm umzuschreiben, dann weiß ich auch nicht weiter ???:L


> Fakt ist, das bei meinem Morph-Objekt die Punkte so "dämlich" zu liegen scheinen (hat man bei importierten Objekten ja auch nicht immer Einfluss drauf), das, wenn ich "hashCode()" verwende (HashSet statt ArrayList), das Morphing selber nicht mehr korrekt funktioniert, selbst wenn es sich nur um eine Vertex-Anzahl, die nicht mal annäherd MaxShort (also noch weit unterhalb von MaxInteger) ist, handelt.


Solange der "Vertrag" nicht erfüllt ist, läuft nichts.  Völlig egal wieviele Vertices das sind: es klappt nicht mal bei zwei, siehe mein Beispiel oben.

Bei implementierung von hash-funktionen sollte man darauf achten, dass die funktion sich möglichst chaotisch verhält, dass also zwei sehr nah beieinander liegende Objekte völlig unterschiedliche Hashcodes erzeugen. Aber das ist ein anderes Thema.


----------



## Spacerat (28. Mrz 2009)

... Ok... Ich versuchs mal so:
ein Vertex besteht bei mir aus 3x float (96 Bit). Für den Hashcode bedeutet das, das sich 3 Vertices einen Hashcode teilen. Über diese 3 Vertices lässt sich sogar ein Dreieck spannen. Will man dieses Dreieck in einem Hashset (wegen dem schnelleren Zugriff) zu einem Polygon zusammenfassen wirds ein Problem. Na klar: Kein Mensch weiss vorher, welche Vertices jeweils dieses Problem ergeben. Aber wie Zufällig können 3D-Welten sein, wie weit liegen diese Vertices auseinander? Man kann ja nicht mal bestätigen, das sie in verschiedenen Quadranten liegen. Die Berechnung des Hashcodes mittels "toString()" oder irgend eine andere Implementation verlegt die jeweils verbundenen Vertices dabei auch nur an eine andere Stelle und das bedeutet, das das Problem für ein Drittel aller Objekte nicht mehr auftritt, dafür aber nun ein anderes betroffen ist. Leider reicht in manchen Fällen hie auch schon eine geringe Menge an Vertices (beim betroffenen Objekt waren es grad mal ca.2000). Lt. Murphy braucht man sich also gar nicht die Mühe machen, ein HashSet für Polygone zu verwenden, den alles was schiefgehen kann geht irgendwann schief. Deswegen ist es auch mehr oder weniger egal, was da für ein Hashcode berechnet wird, und wenn's der ist, den die VM erzeugt, wenn "hashCode()" nicht überschrieben wurde. Vllt. ist das auch ein Fall für "Ausnahmen bestätigen die Regel".
@Edit: "HashTable" hast du vergessen?


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> ... Ok... Ich versuchs mal so:
> ein Vertex besteht bei mir aus 3x float (96 Bit).


Kann mir das grob vorstellen, ja...


> Für den Hashcode bedeutet das, das sich 3 Vertices einen Hashcode teilen.


Im Schnitt... Wenn die hash-funktion gut ist, ja... Sie kann ja auch jedem vertex einfach den Wert 123 zuordnen, dann ist das immer noch eine Hash-funktion, nur eben keine besonders gute...



> Über diese 3 Vertices lässt sich sogar ein Dreieck spannen.


Öhm, offtopic oder was wird das...


> Will man dieses Dreieck in einem Hashset (wegen dem schnelleren Zugriff) zu einem Polygon zusammenfassen wirds ein Problem.


Was wird ein Problem? Kriegst du keine Hash-Funktion für Dreiecke hin oder was... Eben ging's doch noch um Vertices... ;(


> Na klar: Kein Mensch weiss vorher, welche Vertices jeweils dieses Problem ergeben.


bahnhof. Ich raff endgültig nichts mehr. Was ist denn nun das Problem omg?! :autsch:


> Aber wie Zufällig können 3D-Welten sein, wie weit liegen diese Vertices auseinander?


Absolut undefiniert. Bei Delaunay will man einen Haufen kurzer dicker Dreiecke haben, dagegen können zB. laserstrahlen auf 50000000 Milliarden kilometer Langen Dreiecken gerendert werden. Aber was hat das alles mit hash funktionen zu tun????:L


> Man kann ja nicht mal bestätigen, das sie in verschiedenen Quadranten liegen.


 Nein, keine Quadranten...


> Die Berechnung des Hashcodes mittels "toString()" oder irgend eine andere Implementation verlegt die jeweils verbundenen Vertices dabei auch nur an eine andere Stelle und das bedeutet, das das Problem für ein Drittel aller Objekte nicht mehr auftritt, dafür aber nun ein anderes betroffen ist.


Wir sind endgültig am bahnhof angekommen, bitte aussteigen...



> Leider reicht in manchen Fällen hie auch schon eine geringe Menge an Vertices (beim betroffenen Objekt waren es grad mal ca.2000). Lt. Murphy braucht man sich also gar nicht die Mühe machen, ein HashSet für Polygone zu verwenden, den alles was schiefgehen kann geht irgendwann schief. Deswegen ist es auch mehr oder weniger egal, was da für ein Hashcode berechnet wird, und wenn's der ist, den die VM erzeugt, wenn "hashCode()" nicht überschrieben wurde. Vllt. ist das auch ein Fall für "Ausnahmen bestätigen die Regel".


Was willst du mit den Polygonen machen?
Was soll dabei schief gehen?
Imho reden wir hier mittlerweile total aneinander vorbei :bahnhof:


> @Edit: "HashTable" hast du vergessen?


Äääh, egal... Andere Implementierung von HashMap... ändert nichts am Prinzip...


----------



## Spacerat (28. Mrz 2009)

0x7F800000 hat gesagt.:


> Was willst du mit den Polygonen machen?
> Was soll dabei schief gehen?


Mit den Polygonen... ehrlich gesagt nichts.
Was soll dabei schiefgehen? Nein... was ist schiefgegangen, was geht immer noch schief und wird stets weiter schiefgehen, selbst wenn "hashCode()" perfekt implementiert wurde, müsste die Frage lauten.
Ich habe die Vertices von 4 Objekten (ca. 2000 pro Objekt, alle Objekte die gleiche Anzahl) in jeweils einem HashSet gehalten.
In ein 5. Objekt habe ich das erste kopiert (neue Instanzen von Vertex). Dessen Vertices werden nun schrittweise zu den Positionen der Vertices in Objekt 2 verlagert, dann zu Objekt 3 und schliesslich zu Objekt 4 (und das ganze zurück: so funktioniert Morphing). Auf diesem langen Weg der Vertices, schien es, als würde das HashSet einige wenige davon verschlucken. Während die Size gleich blieb des Sets gleich blieb wurden plötzlich einige (3 oder 4) Vertices an ein und der selben Stelle gezeichnet, obwohl man dem vorherigen Verlauf genau entnehmen konnte, wo sie eigentlich hin sollten. Das Problem ist: egal wie "perfekt" deine Hash-Methode ist, du hast keine Kontrolle darüber, wann zwei verschiedene Vertices den selben Hashcode bekommen.


----------



## SlaterB (28. Mrz 2009)

0x7F800000 hat gesagt.:


> Bei der implementierung von equals sollte man hashCode nirgends verwenden, das hat da nichts verloren.


wenn der hashCode() für unveränderliche Objekte gecacht wird (oder bei selten zu ändernden Objekten auch gecacht und korrekt zurückgesetzt wird), 
kann man den schon für einen recht schnellen Vergleich nutzen,

ist nur ein Integer-Gleichheitstest, der bereits für 99% der nicht-gleichen Objekte ausreicht,
bei 10 einzeln zu vergleichenden Attributen einer Klasse recht verführerisch 

wobei je nach Statistik allerdings auch beim ersten oder zweiten Attribut der 10 zu vergleichenden meist recht bald ein 'false' kommen sollte,
spart doch nicht so viel wie ich zuerst dachte 

edit:
immerhin könnte man noch den Hashcode-Test vor instanceof machen,
das ist ja auch eine recht teuere Operation, wenn ich das korrekt erinnere


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> Ich habe die Vertices von 4 Objekten (ca. 2000 pro Objekt, alle Objekte die gleiche Anzahl) in jeweils einem HashSet gehalten.


Wieso eigentlich HashSet... Wie interpolierst du zwischen zwei figuren? Vertex1A wandert zu Vertex1B, Vertex2A wandert zu Vertex2B, Vertex3A wandert zu 3B, 4A zu 4B usw, oder ist das irgendwie komplexer? Falls das der fall ist, dann sehe ich keinen Grund nicht einfach eine ArrayList zu nehmen...


> Auf diesem langen Weg der Vertices, schien es, als würde das HashSet einige wenige davon verschlucken.


nun ja, wenn die vertices beim herumwandern zufällig zur gleichen zeit am gleichen ort vorbeikommen, werden sie vom Set selbstverständlich verschluckt, sonst wär's ja kein Set... Hättest du die Hash funktion falsch implementiert, würde der Set eben falsch funktionieren. Dieses "Verschlucken" ist eher ein Indiz dafür, dass die hashFunktion korrekt implementiert ist. Wenn du das nicht willst, dann, wie gesagt, nimm doch einfach eine Liste.


> Das Problem ist: egal wie "perfekt" deine Hash-Methode ist, du hast keine Kontrolle darüber, wann zwei verschiedene Vertices den selben Hashcode bekommen.


Nein, sollte man auch nicht, will man auch nicht. Hash funktion soll einfach alles durchmischen und eine möglichst chaotische, aber immer deterministische Zahl liefern. Solange die Hash-Funktion korrekt implementiert ist, funktioniert garantiert alles richtig. Von der Implementierung der Hash funktion hängt absolut nicht ab, OB irgendwas mit HashSets funktioniert, sondern nur WIE SCHNELL, vorausgesetzt die hash funktion erfüllt den Vertrag.
Wenn du willst, kannst du einfach

```
@Override
public int hashCode(){
    return 0;
}
```
setzen, das ist eine wunderbare Hash-Funktion, die offenbar den vertrag erfüllt und überhaupt in jeder Hinsicht bombensicher ist. HashSet wird damit funktionieren. Aber eben extrem langsam...

Ich raff immer noch nicht, was dein Problem ist, sorry... :autsch:


----------



## Spacerat (28. Mrz 2009)

@0x7F800000: An einander vorbei reden? Kann sein... wenn du davon ausgehst, dass ich die real vergleichende "equals()" Methode verwende...
Ich rede immer noch von der "fatalen" (Fällt mir natürlich erst jetzt auf, wo sich Slater zu Wort meldet). Also: Wenn ich die "real vergleichende" nehme, gib's mit HashSet ja keine Probleme. Allerdings ist HashSet dann auch weniger schnell, weil es eben bei gleichen Codes "equals()" aufruft (je schlechter die Berechnung desto häufiger die Verwendung, je besser die Berechnung, desto weniger schnell zu berechnen... richtig?). Ich hab' mir deswegen auch gedacht, wenn ich "equals()" dann schon "real vergleichend" implementieren muss, was nutzt dann noch das HashSet? Was brauchts dann noch ein HashCode? Die Tatsache, das ich letztenendes auch noch eher eine HashList (diese dusseligen Objekte können ja sogar zwei Vertices an ein und dem selben Fleck haben... :-( ) gebraucht hätte, haben mir Hash-Collections irgendwie komplett abgewöhnt.
@Edit: ArrayList? Gute Idee... nächstes Problem "Bounding Box"... Deswegen "HashSet", inzwischen TreeSet (obwohl eigentlich SortedList. war gar nicht so einfach...).
Mein Problem ist es, das ich nach wie vor mit diesem Kontrakt auf "Kriegsfuss" stehe. Bisher hats ja nicht viel gebracht, mit diesen HashCodes. Es geht mir hier keinesfalls um meine Morph-Objekte. Das war nur ein Beispiel.


----------



## Illuvatar (28. Mrz 2009)

Spacerat hat gesagt.:


> wenn ich "equals()" dann schon "real vergleichend" implementieren muss, was nutzt dann noch das HashSet? Was brauchts dann noch ein HashCode?



Wenn ein HashSet/HashMap/HashWasAuchImmer zwei Objekte vergleicht, wird zuerst überprüft, ob die zwei hashCodes identisch sind. Das ist eine "notwendige Bedingung" dafür, dass die Objekte gleich sind. Die hashCode-Methode sollte also optimalerweise schnell sein, aber trotzdem so oft wie möglich bei verschiedenen Objekten verschiedene Codes zurückgeben.
Erst wenn diese hashCodes gleich sind, wird die hinreichende Bedingung geprüft - die equals-Methode, die nun tatsächlich jede Variable einzeln vergleichen muss.

Die Variablen, die in die hashCode-Berechnung eingehen, müssen also eine Teilmenge der Variablen sein, die in equals vergleichen werden.

Was übrigens auch möglich ist, ist so eine equals-Methode:
[HIGHLIGHT="Java"]
public void equals (Object o)
{
  if (o == this) return true;
  if (!(o instanceof MyClass)) return false;
  if (o.hashCode() != this.hashCode()) return false; // !!!
  // eigentlicher Vergleich
}
[/HIGHLIGHT]
Im Falle z.B. einer HashMap ist das aber "doppelt gemoppelt".


----------



## 0x7F800000 (28. Mrz 2009)

Spacerat hat gesagt.:


> @0x7F800000: An einander vorbei reden? Kann sein... wenn du davon ausgehst, dass ich die real vergleichende "equals()" Methode verwende...
> Ich rede immer noch von der "fatalen" (Fällt mir natürlich erst jetzt auf, wo sich Slater zu Wort meldet).


Öhm... und in meinem ersten Beitrag habe ich was geschrieben?


> "hash==hash <=> equals==true" was natürlich *völlig ungeeignet* ist, da es ja (wie oben bemerkt) fast immer mehr verschiedene objektzustände gibt, als integer darstellen kann. Deine equals schmeißt sehr viele unterschiedliche Objekte in einen Topf, wie eine hash-funktion eben...


 Also kA wie ich das noch deutlicher ausdrücken soll: diese equals methode ist totaler schrott, und wenn damit irgendetwas zu funktionieren scheint, dann hast du einfach Glück gehabt.



> Also: Wenn ich die "real vergleichende" nehme, gib's mit HashSet ja keine Probleme. Allerdings ist HashSet dann auch weniger schnell, weil es eben bei gleichen Codes "equals()" aufruft


 Ähm, ja, so war es nun mal gedacht, und dummerweise hat bisher keiner was schnelleres als HashSet erfunden. Wenn es dir immer noch zu lahm ist, kannst du ja einfach mehr speicherplatz allokieren, dann sind kollisionen unwahrscheinlicher.
Oder du könntest deine megalahme "divisionsbasierte" hashCode-methode ausbessern, wie ich auch ober erwähnt hab. Aber du wirst nichts schneller als O(1) bekommen, das geht nun mal nicht. 


> Ich hab' mir deswegen auch gedacht, wenn ich "equals()" dann schon "real vergleichend" implementieren muss, was nutzt dann noch das HashSet? Was brauchts dann noch ein HashCode? Die Tatsache, das ich letztenendes auch noch eher eine HashList (diese dusseligen Objekte können ja sogar zwei Vertices an ein und dem selben Fleck haben... :-( ) gebraucht hätte, haben mir Hash-Collections irgendwie komplett abgewöhnt.


Das wird langsam echt irgendwie sinnfrei :autsch: 
Wie soll equals denn vergleichen außer "real vergleichend"? surreal vergleichend? oder einfach "ratend" wie deine "fatale" implementierung es tut??
Was soll eine HashList sein? Liste ist geordnet und kein set, HashSet ist prinzipiell ungeordnet und kann keine wiederholungen enthalten, das widerspricht sich einfach, ich kann mir im moment keine sinnvolle struktur vorstellen, die irgendwie beides sein soll.
Überhaupt, mal Hand auf's Herz: bist du dir sicher, dass du weißt wozu HashSets gut sind und wie sie funktionieren? Nichts für ungut, aber in den letzten paar Stunden ist bei mir ein etwas anderer Eindruck entstanden 


> @Edit: ArrayList? Gute Idee... nächstes Problem "Bounding Box"... Deswegen "HashSet", inzwischen TreeSet (obwohl eigentlich SortedList. war gar nicht so einfach...).


what... 
Wenn du irgendwelche geometrische sachen sortieren willst, dann sind BSP- bis Octrees meistens eher geeignet.


> Mein Problem ist es, das ich nach wie vor mit diesem Kontrakt auf "Kriegsfuss" stehe. Bisher hats ja nicht viel gebracht, mit diesen HashCodes. Es geht mir hier keinesfalls um meine Morph-Objekte. Das war nur ein Beispiel.


wieso auf Kriegsfuß... was hat dir dieser Fuß denn getan... 
was soll so unverständlich an "A.equals(B)=true => A.hash=B.hash" sein?
Ehrlich gesagt kommt es mir grad wirklich so vor, als ob du noch nie selbst eine HashMap implementiert hättest... Solltest du zur Übung mal machen, ok? :bahnhof:


----------



## Spacerat (28. Mrz 2009)

Nein... hab' ich auch nicht... BSP- und Octrees sagen mir auch nichts. Das einzige, was ich diesbezüglich mal gemacht habe war so eine Art HashSet. Objekte die dort aufgenommen werden sollten mussten ein Interface mit einer Methode "toByteArray()" implementieren. Aufgrund dieser Arrays habe ich eine Baumstruktur angelegt, in welcher die einzelnen Bytes von Root ausgehend mit dem niederwertigsten angefangen abgelegt habe. am Ende einer solchen Kette wurde dieser Node dann das Objekt als Wert übergeben. Wenn ich es mir recht überlege, könnte das etwa ein Octree sein (Byte -> 8-Bit Octett)? Dann kenn ich nur (wie sooft) den Fachbegriff nicht.





			
				0x7F800000 hat gesagt.:
			
		

> mal Hand auf's Herz: bist du dir sicher, dass du weißt wozu HashSets gut sind und wie sie funktionieren?


Ich weiss wie sie funktionieren, aber wozu solls gut sein, wenn man in der Art des Hashes so begrenzt ist?


----------



## SchonWiederFred (28. Mrz 2009)

Spacerat hat gesagt.:


> ein Vertex besteht bei mir aus 3x float (96 Bit).


In Deinem Quellcode sieht es so aus, als würdest Du dafür ein Array benutzen. Das ist unnötig viel Overhead in Java. Nimm lieber 3 normale float-Variablen.

Ich empfehle Dir dringen, dieses Kapitel aus Effective Java zu lesen. Da steht alles drin, was man über equals und hashCode wissen muss.

Ich würde die Vertex-Klasse folgendermaßen entwerfen:

```
class Vertex
{
	public final float x, y, z;
	private final int hash;

	public Vertex(float x, float y, float z)
	{
		this.x = x;
		this.y = y;
		this.z = z;

		int hash = 17;
		hash = hash * 31 + Float.floatToRawIntBits(x);
		hash = hash * 31 + Float.floatToRawIntBits(y);
		hash = hash * 31 + Float.floatToRawIntBits(z);
		this.hash = hash;
	}

	@Override
	public boolean equals(Object o)
	{
		if (!(o instanceof Vertex)) return false;
		Vertex v = (Vertex) o;
		return x==v.x & y==v.y & z==v.z;
	}
	
	@Override
	public int hashCode()
	{
		return hash;
	}
}
```

Der Test auf null ist übrigens nicht erforderlich, da "null instanceof AnyType" immer false liefert. Steht glaube ich auch in dem verlinkten Artikel.


----------



## mvitz (28. Mrz 2009)

SchonWiederFred hat gesagt.:


> ...
> [HIGHLIGHT="Java"]
> class Vertex
> {
> ...



So ist es vermutlich noch ein wenig performanter.


----------



## SchonWiederFred (28. Mrz 2009)

habi55 hat gesagt.:


> if(o == this) return true;


Ist es nicht eher unwahrscheinlich, dass man ein Objekt mit sich selbst vergleicht? In den meisten Fällen wird der Vergleich false ergeben und unnötig Rechenzeit schlucken.



habi55 hat gesagt.:


> if(hash != o.hash()) return false;


Das scheint mir dagegen sehr sinnvoll zu sein. In 99,9999999% der Fälle findet man hier schon das korrekte Ergebnis. Sehr schön!



habi55 hat gesagt.:


> return x==v.x && y==v.y && z==v.z;


Die doppelten && finde ich dagegen wieder eher unschön, da hier viele bedingte Sprünge stattfinden. Wenn wir schon so weit gekommen sind, dann handelt es sich wahrscheinlich um das gleiche Objekt, da will ich ganz normale boolsche Algebra ohne Abkürzungen fahren.

So würde ich es jetzt machen:

```
public boolean equals(Object o)
{
	if (!(o instanceof Vertex)) return false;
	Vertex v = (Vertex) o;
	if (hash != v.hash) return false;
	return x==v.x & y==v.y & z==v.z;
}
```


----------



## mvitz (28. Mrz 2009)

also der erste Vergleich stammt auch aus Effective Java als Tipp, man solle es so machen. Kommt denke ich auf den Anwendungsfall drauf an.

Das mit & vs &&:
Der einzige Unterschied ist doch (zumindest nahm ich das bisher immer an), dass bei dem ersten Vergleich, der false ergibt der gesamte Ausdruck immer false ergibt und man sich somit im Idealfall 2 Vergleiche spart, die man bei deiner Variante trotzdem noch macht. (x == v.x ergibt false --> bei mir würde sofort aufgehört, bei dir würde trotzdem noch y == v.y und z == v.z geprüft).
Die eigentliche Frage, ist ein & wirklich performanter als ein && ?


----------



## SchonWiederFred (28. Mrz 2009)

Hm, selbst mit dem einfachen & kommt es zu bedingten Sprüngen, das hätte ich nicht gedacht.

```
27:	aload_0
   28:	getfield	#17; //Field x:F
   31:	aload_2
   32:	getfield	#17; //Field x:F
   35:	fcmpl
   36:	ifne	43
   39:	iconst_1
   40:	goto	44
   43:	iconst_0
   44:	aload_0
   45:	getfield	#19; //Field y:F
   48:	aload_2
   49:	getfield	#19; //Field y:F
   52:	fcmpl
   53:	ifne	60
   56:	iconst_1
   57:	goto	61
   60:	iconst_0
   61:	iand
   62:	aload_0
   63:	getfield	#21; //Field z:F
   66:	aload_2
   67:	getfield	#21; //Field z:F
   70:	fcmpl
   71:	ifne	78
   74:	iconst_1
   75:	goto	79
   78:	iconst_0
   79:	iand
   80:	ireturn
```
Bin wohl zu verwöhnt von C  Naja, dann nehmen wir halt doch lieber die doppelten &&

```
27:	aload_0
   28:	getfield	#17; //Field x:F
   31:	aload_2
   32:	getfield	#17; //Field x:F
   35:	fcmpl
   36:	ifne	65
   39:	aload_0
   40:	getfield	#19; //Field y:F
   43:	aload_2
   44:	getfield	#19; //Field y:F
   47:	fcmpl
   48:	ifne	65
   51:	aload_0
   52:	getfield	#21; //Field z:F
   55:	aload_2
   56:	getfield	#21; //Field z:F
   59:	fcmpl
   60:	ifne	65
   63:	iconst_1
   64:	ireturn
   65:	iconst_0
   66:	ireturn
```
Also dann würde ich es jetzt so implementieren:

```
public boolean equals(Object o)
{
	if (!(o instanceof Vertex)) return false;
	Vertex v = (Vertex) o;
	if (hash != v.hash) return false;
	return x==v.x && y==v.y && z==v.z;
}
```


----------



## Spacerat (28. Mrz 2009)

<completely offtopic>Doch... die Sache mit dem Vertex... da hätten mir 3 floats auch besser gefallen, allerdings veränderbar. Immutables haben bei 3D-Anwendungen meiner Meinung nach rein gar nichts verloren (hatte da schon mal an anderer Stelle drüber geschrieben: Wenn man bei einer FrameRate von ca. 25 FPS 300 Vertices neu Instanzieren muss, weil man sie bewegen will, wird der GarbageCollector gnadenlos überlastet. Jetzt bewege ich 300 Vertices @ ca. 140 FPS). Ferner brauche ich Kontrolle darüber, wann so ein Vertex verändert wird, damit ich ggf. z.B. meine Objekte neu initialisieren kann. Schliesslich arbeite ich mit JOGL und "gl.glVertex3fv(float[])" geht schneller als "gl.glVertex3f(float, float, float)".</completely offtopic>
Das PDF werd' ich mir mal antun. Danke dafür.


----------



## SlaterB (28. Mrz 2009)

bewegliche Vertex steckt man dann auch nicht in eine HashMap


----------



## Spacerat (28. Mrz 2009)

SlaterB hat gesagt.:


> bewegliche Vertex steckt man dann auch nicht in eine HashMap


Hab' oben schon irgendwo erwähnt (bei der länge des Threads wohl utergegangen). Es hat zwar 'n bissl gedauert, aber zu der Einsicht (der Thread ist mehr oder weniger die Folge davon...) bin ich auch schon gekommen. Immerhin gewährt eine HashMap ja recht schnellen Zugriff (bei korrekter Verwendung versteht sich) auf ihre Elemente. Aber mit der Einsicht kam eben die Ernüchterung und die "Frage was soll das mit diesem Kontrakt?". Mir sind halt die Anwendungsgebiete einer HashMap (oder HashWasAuchImmer) ausgegangen. Und die Tatsache, das man es nicht tut, warf dann eben noch die Frage auf, warum man grundsätzlich "hashCode()" überschreiben soll, wenn mann "equals()" überschreibt. Wenn ein Objekt nicht in ein HashWasWeisIch gehört, wozu "hashCode()"? <- Die Fragen stelle ich hier nicht wirklich... steht ja mehr oder weniger schon alles in diesem Thread (und ein wenig mehr hoffentlich in dem PDF).


----------



## SlaterB (28. Mrz 2009)

ich bin auch ein Befürworter der These 'equals() kann auch ohne hashCode() leben', falls dich das freut 

veränderliche Objekte sind ein ziemlich gutes Beispiel, die sollte man eh nicht in eine Map einfügen,
das Argument muss ich mir merken


----------



## Spacerat (28. Mrz 2009)

SlaterB hat gesagt.:


> ich bin auch ein Befürworter der These 'equals() kann auch ohne hashCode() leben', falls dich das freut


:toll: Dann sind wir ja schon zwei... Wie wärs mit ner Umfrage (kl. Scherz). Vllt. wächst unsere Anhängerschaft ja noch.


----------



## SlaterB (28. Mrz 2009)

hier ein Ausschnitt aus dem PDF zu hashCode()


> Whenever it is invoked on the same object more than once during an execu-
> tion of an application, the hashCode method must consistently return the
> same integer, provided no information used in equals comparisons on the
> object is modified. This integer need not remain consistent from one execu-
> tion of an application to another execution of the same application.


bzw. steht auch in der Object-API

es ist also schwachsinnig, zu versuchen, den hashCode immer den aktuellen Status des Objektes nachhächeln zu lassen,
das funktioniert in einer Map sowie nicht, wenn sich das Objekt ändern darf

edit: jetzt hab ich 'providing ..' nicht gelesen  , bei Änderung machts trotzdem keinen Sinn


----------



## 0x7F800000 (28. Mrz 2009)

SlaterB hat gesagt.:


> ich bin auch ein Befürworter der These 'equals() kann auch ohne hashCode() leben', falls dich das freut
> 
> veränderliche Objekte sind ein ziemlich gutes Beispiel, die sollte man eh nicht in eine Map einfügen,
> das Argument muss ich mir merken


solange ihr mit
[highlight=Java]
@Override 
public int hashCode(){
   throw new UnsupportedOperationException("this isn't supposed to be used in hash-structures");
}
[/highlight]
dafür sorgt, dass es da keine verwirrung gibt, ist alles in Ordnung.


----------



## Spacerat (28. Mrz 2009)

Dann war meine anfängliche Annahme ja gar nicht so (wenn überhaupt) daneben. Wenn mich meine Englischkenntnisse nicht trügen, lautet der frei übersetzte Text etwa so:





> Wann immer "hashCode()" während der Ausführung einer Anwendung auf ein und das selbe Objekt aufgerufen wird, muss der selbe Integer, ohne Aussage darüber, ob sich in "equals()" verwendete Werte geändert haben, zurückgegeben werden. Dieser Integer darf bei jedem Neustart der selben Anwendung ein anderer sein.


Und so etwas steht in der API? ( :rtfm: ) ähhm stimmt. Ist mir ja fast peinlich, das ich nicht selbst nachgeschaut habe (nö, ist es gar nicht... auch wenn von einigen vielen nun eine eingemeisselte Vorstellung einbricht, wir haben doch alle was davon). Und die Exception können wir uns dann ja wohl auch sparen.
@07F800000: Verwirrt?


----------



## SlaterB (28. Mrz 2009)

> ohne Aussage darüber, ob sich in "equals()" verwendete Werte geändert haben

naja :shock: , eher

"vorausgesetzt, dass sich keine Information, die ein equals() verwendet wird, geändert hat"


deshalb auch mein edit im letzen Posting


----------



## Spacerat (28. Mrz 2009)

...was solls... dan trügen mich meine Englischkenntnisse eben... Hatte schon angenommen, das sich alle Irren und wir Recht haben. Aber so, müssen wir ja doch die Exception bringen...? aaach s.d. da steh ich drüber...


----------



## Marco13 (29. Mrz 2009)

Wir sollten auch einen "Oscar für den verwirrendsten Thread" einführen ... ???:L

Irgendwie hab' ich immernoch nicht kapiert, wieso du überhaupt Vertices in eine Set oder speziell ein HashSet einfügen willst... ?!


----------



## 0x7F800000 (29. Mrz 2009)

Marco13 hat gesagt.:


> Irgendwie hab' ich immernoch nicht kapiert, wieso du überhaupt Vertices in eine Set oder speziell ein HashSet einfügen willst... ?!


Betriebsgeheimnis...:bahnhof:

[forum.getUserByName("0x7F800000").decrementCounter() ]


----------



## Spacerat (29. Mrz 2009)

Marco13 hat gesagt.:


> Irgendwie hab' ich immernoch nicht kapiert, wieso du überhaupt Vertices in eine Set oder speziell ein HashSet einfügen willst... ?!


Nee... kein Bertriebsgeheimnis... steht aber auch schon öfter da... z.B. hier: http://www.java-forum.org/java-basi...69-equals-hashcode-contract-2.html#post502693
Was ich urig finde, ist die Tatsache, das man hier immer nur gefragt wird, "warum willst du das so machen?" wenn die Antworten darauf schon längst gegeben worden sind. Solche Fragen lösen das Problem nicht. Mir fehlen nach wie vor konkrete Anwendungsgebiete für "HashXxxx" (stellvertreted für alle). Die Frage, ob ich "hashCode()" auch weglassen kann, wenn ich nur einen inhaltlichen Vergleich brauch', beantworte ich mir derweil mal mit "Ja", bis sich ein vernünftiges Anwendungsgebiet gefunden hat.
Für meine Objekte verwende ich inzwischen im Prinzip eine simple ArrayList. Naja... besser 'ne eigene Collection-Implementation, mit einer internen Arraylist, bei der sich ModificationListener registrieren können und ich Elemente selektieren und deselektieren kann. Auf die Sortierbarkeit wurde inzwischen komplett verzichtet, da das nur notwendig war, um die Bounding-Box eines Objekts fest zu stellen. Die Bounds-Klasse merkt sich maximale und minimale Achs-Werte des Objekts, registriert sich in der Liste als ModificationListener und wenn sich so ein Vertex nun verschoben hat bekommt sie das mit. Ggf. speichert sie dann auch neue (Min/Max) Achs-Werte.


----------



## SlaterB (29. Mrz 2009)

> steht aber auch schon öfter da... z.B. hier: 

es hilft nicht besonders, auf ein Post zu verweisen, in welchem auch nur 'Hab' oben schon irgendwo erwähnt' steht oder meinst du einen anderen Satz(-teil)?

> Immerhin gewährt eine HashMap ja recht schnellen Zugriff (bei korrekter Verwendung versteht sich) auf ihre Elemente. 

finde ich nicht gerade spezifisch,

aber ich übernehme jetzt die Pionieraufgabe, die mir noch unbekannte erste Seite durchzulesen,
vielleicht finde ich was und poste es dann hier noch als edit 

---------

edit:
also zum Teil vertrittst du ja die Position 'will gar kein hashCode implementieren', woraus eigentlich nur 'will kein HashSet/Map/Table verwenden' zu schließen ist,

dann kommt aber vermutlich doch eine HashSet-Anwendung,
> Will man dieses Dreieck in einem Hashset (wegen dem schnelleren Zugriff) zu einem Polygon zusammenfassen wirds ein Problem. Na klar: Kein Mensch weiss vorher, welche Vertices jeweils dieses Problem ergeben.
http://www.java-forum.org/java-basi...1069-equals-hashcode-contract.html#post502482

im weiteren noch etwas ausgeführt, aber für mich trifft da ehrlicherweise nur die Aussage von 0x7F800000 zu:
> bahnhof. Ich raff endgültig nichts mehr. Was ist denn nun das Problem omg?!

wenn du doch HashSets verwendest, dann sicherlich so, dass sich die Objekte darin während des Enthaltenseins nicht ändern,
auch wenn sie allgemein vielleicht änderbar sind (Referenz-Objekte oder so)
in dem Fall macht dann aber eine einigermaßen gute Hashfunktion Sinn, eine KORREKTE Hashfunktion (zu equals passend) wäre absolute Voraussetzung,
ohne hashCode kein HashSet, einfache Regel,

ob du aber HashSets brauchst und wofür genau ist mir immer noch nicht 100% klar,
wenn du das weiter ausführen willst, dann besser in einem neuen Post in einfachen verständlichen Worten,
nicht

> Ich habe die Vertices von 4 Objekten (ca. 2000 pro Objekt, alle Objekte die gleiche Anzahl) in jeweils einem HashSet gehalten.
> In ein 5. Objekt habe ich das erste kopiert (neue Instanzen von Vertex). Dessen Vertices 
> werden nun schrittweise zu den Positionen der Vertices in Objekt 2 verlagert, dann zu 
> Objekt 3 und schliesslich zu Objekt 4 (und das ganze zurück: so funktioniert Morphing).


obwohl ok, das ist nun recht deutlich, dass du HashSets hast


----------



## 0x7F800000 (29. Mrz 2009)

Spacerat hat gesagt.:


> Mir fehlen nach wie vor konkrete Anwendungsgebiete für "HashXxxx" (stellvertreted für alle).


Bezogen auf dein Problem? (da scheint es keine Anwendungen zu geben) Oder kannst du dir allgemein nicht vorstellen, wozu man ein Hashset gebrauchen soll? :shock:

Ich meine... den braucht man doch einfach dauernd und überall, wenn man einfach eine Menge darstellen will, von der man vorher nichts weiß. Gestern habe ich wieder angefangen mit kontextfreien Grammatiken rumzubasteln (disesmal in Java).
Da kommt durchschnittlich in jeder 10 Zeile irgendein "HashXyz" vor, das gesammte ding arbeitet bisher praktisch ausschließlich mit den Strukturen HashMap<T,HashSet<T>> (die eben eine Funktion darstellen, die Symbolen Mengen von anderen Symbolen zuordnen, sowas wie FIRST-sets oder so). Nur so als Beispiel... :bahnhof:


----------



## Marco13 (29. Mrz 2009)

Spacerat hat gesagt.:


> Was ich urig finde, ist die Tatsache, das man hier immer nur gefragt wird, "warum willst du das so machen?" wenn die Antworten darauf schon längst gegeben worden sind. Solche Fragen lösen das Problem nicht.



Ja, wieder mein altes Beispiel: Wenn jemand Fragt: "Wie kann ich mit einer KaffeeTasse einen Nagel in die Wand hauen, ohne dass sie kaputt geht?" sollte man nicht beschreiben, wie man eine Kaffeetasse aus Glasfasterverstärktem Kohlenstoff herstellt, sondern man sollte sagen: Nimm einen Hammer!

Und in diesem Fall: Nimm eine ArrayList!

Die einzige Aussage im verlinkten Beitrag, die man als "Rechtfertigung" für die Verwendung einer ArrayList ansehen könnte, wäre
_Immerhin gewährt eine HashMap ja recht schnellen Zugriff (bei korrekter Verwendung versteht sich) auf ihre Elemente_
Allerdings solltest du dir im Klaren sein:
- Eine HashSet enthält jedes Element nur EIN mal - wenn also zwei Vertices zufällig mal am selben Platz landen, verschwindet einer von beiden, was GARANTIERT nicht erwünscht ist
- ArrayList erlaubt schnelleren Zugriff als HashSet (und für dein Problem auch sinnvolleren, nämlich _indizierten_ Zugriff)


Ein bißchen mehr Kontextinformation wäre vielleicht hilfreich - oder ein bißchen weniger. Wenn es dir NUR im den Contract von hashCode und equals geht, hier eine mögliche Antwort:

Eine HashSet kann man sich (vereinfacht) vorstellen als einen Array aus Listen. 
List listArray[] = new List[100];
Jedes Element dieses Arrays enthält die Liste der Objekte, die den gleichen HashCode haben. Wenn ein neues Objekt eingefügt wird, wird prinzipiell sowas gemacht wie

```
void add(Object object)
{
    int arrayIndex = object.hashCode() % 100;
    List list = listArray[arrayIndex];
    if (!list.contains(object))
    {
        list.add(object);
    }
}
```
Bei einer "guten" HashMap enthalten diese Listen immer nur EIN Element. Wenn aber zwei oder mehr Elemente den gleichen HashCode haben, dann müssen in so eine Liste auch mal zwei oder mehr Elemente eingefügt werden. Voraussetzung für das Einfügen ist aber, dass die jeweilige Liste nicht schon das GLEICHE Element enthält, d.h. die Liste darf kein Element enthalten, bei dem 
neuesElement.equals(vorhandenesElement);
gilt. WENN sie schon so ein Element enthält, wird das neue nicht eingefügt.

Jetzt kann man sich klarmachen, wozu der "Contract" von equals und hashCode gut ist: In einer Set dürfen NIE zwei Elemente liegen, die "equals" sind. Und die Bedinungen für equals und hashCode dienen dem Zweck, sicherzustellen, dass das NIE passiert. 

Es könnte nämlich passieren, dass verbotenerweise zwei "equale" Elemente in der HashSet liegen, wenn...
- zwei Elemente, die "equals" sind, unterschiedliche HashCodes liefern
- sich vorhandene Objekte NACH dem Einfügen so verändern, das sie "equals" zu einem anderen bereits eingefügen Element werden
- sich vorhandene Objekte NACH dem Einfügen verändern, dass ihr hashCode sich verändert



Wenn es dir um eine Datenstruktur geht, mit der man Morphing durchführen kann, kommt dafür IMHO(!) nur eine geordnete (nicht sortierte, sondern geordnete) Datenstruktur mit effizientem indiziertem Zugriff in Frage - also eine (Array)List.

_Für meine Objekte verwende ich inzwischen im Prinzip eine simple ArrayList. Naja... besser 'ne eigene Collection-Implementation, mit einer internen Arraylist, bei der sich ModificationListener registrieren können und ich Elemente selektieren und deselektieren kann. Auf die Sortierbarkeit wurde inzwischen komplett verzichtet, da das nur notwendig war, um die Bounding-Box eines Objekts fest zu stellen. Die Bounds-Klasse merkt sich maximale und minimale Achs-Werte des Objekts, registriert sich in der Liste als ModificationListener und wenn sich so ein Vertex nun verschoben hat bekommt sie das mit. Ggf. speichert sie dann auch neue (Min/Max) Achs-Werte._

Mit anderen Worten ist deine BoundinBox jetzt ein Listener auf bestimmte Vertices des Objektes?!? Wie oft muss die BoundingBox berechnet werden? Musst du nicht für das Morphing und etliche andere Operationen sowieso hin und wieder über alle vertices laufen, so dass du dort die BoundingBox "nebenbei" berechnen könntest? 

(Mir ist ehrlich gesagt schleierhaft, wie du Morphing zwischen mehreren Objekten mit einer Datenstruktur machen willst oder wolltest, die keinen indizierten Zugriff bietet, und bei der sich die Reihenfolge der Enthaltenen Elemente jederzeit beliebig ändern kann... ???:L )


----------



## Spacerat (29. Mrz 2009)

0x7F800000 hat gesagt.:
			
		

> Bezogen auf dein Problem? (da scheint es keine Anwendungen zu geben) Oder kannst du dir allgemein nicht vorstellen, wozu man ein Hashset gebrauchen soll?


Und du erzählst mir, du verstündest nur Bahnhof? 
Genau so ist es: Ich habe HashSet nur wegen dem schnellen Zugriff gewählt (wenn man's genau nimmt, ohne wirklich zu Wissen was es damit aufsich hat). Die "fatale" "equals()"-Implementation war (wie SlaterB schon so schön sagte) sehr verführerisch. Und da sich das ganze nun als Fatal erwiesen hat, ging eben meine gesamte Vorstellung von diesem "Contract" die Wupper runter, und damit auch alle AnwendungsGebiete mit HashXxxx. Die Frage, ob man "hashCode()" nun einfach beiseite lassen kann, erschloss sich dann so:
Die Vertex-Instanz bleibt die gesammte Laufzeit über immer ein und dieselbe, auch wenn sich dessen Lage ändert ("hashCode()" so zu sagen als Instanzkennung). Zeitweilig muss aber dennoch der Inhalt zweier Vertices verglichen werden -> "equals()" (ok... dazu hätte man auch "Compareable" implementieren können und ich hätte mir einige Blamagen erspart... für Geistesblitze ist es 'nu wirklich bissl spät.  ). Ich hatte angenommen, ich würde das HashSet eben nicht aus dem Tritt bringen, wenn ich das so handhabe (also: "hashCode()" nicht zu überschreiben). HashXxxx könnte so auch mehrere gleiche Vertices aufnehmen.


----------



## 0x7F800000 (29. Mrz 2009)

Marco13 hat gesagt.:


> - ArrayList erlaubt schnelleren Zugriff als HashSet (und für dein Problem auch sinnvolleren, nämlich _indizierten_ Zugriff)


"Zugriff"... Was ist "Zugriff" soll sich da jeder vorstellen was er will oder wie?:noe:
Bis du den Spacerat noch mehr verwirrst, was die nützlichkei von HashSets angeht: Random access geht bei ArrayList in O(1), FIND dagegen in O(n). Bei HashSets is FIND dagegen sehr billig, nämlich O(1), und indizierten zugriff gibts nicht, weil's sinnfrei ist.



Spacerat hat gesagt.:


> HashXxxx könnte so auch mehrere gleiche Vertices aufnehmen.


Klasse. Dann lautete die Frage wohl eher "wie haue ich mit einer Kaffetasse einen Nagel in die Wand, sodass die tasse dabei in möglichst viele scharfe Splitter zerspringt". Lass das mit der Absichtlichen Sabotage von Datenstrukturen, das ist sinnfrei.

Ich will gar nicht fragen, wieso du jetzt plötzlich Vertices als Comparable in R³ implementieren willst, sonst geht gleich genau derselbe Chaos mit SortedSets los :autsch:
Lass es auch, das ist noch zweckentfremdeter, was auch immer du damit vorhast...


----------



## Marco13 (29. Mrz 2009)

0x7F800000 hat gesagt.:


> "Zugriff"... Was ist "Zugriff" soll sich da jeder vorstellen was er will oder wie?:noe:


Darunter sollte Spacerat sich das vorstellen, was er mit "Zugriff" gemeint hat  Zu hinterfragen, was das ist, ist aber gerechtfertigt.


----------



## 0x7F800000 (29. Mrz 2009)

Marco13 hat gesagt.:


> Darunter sollte Spacerat sich das vorstellen, was er mit "Zugriff" gemeint hat  Zu hinterfragen, was das ist, ist aber gerechtfertigt.


Ich wage sogar mal die These aufzustellen, dass dies die Wurzel allen Übels ist.


----------



## SchonWiederFred (29. Mrz 2009)

Spacerat hat gesagt.:


> Wenn man bei einer FrameRate von ca. 25 FPS 300 Vertices neu Instanzieren muss, weil man sie bewegen will, wird der GarbageCollector gnadenlos überlastet.


Hast Du das gemessen? Kurzlebige Objekte sind für den Garbage-Collector eigentlich überhaupt kein Problem. Was Zeit kostet, sind die lebendigen Objekte, nicht die toten.



Spacerat hat gesagt.:


> Schliesslich arbeite ich mit JOGL und "gl.glVertex3fv(float[])" geht schneller als "gl.glVertex3f(float, float, float)".


glVertex3f -- du schiebst einzelne Vertices durch die Pipeline und diskutierst über Performance?


----------



## Spacerat (29. Mrz 2009)

@Fred: 1.GL ist nicht das Thema, und nein, ich schiebe keine einzelnen Verts in die Pipe. Und über Performance diskutiere ich hier auch nicht.
2. Gemessen! Wenn ein FrameCounter bei der Verwendung von "new" ca. 12 FPS, und bei (ich nenne es mal) Objekt-Recycling (nicht mehr aktuelle Vertices wieder verwenden) ca. 143 FPS anzeigt, gehe ich mal davon aus, das der GC nicht mitkommt...
@All: Zugriff steht da allgemein, weil's so gemeint ist. In jeder Hinsicht am schnellsten drauf zugreifen können (Iterativ, Suchindex, wie auch immer). Weil's finally nicht ging, kam mir die Idee: sollen sich veränderte Vertices halt irgendwo melden. Ich muss nun also nirgends mehr in irgendeiner Liste suchen. Irgendwelche Hash-Collections verwende ich deswegen auch schon lange nicht mehr (Wie alt ist der Thread? Ungefähr solange ist's her.). In diesem Thread ging es auch niemals darum, das eine zu verwenden und das andere doch besser sein zu lassen. Es ging immer nur um die Frage.... Wir drehen uns im Kreis...
@0x7F800000: "...das dies die Wurzel allen übels ist." Den Nagel auf den Kopf getroffen, würd' ich sagen.
Wär doch zu schön gewesen:
Instanzierungscode als Suchindex, realisiert indem man "hashCode()" einfach nicht überschreibt. HashSet könnte so verschiedene Instanzen aufnehmen, die sogar "equal()" sein dürfen. Aber halt... dann wär's ja 'ne Liste...(@0x7F800000 hattest du mich nicht im Verlaufe dieses Threads nach einer HashList gefragt? Bidde schön, here you are) Nicht zufällig 'ne Liste, die schneller als jede ArrayList gewesen wär (vgl. "get()")? Welch ein verwerflicher Gedanke... der Contract ist ja sowas von in Stein gemeisselt... und wenn man's hinterfragt, blamiert man sich bis aufs Blut... Egal da steh' ich drüber.


----------



## 0x7F800000 (29. Mrz 2009)

Spacerat hat gesagt.:


> In jeder Hinsicht am schnellsten drauf zugreifen können (Iterativ, Suchindex, wie auch immer).


Würde vielleicht mit einer Hybridstruktur a'la 
SparseArrayList<T>+HashMap<T,List<SmartPointer<T>>>
evtl. sogar alles in O(1) gehen? ???:L Das Ding hätte aber einen ziemlichen Overhead, und würde für zB. <1000000 Objekte sowohl gegen gewöhnliche ArrayLists als auch gegen HashSets total versagen... Außerdem ich verstehe nach wie vor nicht, wozu sowas gut sein sollte, irgendein zuendegedachtes Beispiel konntest du nach wie vor nicht liefern, bzw es ist "irgendwo hier" untergegangen...



> Dann wäre da Weil's finally nicht ging, kam mir die Idee: sollen sich veränderte Vertices halt irgendwo melden. Ich muss nun also nirgends mehr in irgendeiner Liste suchen.


du recyclest also vertices zur optimierung, und dann wendest du darauf Listener-Pattern an? Hmm, naja, hört sich zwar abenteuerlich an, aber wer weiß...



> Nicht zufällig 'ne Liste, die schneller als jede ArrayList gewesen wär (vgl. "get()")?


Bei RandomAccess schneller als eine ArrayList? Das soll ja wohl'n scherz sein... ;(ArrayList baut direkt auf Arrays auf, schneller als Arrays läuft nichts. Das wird direkt hardwaremäßig so schnell erledigt wie nichts anderes.
Nochmal: O(1) von FIND in HashSet und O(1) bei RANDOM_ACCESS in ArrayList sind nur _asymptotisch_ gleich. In diesem fall würde ich mal vermuten, dass FIND bei HashSet paar hundert mal langsamer ist, aber es ist eben auf dauer ein *konstanter Faktor*. Mit einer HashMap Random-Access zu simulieren ist Irrsinn, das läuft sicherlich um einen Faktor langsamer. Diese Hash-Dinger sind dafür nun mal nicht gebaut, ende.


----------



## Spacerat (30. Mrz 2009)

0x7F800000 hat gesagt.:


> Würde vielleicht mit einer Hybridstruktur a'la
> SparseArrayList<T>+HashMap<T,List<SmartPointer<T>>>
> evtl. sogar alles in O(1) gehen? ???:L Das Ding hätte aber einen ziemlichen Overhead, und würde für zB. <1000000 Objekte sowohl gegen gewöhnliche ArrayLists als auch gegen HashSets total versagen... Außerdem ich verstehe nach wie vor nicht, wozu sowas gut sein sollte, irgendein zuendegedachtes Beispiel konntest du nach wie vor nicht liefern, bzw es ist "irgendwo hier" untergegangen...


Ja, sowas wär's wohl auch geworden. Bin in diesem Fall leider, sonst wohl glücklicherweise schon vorher, meiner "fatalen" "equals()"-Implementation sei dank, am einfachen HashSet gescheitert. Wär mir das nicht passiert, wer weis, vllt. hätten wir erfahren ob es versagt hätte. Das Beispiel ist tatsächlich noch nirgends konkret erwähnt. Ich wollte, dass während des Morphvorganges die Bounding-Box des Objekts ständig aktuell gehalten wird, damit sie nicht erst bei einer Kollisionsabfrage berechnet werden muss. Dazu hätte ich dann wissen müssen an welcher Stelle der Vertex im Set gelegen hätte, ihn an erste, bzw. letzte Stelle verfrachten usw...


			
				0x7F800000 hat gesagt.:
			
		

> du recyclest also vertices zur optimierung, und dann wendest du darauf Listener-Pattern an? Hmm, naja, hört sich zwar abenteuerlich an, aber wer weiß...


Listener-Pattern: Im Augenblick schon noch ja... Und wenn ich mir's recht überlege, hatte ich diesbezüglich wohl grad' 'nen Pfeil im Kopf. Deswegen versuche ich grad' die BB während des Iterierens über die Vertices zu erstellen (wie weiter oben vorgeschlagen...). Das hat aber nichts mit dem Recycling zu tun. Das dient ausschliesslich der Vermeidung von "new", und das bleibt so. (Hoff' du erinnerst dich, an deinen "BenchMark" mit dieser "if-Geschichte" hier). Vorm iterieren lege ich dazu ein einziges float[3]-Array an welches ich dann zwecks Interpolation durch die Vertices reiche. Das Resultat landet dann per "gl.glVertex3fv()" in einer GL_LIST.



			
				0x7F800000 hat gesagt.:
			
		

> Bei RandomAccess schneller als eine ArrayList? Das soll ja wohl'n scherz sein... ;(ArrayList baut direkt auf Arrays auf, schneller als Arrays läuft nichts. Das wird direkt hardwaremäßig so schnell erledigt wie nichts anderes.
> Nochmal: O(1) von FIND in HashSet und O(1) bei RANDOM_ACCESS in ArrayList sind nur _asymptotisch_ gleich. In diesem fall würde ich mal vermuten, dass FIND bei HashSet paar hundert mal langsamer ist, aber es ist eben auf dauer ein *konstanter Faktor*. Mit einer HashMap Random-Access zu simulieren ist Irrsinn, das läuft sicherlich um einen Faktor langsamer. Diese Hash-Dinger sind dafür nun mal nicht gebaut, ende.


Nee... das sollte kein Scherz sein... Am Anfang deines Posts hast du ja noch gesagt, das könnte klappen mit dieser Hybrid-Geschichte. So brannte es sich eigenlich auch in meine Vorstellung. Mom, ich verwerfs mal eben .

So, ich komm dann mal zu dem Schluss, das man "hashCode()" also nicht weglassen sollte, wenn man "equals()" überschreibt. Bei Objekten wie z.B. Vertices (also Objekte wo man weiss, das sie kaum in Hash-Collections verwendet werden können) genügt dann auch "return toString().hashCode()", sofern man in der "toString()"-Methode alle in "equals()" verwendeten Werte einschliesst.


----------



## Marco13 (30. Mrz 2009)

_Bei Objekten wie z.B. Vertices (also Objekte wo man weiss, das sie kaum in Hash-Collections verwendet werden können) genügt dann auch "return toString().hashCode()", sofern man in der "toString()"-Methode alle in "equals()" verwendeten Werte einschliesst._

Ich halte das für sehr unschön und gewfährlich. Unschön, weil "toString" i.a. SEHR teuer ist (sowas wie 
return String.valueOf(someFloat).hashCode();
ist VIEL aufwändiger als
return Float.floatToIntBits(someFloat);
wodurch ein Großteil des Vorteils, den Hash-Datenstrukturen bieten, wieder aufgefressen wird)

Und gefährlich, weil jede Unterklasse von Vertex "toString" passend überschreiben wird, und dann kommt Mist raus. Es scheint ja schon schwierig zu sein, den Contract zwischen equals und hashCode einzuhalten - jetzt noch einen (viel schwieriger zu formalisierenden, und kaum einzuhaltenden) Contract zwischen equals, hashCode und toString einzuführen, wäre nicht zielführend....


----------



## Spacerat (30. Mrz 2009)

Wird hier eigentlich nur in Quadraten gedacht? Es gibt Kreise... Dreiecke... Polygone... 
"return toString().hashCode()" steht hier für "return soSimpelWieMöglichAberKonform".
Ok.: die Begründug für "gefählich" lass ich mir sogar gefallen. Hab' ich ein glück, das mein Vertex "final" ist.


----------



## 0x7F800000 (30. Mrz 2009)

Spacerat hat gesagt.:


> "return soSimpelWieMöglichAberKonform"


return 0; //ist konform
throw UnsupportedOperationException(); //räumt sofort alle missverständnisse aus.

Statt hier mit der Durchreichung von irgendwelchen Arrays zu optimieren, könntest du imho nochmal versuchen nach dem Prinzip "keep it simple & stupid", dann aber die berechnungen auf 2 Cores aufteilen, damit der zweite prozessor nicht rumgammelt...


----------



## Ebenius (30. Mrz 2009)

0x7F800000 hat gesagt.:


> throw UnsupportedOperationException(); //räumt sofort alle missverständnisse aus.


Reden wir hier immer noch von hashCode()? :autsch:

Ebenius


----------



## 0x7F800000 (30. Mrz 2009)

Ebenius hat gesagt.:


> Reden wir hier immer noch von hashCode()? :autsch:


Naja, was soll man da eigentlich machen?
[highlight=Java]
import java.util.*;

public class _ {
    private static class X{
        private int x;
        public X(int _){
            x=_;
        }
        public void setX(int _){
            x=_;
        }
        @Override
        public boolean equals(Object other){
            if(other instanceof X){
                X y=(X)other;
                return y.x==this.x;
            }
            return false;
        }
        @Override
        public int hashCode(){
            return x;
        }
        @Override
        public String toString(){
            return ""+x;
        }
    }
    public static void main(String... _) {

        HashSet<X> set=new HashSet<X>();
        X a=new X(1);
        X b=new X(2);
        set.add(a);
        a.setX(2);
        set.add(b);
        System.out.println(set); // [2, 2] toller set, alles im A****  
    }
}
[/highlight]
Was soll man tun, wenn die hash-funktion von werten abhängt, die dauernd verändert werden sollen? Ist es da nicht besser den Benutzer der klasse mit einer exception darauf hinzuweisen, dass diese Objekte für Hash-Strukturen einfach nicht gedacht sind? Für (im wesentlichen) immutable objekte ist alles klar, und was macht man eigentlich mit den veränderlichen? :bahnhof: Ich würde eigentlich normal hashCode implementieren, und dann diejenigen elemente, die verändert werden müssen, aus dem set rausholen, verändern, wieder hashen und einfügen.


----------



## Ebenius (30. Mrz 2009)

UnsupportedOperationException sollte man nur benutzen, wenn Methoden einer API als optional gelten, die spezielle Implementierung diese optionale Methode aber nicht unterstützt. In einer hashCode()-Methode eine Exception zu werfen halte ich im allgemeinen für ein Verbrechen. 

Date.hashCode() macht es doch richtig vor; das Objekt gibt einen hashCode des derzeitigen Status wieder. Wenn der sich ändert, ist der hashCode ebenfalls anders. Kein Problem. Achtung: Ich vergesse gern, dass java.util.Date nicht immutable ist; falls es noch jemandem so geht...

Das Objekt selbst sollte sich doch nicht dafür interessieren müssen, dass es niemand falsch verwendet. Ein sich änderndes Objekt hat nichts in einer HashMap / einem HashSet zu suchen während es sich verändert. Dafür ist der Nutzer der Klassen zuständig, nicht das Objekt. Genauso müsste beispielsweise der Comparator der die Objekte irgendwie vergleichen kann auch UnsupportedOperationException schmeißen, weil ja irgendwer auf die Idee kommen könnte, die Objekte in einem TreeSet abzulegen. :autsch:

Ebenius


----------



## SchonWiederFred (30. Mrz 2009)

0x7F800000 hat gesagt.:


> Was soll man tun, wenn die hash-funktion von werten abhängt, die dauernd verändert werden sollen?


Dann muss der Benutzer verantwortungsbewusst mit der Klasse umgehen 

Idealerweise verwendet man nur unveränderliche Objekte in HashSets bzw. als Keys in HashMaps. Wenn man von dieser Regel abweicht, muss man halt selber aufpassen.


----------



## Stefan S. (3. Apr 2009)

0x7F800000 hat gesagt.:


> Gestern habe ich wieder angefangen mit kontextfreien Grammatiken rumzubasteln (disesmal in Java).
> Da kommt durchschnittlich in jeder 10 Zeile irgendein "HashXyz" vor, das gesammte ding arbeitet bisher praktisch ausschließlich mit den Strukturen HashMap<T,HashSet<T>> (die eben eine Funktion darstellen, die Symbolen Mengen von anderen Symbolen zuordnen, sowas wie FIRST-sets oder so). Nur so als Beispiel... :bahnhof:



Du bastelst in deiner Freizeit freiwillig an CFG/Parsern? Sauber, man hat ja sonst nichts zu tun. :toll:


----------



## Marco13 (4. Apr 2009)

Jaja, Student müßte man wieder sein :reflect:


----------

