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?

Answer 1

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

Answer 2

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);
}

Answer 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.