[Java/ALG] Belang van correcte hash en equal method *

[Macros]

Verder zou ik nooit je hashCode 0 laten returnen. Dan werken je HashMap/Set niet meer in O(1), maar in O(N), en dat wilde we nu juist voorkomen.

---

Dit topic is een afsplitsing van [rml][ Java] Alternatief voor Vector of array[/rml]


Zie ook [rml]gorgi_19 in "[ Java/ALG] Belang van correcte hash en e..."[/rml]

[ Voor 52% gewijzigd door Janoz op 14-06-2004 08:21 ]

[Soultaker]

0 is beter dan helemaal geen implementatie, want dan returned 'ie een code gebaseerd op de object reference en dan werken HashMap/HashSet's helemaal niet meer. Liever een inefficiente werking dan een incorrecte werking.

[Robtimus]

Soultaker schreef op 12 juni 2004 @ 16:24:
0 is beter dan helemaal geen implementatie, want dan returned 'ie een code gebaseerd op de object reference en dan werken HashMap/HashSet's helemaal niet meer. Liever een inefficiente werking dan een incorrecte werking.

De HashMap/Set werkt dan wel, zolang je de standaard equals niet overschrijft.
Dus: o1.equals(o2) === o1 == o2

[Verwijderd]

De HashMap/Set werkt dan wel maar niet meer zoals 'tie zou moeten werken. Een hele simpele oplossing die ik altijd (nou ja vaak dan) gebruik is een unieke toString() methode schrijven en voor de hashCode methode gewoon de toString().hashCode() returnen. Ben je altijd uniek en blijven HashMap/Sets ook gewoon zo optimaal mogelijk werken.

[Macros]

Kan je meteen je equals op dezelfde manier laten werken, door de toStrings() te vergelijken.

[Alarmnummer]

Macros schreef op 13 juni 2004 @ 11:55:
Kan je meteen je equals op dezelfde manier laten werken, door de toStrings() te vergelijken.

Dan moet je wel 100% zeker weten dat je een unieke string hebt

[Verwijderd]

Appfuse gebruikt commons lang om hashcode, equals en toString te genereren.

http://jakarta.apache.org...lder/ToStringBuilder.html

This will produce a toString of the format: Person@7f54[name=Stephen,age=29,smoker=false]

die 7f54 zal wel een geheugenlocatie zijn zodat je == toepast. Als je dat niet wil kies je een ander type ToStringStyle

[Macros]

Leuk zo'n toStringBuilder, maar je kan ze beter zelf schrijven. Het schrijven kost bijna geen tijd, en het is een stuk sneller. Vooral die reflectie variant zal wel zo traag als dikke stroop zijn.

[Robtimus]

Verwijderd schreef op 13 juni 2004 @ 11:13:
De HashMap/Set werkt dan wel maar niet meer zoals 'tie zou moeten werken.

De HashMap/Set werkt zolang o1.equals(o2) => o1.hashCode() == o2.hashCode().

Als je de hashCode() niet overschrijft, geldt dus o1 != 02 => o1.hashCode() != o2.hashCode(). Om ervoor te zorgen dat de HashMap/Set dan werkt, moet equals dus hetzelfde werken:

Java:

public boolean equals(Object o) { return this == o; }

Dat is dus precies de implementatie die Object gebruikt.

[Macros]

Dan hoeft het nog niet te werken. Stel je hebt een eigen Integer implementatie met die equals. Dan werkt het niet, want als je 2 instanties van het getal 4 maakt, zullen ze verschillend zijn volgens die definitie.

[Robtimus]

Het zijn objecten, dus de hashcode is meestal gebaseerd op de plek in het geheugen:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Ze zijn hoe dan ook altijd uniek.

o1.equals(o2) === o1 == o2. Dus als o1.equals(o2), dan o1 == o2 (zelfde object), dan o1.hashCode() == o2.hashCode().

Het werkt dus WEL.

