[Java] HashSet gebruikt niet equals() van mijn class

[Verwijderd]

Ik heb een eigen classe gemaakt Users.
Het enige wat deze class heeft zijn wat setters en getters en een toString() functie en een equals() functie. Nou wil ik deze class graag gebruiken in een HashSet. Zodat deze kan bebalen welke users dubbel zijn etc. Alles goed en aardig maar het lijkt erop dat HashSet niet mijn equals() gebruikt om twee User classes te vergelijken. Zie de volgende code:

Java:

User user1 = new User("rik", "Geen Naam", "101010101", true);
User user2 = new User("rik", "Geen Naam", "101010101", true);
log.debug( ""+user1.equals(user2) );
usersDB.add(user1);
usersDB.add(user1);
usersDB.add(user2);
log.debug(usersDB);

Ik verwacht dus dat er maar 1 User object in de HashSet komt te staan maar de uitvoer is als volgt:

code:

DEBUG - true
DEBUG - [Geen Naam (rik) , 101010101 , true, Geen Naam (rik) , 101010101 , true]

Object user1 en user1 vind hij wel het zelfde maar user1 en user2 zijn niet het zelfde. Terwijl zoals je in de uitvoer kan zien user1.equals(user2) wel TRUE geeft.

Wat kan ik hier nou aan doen!?!? Trouwens met String objecten werkt het wel naar behoren!

Zie hier nog de equals methode in User:

Java:

public boolean equals( Object obj ) {
  if(this==obj)
    return true;
        
  // Username is primary key.
  User u = (User) obj;
  return( this.userName.equals(u.getUserName()) );
}

[Nvidiot]

Moet je niet een interface implementeren in je User class? Iets als IComparable ofzo?

[whoami]

Je hebt ook de nodige interface geimplementeerd ?
Ik doe wel geen Java, maar ik kan me wel voorstellen dat je ook een Comparable interface oid moet implementeren...

[Varienaja]

public boolean add(Object o)

Adds the specified element to this set if it is not already present.

Jouw object user1 is een ander object dan user2. Ookal geeft geldt dat user1.equals(user2) het zijn 2 losse objecten, en je kunt ze dan ook allebei in een HashSet stoppen.

edit:
Het IComparable-verhaal klinkt erg goed.

[ Voor 9% gewijzigd door Varienaja op 19-01-2006 16:05 ]

[NetForce1]

Normaal gesproken hoef je om items in een collectie te frotten geen interface te implementeren hoor. Misschien helpt het als je hashCode override.

[Verwijderd]

Het helpt inderdaad heel goed als je hashCode override (kijk overigens even in javadoc van Object naar het overriden van equal en hashCode)

Java:

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }

Dit fragment komt uit HashMap die van je object een unieke key ophaalt...

[Verwijderd]

(Voor het geval de TS dit nog niet wist... ) Het is triviaal dat de hash-functie eenzelfde hash moet retourneren als de objecten (volgens de equals methode) hetzelfde zijn.

[Verwijderd]

Verwijderd schreef op donderdag 19 januari 2006 @ 16:12:
(Voor het geval de TS dit nog niet wist... ) Het is triviaal dat de hash-functie eenzelfde hash moet retourneren als de objecten (volgens de equals methode) hetzelfde zijn.

Toch vind ik deze implementatie van HashMap overigens vreemd aangezien een gelijke hashCode er niet op duidt dat de equals methode gelijk moet zijn. Terwijl de specificatie van een Set juist weer duidelijk voorschrijft dat hiervoor equals gelijk moet zijn.

[SPee]

De hashset gebruikt de hashcode van het object. In de javadoc staat bij Object:

code:

int hashCode()

Deze moet re hashcode teruggeven van het object. Als je deze niet gebruikt in je classe, dan pakt de hashset een automatische code, welke niet uniek is voor dezelfde object.

Dus de hashset gebruikt niet de .equals(Object o) funtie, maar de .hashCode() functie. Als je deze implementeerd, krijg je de juiste werking.

[Robtimus]

Verwijderd schreef op donderdag 19 januari 2006 @ 16:16:
Toch vind ik deze implementatie van HashMap overigens vreemd aangezien een gelijke hashCode er niet op duidt dat de equals methode gelijk moet zijn. Terwijl de specificatie van een Set juist weer duidelijk voorschrijft dat hiervoor equals gelijk moet zijn.

HashSet is geimplementeerd met een backing HashMap.
Een HashMap bestaat uit meerdere buckets, elke bucket bevat elementen met dezelfde hash code. Als je gaat zoeken wordt eerst hashCode gebruikt om de goede bucket te vinden, daarna wordt mbv equals in die bucket het juiste object gevonden. Voor HashSet geldt dus hetzelfde. hashCode en equals worden dus allebei gebruikt, en a.equals(b) moet inhouden dat a.hashCode() == b.hashCode(). Niks mis mee dus.

TreeSet / TreeMap daarentegen breekt het contract van de Set interface omdat die compareTo van de Comparable objecten of compare van de Comparator gebruikt.

[Verwijderd]

@IceManX
Ah ik had dus wel iets verder moeten lezen in de code... nadeel van "even snel kijken"

[Verwijderd]

Maar ik wil er juist helemaal niet voor zorgen dat het de zelfde objecten zijn. Dus ik wil juist dat hij enkel equals gebruikt om te vergelijken. Dit is toch ook zoomschreven in Set ??

