Java - HashMap and HashSet not backed by Object.hashCode()?

Question

I'm trying to write a server, which tracks its clients by a uniquely-generated ID using a HashMap<ClientID,Client>. The idea is, if I'm an admin and I want to boot somebody off the server, I look up the appropriate ClientID (which is really just a String; only difference is the ClientID class does the work of ensuring that no two clients are ever assigned the same ID) for that client and then enter a command such as "kick 12" (if the ClientID of the person I wanted to kick happened to be 12). I assumed this would work because I figured that a HashMap was probably backed by internal use of the hashCode() method inherited from Object, and I designed the ClientID class in a way that would support the necessary lookup operations, assuming that's true. But apparently, it's not true - two keys with the same hashcodes are evidently not considered to be the same key in a HashMap (or HashSet). I've created a simple example using HashSet to illustrate what I want to do:

import java.lang.*;
import java.io.*;
import java.util.*;

class ClientID {
    private String id;

    public ClientID(String myId)
    {
        id = myId;
    }

    public static ClientID generateNew(Set<ClientID> existing)
    {
        ClientID res = new ClientID("");
        Random rand = new Random();
        do {
            int p = rand.nextInt(10);
            res.id += p;
        } while (existing.contains(res));
        return res;
    }

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

    public boolean equals(String otherID)
    {
        return (id == otherID);
    }

    public boolean equals(ClientID other)
    {
        return (id == other.id);
    }

    public String toString()
    {
        return id;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        HashSet<ClientID> mySet = new HashSet<ClientID>();
        ClientID myId = ClientID.generateNew(mySet);
        mySet.add(myId);
        String input;
        do {
            System.out.println("List of IDs/hashcodes in the set: ");
            for (ClientID x: mySet)
                System.out.println("\t" + x.toString() + "\t" + x.hashCode());
            System.out.print("\nEnter an ID to test if it's in the set: ");
            input = in.readLine();
            if (input == null)
                break;
            else if (input.length() == 0)
                continue;
            ClientID matchID = new ClientID(input);
            if (mySet.contains(matchID))
                System.out.println("Success! Set already contains that ID :)");
            else {
                System.out.println("Adding ID " + matchID.toString() + " (hashcode " + matchID.hashCode() + ") to the set");
                mySet.add(matchID);
            }
            System.out.println("\n");
        } while (!input.toUpperCase().equals("QUIT"));
    }
}

Using this code, it is impossible (as far as I can tell) to produce the output

Success! Set already contains that ID :)

... Instead, it will just keep adding values to that set, even if the values are duplicates (that is, they are equal with the equals method AND they have the same hashcode). If I'm not communicating this well, run the code for yourself and I think you'll quickly see what I mean... This makes lookups impossible (and it also means the Client.generateNew method does NOT work at all as I intend it to); how do I get around this?

It is private, in my original code (which is over 1000 lines, so I didn't want to post it here). I just made it public in order to write this example more easily, I'm lazy like that :) — user1473824
– user1473824, Commented Jun 22, 2012 at 4:37

cheeken · Accepted Answer · 2012-06-22 05:28:45Z

4

In Java, for a particular class to function as a key in a hash, it must implement two methods.

public int hashCode();
public boolean equals(Object o);

These methods must operate coherently: if one object equals another, those objects must produce the same hash.

Note the signature for equals(Object o). Your equals methods are overloading equals, but you must override equals(Object o).

Your overriden equals methods are also broken, as others have noted, because you are comparing String identity, not value. Instead of comparing via str1 == str2, use str1.equals(str2).

Make the following amendments to your code and things should start working properly.

public boolean equals(Object o){
    return o instanceof ClientID ? this.equals((ClientID) o);
}

public boolean equals(String otherID) {
    return id.equals(otherID);
}

public boolean equals(ClientID other) {
    return id.equals(other.id);
}

edited Jun 22, 2012 at 5:28

answered Jun 22, 2012 at 4:27

cheeken

34.7k4 gold badges38 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1473824 Over a year ago

Incidentally, I also needed to change my existing overloads. In my original code the overloads were calling the == operator, when they should have called the equals method. Doh! But after correcting that, and also adding your code, everything seems to be in order. Thanks!

cheeken Over a year ago

@user1473824 Indeed, I amended my post based on that fact. I mistook id for an int.

yshavit · Accepted Answer · 2012-06-22 04:31:56Z

3

HashSet (and HashMap) use the Object.hashCode method to determine which hash bucket the object should go into, but not whether that object is equal to another object also in that bucket. For that, they use Object.equals. In your case, you've tried to implement that method using reference equality of the String ID -- not "actual" equality, but String equality. You also created a new overload of equals, rather than overriding Object.equals.

You can search on SO for lots and lots of questions about why String can't be compared using ==, but the tl;dr version is that you need to override boolean equals(Object) (not an overloaded method of the same name, but that method exactly -- it has to take Object) and check that the incoming object is a ClientID whose String id equals (ont ==s) this ClientID's String id.

answered Jun 22, 2012 at 4:31

yshavit

43.7k8 gold badges89 silver badges127 bronze badges

1 Comment

cheeken Over a year ago

Good call, I hadn't noticed id was a String!

Tomer Shalev · Accepted Answer · 2015-03-04 10:18:13Z

BTW all of those reading this post:

uou should all be careful of any Java Collection that fatches it's children by hashcode, in the case that it's child type's hashcode depends on it's mutable state. an example:

HashSet<HashSet<?>> or HashSet<AbstaractSet<?>> or HashMap varient:

HashSet retrieves it's item by it's hashCode, but it's item type is a HashSet, and hashSet.hashCode depends on it's items state.

code for that matter:

HashSet<HashSet<String>> coll = new HashSet<HashSet<String>>();
HashSet<String> set1 = new HashSet<String>();
set1.add("1");
coll.add(set1);
print(set1.hashCode); //---> will output X
set1.add("2");
print(set1.hashCode); //---> will output Y
coll.remove(set1) // WILL FAIL TO REMOVE (SILENTLY)

End Code

-reason being is HashSet remove method uses HashMap and it identifies keys by hashCode, while AbstarctSet's hashCode is dynamic and depends upon the mutable properties of itself.

hope that helps

Collectives™ on Stack Overflow

Java - HashMap and HashSet not backed by Object.hashCode()?

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related