[Macros]

Toch is het niet de bedoeling Objecten zijn hetzelfde als ze logisch identiek zijn, niet als ze op hetzelfde geheugen plek bevinden

[Robtimus]

In hoeverre 2 objecten gelijk zijn is aan de programmeur, als gebruiker van de code heb je je daaraan te houden. Soms heeft het zin om de equals zo strict mogelijk te houden (al zie ik idd niet in wanneer het ZO strict moet zijn, maar ok).

[zneek]

NOFI, maar ik denk dat TS helemaal niets heeft aan deze discussie over hashcodes en string functies. Zijn vraag ging over dynamische arrays, en hoe in Java zijn meetgegevens in een hanteerbare structuur bij te houden.

Misschien is het een idee om een topic af te splitsen waar verder gediscussieerd kan worden over hoe belangrijk een correcte hash en equal methode is? En hoe de werking daarvan zou moeten zijn.

[Soultaker]

Naar mijn idee zijn de default implementaties gewoon fout. Object.equals() zou altijd true moeten retourneren (want 'lege' objecten verschillen in niets) en de Object.hashCode() zou altijd dezelfde constanten moeten retourneren (in overeenstemming met equals).

Op deze manier kun je ook in je eigen klasse veilig equals() overriden zonder per se hashCode() ook te moeten overriden. Nog belangrijker is echter dat je dan je equals() als volgt kan implementeren:

Java:

class Foo
{
    public int attribute;

    public bool equals(Object other) {
         return (other instanceof Foo) && (attribute == ((Foo)other).attribute)
            && (super.equals(other));
    }
}

Dit idioom is erg handig omdat je op deze manier in een afgeleide klasse alleen maar de attibuten die jouw klasse toevoegt hoeft te controleren en de rest van de gelijkheid laat je afhandelen door de superklasse.

Met de huidige foutieve implementatie van Object.equals() kun je dit idioom niet toepassen als je (impliciete) superklasse Object is; nogal inconsequent. Als Object.equals() altijd true zou opleveren, zoals ik voorstel, dan zou het wél goed gaan.

[ Voor 11% gewijzigd door Soultaker op 13-06-2004 17:38 ]

[gorgi_19]

En een kleine afsplitsing gemaakt van [rml][ Java] Alternatief voor Vector of array[/rml]

[ Voor 11% gewijzigd door gorgi_19 op 13-06-2004 21:37 ]

[Macros]

De default implementatie van Object zou eigenlijk reflectief moeten zijn en dan gebruik moeten maken van de attributen om te bepalen of een object gelijk is.
De hashcode zou op eenzelfde manier kunnen gaan, door de hashcodes van de attributen bij elkaar te nemen.

[Soultaker]

Dat is wel een erg kostbare default implementatie als je 'm toepast op cyclische datastructuren of op objecten die remote geimplementeerd zijn. Het lost de problemen nog steeds niet op, omdat objecten verschillende attributen kunnen hebben maar toch conceptueel gelijk kunnen zijn (denk bijvoorbeeld aan breuken als 1/2 en 2/4). Bovendien heb je dan weer de ellende dat je niet domweg de equals methode van de superklassa kan aanroepen in je equals methode.

De suggestie van een reflexieve equals is wel leuk, maar ik vind dat het geen attribuut van Object hoort te zijn. Het is meer wat voor een static method die twee willekeurige objecten met elkaar kan vergelijken.

[ Voor 74% gewijzigd door Soultaker op 13-06-2004 19:01 ]

[Macros]

Daar heb je wel gelijk in.
Hoe zit het in C# eigenlijk? Zelfde als Java?

[ACM]

Soultaker schreef op 13 juni 2004 @ 17:36:
Naar mijn idee zijn de default implementaties gewoon fout. Object.equals() zou altijd true moeten retourneren (want 'lege' objecten verschillen in niets) en de Object.hashCode() zou altijd dezelfde constanten moeten retourneren (in overeenstemming met equals).