En dan nog iets, hoe kan het dan dat het bij Strings wel werkt?
Dus zelfde code maar dan:

Java:

String user1 = new String("rik");
String user2 = new String("rik");

Mijn inziens word hier ookalleen maar equals() gebruikt dan. Want de hashcodes zijn verschilllend neem ik aan?

[NetForce1]

Als je de javadoc van equals bekijkt dan lees je daar het volgende:

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

De hashcodes van twee dezelfde strings zijn ook hetzelfde, bekijk de javadoc van String.hashCode maar eens:
[quote]

Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, 
and ^ indicates exponentiation. (The hash value of the empty string is zero.)
[/]

[Verwijderd]

Het gaat mij namelijk het meest om zometeen de methode removeAll( Collection c ) te gebruiken zodat ik het verschil tussen twee HashSet kan afvangen.
Moet ik dus in mijn class User de methode hashCode() overriden?
Hoe moet ik die dan implementeren zodat removeAll() gaat werken?

[Verwijderd]

Verwijderd schreef op donderdag 19 januari 2006 @ 17:39:
Het gaat mij namelijk het meest om zometeen de methode removeAll( Collection c ) te gebruiken zodat ik het verschil tussen twee HashSet kan afvangen.
Moet ik dus in mijn class User de methode hashCode() overriden?
Hoe moet ik die dan implementeren zodat removeAll() gaat werken?

Wat dacht je ervan dat als je equals enkel baseert op 1 enkele String dan ook de hashCode van die string te laten retouneren _{maal 29}.

[Soultaker]

Verwijderd schreef op donderdag 19 januari 2006 @ 17:39:
Het gaat mij namelijk het meest om zometeen de methode removeAll( Collection c ) te gebruiken zodat ik het verschil tussen twee HashSet kan afvangen.
Moet ik dus in mijn class User de methode hashCode() overriden?
Hoe moet ik die dan implementeren zodat removeAll() gaat werken?

Het is voor de werking van hash tables van belang dat de volgende relatie geldt:
• als a.equals(b) dan a.hashCode() == b.hashCode()
Omgekeerd hoeft het niet te gelden (als de hashcodes gelijk zijn, mogen de objecten nog verschillen).

De default-implementatie van hashCode() retourneert voor elk uniek object een andere code en dat klopt dus niet met bovenstaande eis. Eigenlijk is dat een beetje een gebrek in de implementatie van Object (hoewel het consistent is met Object.equals()); een betere default-implementatie zou er een zijn die altijd een constante waarde retourneert (of de hashCode() van de class ofzoiets).

De beste en makkelijkste manier om de hashcode te definiëren is in termen van hashcodes van de attributen die de toestand van een object definiëren; dat zijn dus dezelfde attributen waarmee je vergelijkt in equals. Een voorbeeld:

Java:

public class Foo {
    private String name;
    private Image img;

    public boolean equals(Object o) {
        if(!o instanceof Foo)
            return false;
        Foo f = (Foo)f;
        return name.equals(f.name) && img.equals(f.img);
    }
    
    public int hashCode() {
        return name.hashCode() ^ img.hashCode();
    }
};

Overigens kun je ook 'minder' velden bij je hashcode betrekken (alleen name.hashCode() retourneren bijvoorbeeld); het retourneren van een constante (bv. 0) is daar een extreem voorbeeld van. Dat gaat wel tenkoste van de performance van de hash table natuurlijk.

[ Voor 3% gewijzigd door Soultaker op 19-01-2006 19:52 ]

[Robtimus]

Let trouwens op 1 ding heel goed: de huidige implementaties van HashSet/HashMap en TreeSet/TreeMap werken alleen maar als de keys (voor sets de objecten) niet veranderen wat betreft de velden die gebruikt worden voor hashcode cq. compareTo. De verdeling van buckets cq. de verdeling in de tree wordt nml maar eenmaal gedaan per object. Als jij dus een veld verandert dat gebruikt wordt in de hash code kan de hash code veranderen, maar het object zit nog wel in de bucket voor zijn oude hash code. Je zult het object dan ook waarschijnlijk niet meer terugvinden. Daarom zijn strings ook perfecte keys in maps, die veranderen nooit.

[Verwijderd]

Bedankt voor jullie reactie, het is nu helemaal duidelijk! Ik kan weer verder.

Ik vond het vreemd omdat in het boek Datastructuren in Java door Gertjan Laan werd gezegd dat voor HashSet.removeAll() ik enkel equals hoefde overteschrijven. Toen dit dus niet werkt keek ik in de Javadocs van Set en daar staat het volgende onder remove() (wat gebruikt wordt door removeAll en wat ik enkel nodig had):

Removes the specified element from this set if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if the set contains such an element. Returns true if the set contained the specified element (or equivalently, if the set changed as a result of the call). (The set will not contain the specified element once the call returns.)

Toen ik dit las dacht ik dat er enkel naar equals() werd gekeken ter vergelijking.
Maar het is mij nu duidelijk, erg bedankt nogmaals en goeie opmerking ook IceManX: dank.

[Robtimus]

Alleen als je equals overschijft moet je volgens het contract van Object ook meteen hashCode overschrijven. Daar gaat veel code die equals gebruikt ook vanuit.

Maar nogmaals, TreeSet en TreeMap zijn eigenlijk foute implementaties omdat ze het contract van Set / Map (er wordt equals gebruikt voor equality) verbreken: ze gebruiken compareTo / compare.