't Probleem met jouw voorstel is dat het als default implementatie voor elke afgeleide van Object nogal gevaarlijk is.
Imho moet je bij een defaultimplementatie voor de meest veilige of correcte variant kiezen, niet voor degene die de mooiste code oplevert.

En het is, imho, niet veilig om maar gewoon altijd true terug te geven. En het is niet helemaal correct om altijd false terug te geven. Een variant als a == b is een van de weinige waarvan je hard kan maken dat ie klopt (mits je definitie van gelijkheid dat toelaat) en aangezien je bij een Object niks anders kan testen dan of de referentie hetzelfde is, is dat de enige test die overblijft.

Overigens ben ik niet met je eens dat objectA altijd gelijk aan objectB is als ze beiden geen inhoud hebben. Want dat impliceert dat objecten van onderstaande klassen ook altijd gelijk zijn, of niet?

Java:

class typeB implements SomeInterface
{
}

class typeC implements SomeOtherInterface
{
}

[ Voor 2% gewijzigd door ACM op 13-06-2004 20:29 . Reden: Op verzoek van Macros code-tags ;) ]

[Soultaker]

Ik denk dat je pas op een zinnige wijze op gelijkheid kan testen als je gelijkheid voor je klasse hebt gedefinieerd. Je kunt niet zomaar de implementatie van Object erven en dan verwachten dat je een zinnige implementatie heb; net als met elke superklasse weet je dan alleen of het deel van de objecten dat bij die superklasse hoort gelijk is. Ik vind dan ook niet dat Object.equals() ontworpen moet worden zodat afgeleide klassen 'm zouden kunnen overerven; dat is niet haalbaar en in deze vorm zorgt bovendien voor het tegenovergestelde, namelijk dat de methode niet bruikbaar is voor subklassen van Object.

En het is, imho, niet veilig om maar gewoon altijd true terug te geven.

Waarom precies niet? Ik vind het conceptueel wel veilig. Waarin verschillen twee instanties van Object nu inhoudelijk? Verschil in identiteit kun je altijd wel testen door references te vergelijken, de equals()-methode moet juist structureel verschil testen.

En het is niet helemaal correct om altijd false terug te geven.

Dat ben ik sowieso met je eens, want a.equals(a) moet natuurlijk true opleveren.

Overigens ben ik niet met je eens dat objectA altijd gelijk aan objectB is als ze beiden geen inhoud hebben. Want dat impliceert dat objecten van onderstaande klassen ook altijd gelijk zijn, of niet?

Java:

class typeB implements SomeInterface
{
}

class typeC implements SomeOtherInterface
{
}

Dat is eigenlijk hetzelfde punt als het eerste. Ik vind dat equals voor deze klassen weer als volgt moet worden geïmplementeerd:

Java:

public bool equals(Object other)
{
    return (other instanceof Type) && (super.equals(other));
    // let op: dit gaat er van uit dat super.equals(other) true op zou leveren!
}

Dit is een specifiek geval van het idioom dat ik al eerder noemde (alleen voegen de klassen helemaal geen eigen state toe dus hoeft die ook niet vergeleken te worden). Naar mijn mening moet Object dit idioom ook volgen. Omdat elk object instantie is van Object valt de eerste controle weg, en omdat er geen superklasse voor Object is de tweede, en effectief blijft er dan een 'return true' over.

Als beide door jouw genoemde klassen op deze manier hun equals-methode implementeren dan verschillen ze omdat ze verschillen van type (ook al verschillen ze niet van structuur). Dat onderschrijft alleen maar mijn stelling dat elke klasse een zinnige equals()-methode moet implementeren en dat Object.equals() op dat gebruik toegespitst zou moeten zijn.

Het mooie is dat ik jouw voorbeeld net zo goed tegen jouw stelling kan gebruiken: twee instanties van TypeB zijn volgens Object.equals() verschillend, terwijl ze inhoudelijk toch echt hetzelfde zijn bij gebrek aan state! Dat klopt toch ook niet? De enige conclusie die ik hieruit kan trekken is: Object.equals() kan niet direct geerfd worden door subklassen.

[ Voor 10% gewijzigd door Soultaker op 13-06-2004 21:05 ]

[Macros]

Zou equals niet gewoon abstract moeten zijn in Object? Of protected net als clone()?

[Soultaker]

Oh trouwens, Java is toch al krom waar het equality testing bepaalt. Zelfs als je een instantie van een klasse (anders dan Object) en van een subklasse daarvan hebt, dan kan het goed voorkomen dat a.equals(b) != b.equals(a), wat natuurlijk erg raar is aangezien je verwacht dat 'gelijkheid' een symmetrische relatie is.

[Soultaker]

Macros schreef op 13 juni 2004 @ 21:07:
Zou equals niet gewoon abstract moeten zijn in Object? Of protected net als clone()?

Abstract is wel erg jammer, want dan ben je verplicht 'm te implementeren in subklassen voordat je ze kunt instantiëren. Bovendien kun je dan geen dummy Object'en instantiëren, wat vaak handig is als je een extra monitor wilt hebben (en dan kan de equals methode je geen ruk schelen).

Een interface Comparable lijkt me al een stuk beter (die bestaat nu ook al, maar doet nog iets meer). Je kunt dan gewoon kiezen of je de methode wel of niet implementeert en als je 'm niet implementeert dan geeft de compiler een nette foutmelding als je 'm toch wilt gebruiken. Nu wordt de equals()-methode in Containers en dergelijke gebruikt, ongeacht of er wel of niet een zinnige implementatie beschikbaar is (en daar krijg je dus geen enkele waarschuwing voor). Dat vind ik een slechte zaak.

[Macros]

Eigenlijk is het dus een open probleem

[ACM]

Soultaker schreef op 13 juni 2004 @ 21:01:
Ik vind dan ook niet dat Object.equals() ontworpen moet worden zodat afgeleide klassen 'm zouden kunnen overerven; dat is niet haalbaar en in deze vorm zorgt bovendien voor het tegenovergestelde, namelijk dat de methode niet bruikbaar is voor subklassen van Object.

Dat ben ik deels met je eens. Maar anderzijds ben ik wel van mening dat het geen "kwaad" moet kunnen als je niet de moeite neemt een specifieke methode over te erven.

Waarom precies niet? Ik vind het conceptueel wel veilig. Waarin verschillen twee instanties van Object nu inhoudelijk? Verschil in identiteit kun je altijd wel testen door references te vergelijken, de equals()-methode moet juist structureel verschil testen.

Op zich ben ik het met je eens, wbt de functionaliteit van equals. Maar als je Objecten gebruikt als "keys" voor iets, waar dus dmv equals getest wordt op gelijkheid, kan je met een equals die altijd true teruggeeft nooit onderscheid tussen verschillende key/value-paren maken.
En ik weet dat Objecten niet het allerhandigst als key zijn, maar zeker niet onwerkbaar ofzo. 't Gaat meer om het punt dat altijd maar true teruggeven bijna net zo fout is als altijd false.
Er kan verschil zijn tussen twee verschillende objecten (afhankelijk van je definitie van gelijkheid), maar met jouw equals-aanpak is dat alleen te testen door de == relatie, die weer niet overal toegepast wordt.

Dit is een specifiek geval van het idioom dat ik al eerder noemde (alleen voegen de klassen helemaal geen eigen state toe dus hoeft die ook niet vergeleken te worden). Naar mijn mening moet Object dit idioom ook volgen. Omdat elk object instantie is van Object valt de eerste controle weg, en omdat er geen superklasse voor Object is de tweede, en effectief blijft er dan een 'return true' over.

Ik ben van mening dat je voor elk type apart moet of kunt bepalen hoe de gelijkheid voor dat type in elkaar steekt.
En de keuze bij Object is ofwel "beide zijn leeg, dus beide zijn gelijk" (maar waarom is de ene leegheid hetzelfde als de andere?) en de keus voor de fysieke locatie.
Trouwens, jouw methode is niet transitief:

Java:

class TypeA
{
   int paramA;
   boolean equals(Object o)
   {
       return (o instanceof TypeA) 
          && this.paramA == o.paramA && super.equals(); // jouw equals
   }
}

Object x = new Object();
TypeA y = new TypeA();

y.equals(x); // false
x.equals(y); // true

Wat wellicht nog een beter argument is om niet zomaar, ongeacht de input, maar true terug te geven. De standaard Object-aanpak levert, zelfs met een geherdefinieerde equals, wel netjes in beide gevallen false op.

Het mooie is dat ik jouw voorbeeld net zo goed tegen jouw stelling kan gebruiken: twee instanties van TypeB zijn volgens Object.equals() verschillend, terwijl ze inhoudelijk toch echt hetzelfde zijn bij gebrek aan state! Dat klopt toch ook niet? De enige conclusie die ik hieruit kan trekken is: Object.equals() kan niet direct geerfd worden door subklassen.

Dat is niet waar, dat hangt van je definitie af
Je conclusie ben ik het met een genuanceerde versie eens. Je moet niet zomaar de Object.equals gebruiken.

Zeker met "enumeration"-klassen, is het nuttig om gewoon de Object.equals te gebruiken, zonder moeite te doen om een eigen implementatie te geven.

Java:

public class TreeNavigationType
{
    public static final TreeNavigationType DEEP = new TreeNavigationType();
    public static final TreeNavigationType TOP = new TreeNavigationType();

    private TreeNavigationType()
    {}
}

Die DEEP en TOP zijn wel degelijk verschillend, ondanks dat ze geen inhoud hebben. In jouw definitie van gelijkheid zouden ze echter gelijk zijn?
Of met jouw opzet zou je me dwingen voor dit soort vlutklassen steeds maar weer een equals methode te maken, die precies doet wat de huidige Object-equals al doet

[ Voor 7% gewijzigd door ACM op 13-06-2004 23:11 ]

[Verwijderd]

Macros schreef op 13 juni 2004 @ 15:19:
Leuk zo'n toStringBuilder, maar je kan ze beter zelf schrijven. Het schrijven kost bijna geen tijd, en het is een stuk sneller. Vooral die reflectie variant zal wel zo traag als dikke stroop zijn.

dat is inderdaad niet zo snel (de snelheid van reflection verbeterd wel, maar nog niets zo goed als zelfgeklopte code inderdaad).
Maar ik bedoelde dat dat de default implementatie is. Er zijn in IDEA (eclipse weet ik niet) plugins die een toString builden adhv reflection, volgens mij moet het ook mogelijk zijn om adhv reflection een equals te builden en daar de code van te genereren. Dus heb je het beste van twee werelden.
Een correcte (maar ûbertrage) default implementatie die je omwile van performance maar moet overschrijven. En een editor die je daarbij helpt.

[Robtimus]

ACM schreef op 13 juni 2004 @ 23:05:
Ik ben van mening dat je voor elk type apart moet of kunt bepalen hoe de gelijkheid voor dat type in elkaar steekt.
En de keuze bij Object is ofwel "beide zijn leeg, dus beide zijn gelijk" (maar waarom is de ene leegheid hetzelfde als de andere?) en de keus voor de fysieke locatie.
Trouwens, jouw methode is niet transitief commutatief / symmetrisch:

Java:

class TypeA
{
   int paramA;
   boolean equals(Object o)
   {
       return (o instanceof TypeA) 
          && this.paramA == o.paramA && super.equals(); // jouw equals
   }
}

Object x = new Object();
TypeA y = new TypeA();

y.equals(x); // false
x.equals(y); // true

Wat wellicht nog een beter argument is om niet zomaar, ongeacht de input, maar true terug te geven. De standaard Object-aanpak levert, zelfs met een geherdefinieerde equals, wel netjes in beide gevallen false op.

Transitief is:
x.equals(y) && y.equals(z) => x.equals(z)

Ook geldt dat x.equals(y) == false, want x != y

Verder uit Object.equals:

The equals method implements an equivalence relation on non-null object references:

• It is reflexive: for any non-null reference value x, x.equals(x) should return true.
• It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
• It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
• It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
• For any non-null reference value x, x.equals(null) should return false.

Als je dus een equals schrijft moet je dus rekening houden dat je superklassen ook goed vergelijkt (@SoulTaker). Dit kan idd wat logische problemen geven, als je opeens voor gelijkheid atributen moet negeren als het object waarmee je vergelijkt een instantie van de superclass is. Dat is echter wel de enige correct manier volgens de specificatie.

[ACM]

IceManX schreef op 14 juni 2004 @ 10:02:
Transitief is:
x.equals(y) && y.equals(z) => x.equals(z)

Klopt, ik bedoelde symetrisch

Ook geldt dat x.equals(y) == false, want x != y

Niet met Soultaker's voorstel van een default equals.

Verder uit Object.equals:

Precies.
De reflexie is fout bij altijd false voor Object (x.equals(x) = false)
De symetrie is fout bij altijd true voor Object (vs andere equals-methoden) (x.equals(y) = false, y.equals(x) = true in mijn voorbeeld)

[Alarmnummer]

Op javaworld staat toevallig net een artikel erover:
http://www.javaworld.com/...-2004/jw-0614-equals.html

[Robtimus]

Conclusie daarvan: gebruik ipv instanceof een check of getClass gelijk is (this.getClass() == o.getClass()); zo zijn instanties van een subclass nooit gelijk aan instanties van de baseclass.

FF wat stukjes van mijn code herschrijven

[Soultaker]

ACM schreef op 13 juni 2004 @ 23:05:
Die DEEP en TOP zijn wel degelijk verschillend, ondanks dat ze geen inhoud hebben. In jouw definitie van gelijkheid zouden ze echter gelijk zijn?
Of met jouw opzet zou je me dwingen voor dit soort vlutklassen steeds maar weer een equals methode te maken, die precies doet wat de huidige Object-equals al doet

Dat is inderdaad een lastig praktisch punt. Overigens gebruikt de Java API voor enumerations zelf integers en geen Objects. Het probleem treedt dus alleen op als je per se af wil wijken van de gangbare praktijk.

Wat betreft de symmetrie van equality testing: ik vind dat die alleen hoeft te gelden voor de gemeenschappelijke basis van objecten. Met andere woorden, ik zou symmetrie willen definiëren als: a.T::equals(b) == b.T::equals(a) (met T willkeurig).

[Macros]

Java 1.5 introduceerd een nieuw type Collections, de enums. Hoe die werken weet ik nog niet. Nog niet in verdiept, zal wel lastig zijn

[ACM]

Soultaker schreef op 14 juni 2004 @ 19:58:
Dat is inderdaad een lastig praktisch punt. Overigens gebruikt de Java API voor enumerations zelf integers en geen Objects. Het probleem treedt dus alleen op als je per se af wil wijken van de gangbare praktijk.

't Voordeel van deze aanpak is dat je methoden kan dwingen slechts met enkele opties te werken, namelijk alleen de beschikbare enumeration-elementen. Bij een integer wordt dat niet afgedwongen, daar kan je in principe prima -1 meegeven als de mogelijke waarden officieel alleen 0, 1, 2, 3, 4 en 5 zijn
De compiler klaagt er niet over.

Nadeel is natuurlijk dat het niet zo handig in een switch/case toe te passen is.