What happens to the lookup in a Hashmap or Hashset

Question

In a Hashmap the hash code of the key provided is used to place the value in the hashtable. In a Hashset the obects hashcode is used to place the value in the underlying hashtable. i.e the advantage of the hashmap is that you have the flexibility of deciding what you want as the key so you can do nice things like this.

Map<String,Player> players = new HashMap<String,Player>();

This can map a string such as the players name to a player itself.

My question is is what happens to to the lookup when the key's Hashcode changes.

This i expect isn't such a major concern for a Hashmap as I wouldn't expect nor want the key to change. In the previous example if the players name changes he is no longer that player. However I can look a player up using the key change other fields that aren't the name and future lookups will work.

However in a Hashset since the entire object's hashcode is used to place the item if someone slightly changes an object future lookups of that object will no longer resolve to the same position in the Hashtable since it relies on the entire objects Hashcode. Does this mean that once data is in a Hashset it shouldnt be changed. Or does it need to be rehashed? or is it done automatically etc? What is going on?

Answer 1

With Java's hashes, the original reference is simply not found. It's searched in the bucket corresponding the current hashcode, and not found.

To recover from this after the fact, the Hash keySet must be iterated over, and and any key which is not found by contains method must be removed through the iterator. Preferable is to remove the key from the map, then store the value with new key.

Answer 2

In your example, the keys are String which are immutable. So the hashcode of the keys won't change. What happens when the hashcode of the keys changes is undefined and leads to "weird" behaviour. See the example below, which prints 1, false and 2. The object remains in the set, but the set looks like it is broken (contains returns false).

Extract from Set's javadoc:

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

public static void main(String args[]) {
    Set<MyObject> set = new HashSet<>();
    MyObject o1 = new MyObject(1);
    set.add(o1);
    o1.i = 2;
    System.out.println(set.size());       //1
    System.out.println(set.contains(o1)); //false
    for (MyObject o : set) {
        System.out.println(o.i);          //2
    }
}

private static class MyObject {
    private int i;

    public MyObject(int i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return i;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final MyObject other = (MyObject) obj;
        if (this.i != other.i) return false;
        return true;
    }
}

Answer 3

The HashSet is backed up by a HashMap.

From the javadocs.

This class implements the Set interface, backed by a hash table (actually a HashMap instance).

So if you change the hashcode, I doubt whether you can access the object.

Internal Implementation Details

The add implementation of HashSet is

 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
 }

The key is the elem and value is just a dummy Object called PRESENT

and the contains implementation is

public boolean contains(Object o) {
        return map.containsKey(o);
}

Answer 4

In your example, a String is immutable so its hashcode cannot change. But hypothetically, if the hashcode of an object did change while was a key in a hash table, then it would probably disappear as far as hashtable lookups were concerned. I went into more detail in this Answer to a related question: https://stackoverflow.com/a/13114376/139985 . (The original question is about a HashSet, but a HashSet is really a HashMap under the covers, so the answer covers this case too.)

It is safe to say that if the keys of either a HashMap or a TreeMap are mutated in a way that affects their respective hashcode() / equals(Object) or compare(...) or compareTo(...) contracts, then the data structure will "break".

---

Does this mean that once data is in a Hashset it shouldnt be changed.

Yes.

Or does it need to be rehashed? or is it done automatically etc?

It won't be automatically rehashed. The HashMap won't notice that the hashcode of a key has changed. Indeed, you won't even get recomputation of the hashcode when the HashMap resizes. The data structure remembers the original hashcode value to avoid having to recalculate all of the hashcodes when the hash table resizes.

If you know that the hashcode of a key is going to change you need to remove the entry from the table BEFORE you mutate the key, and add it back afterwards. (If you try to remove / put it after mutating the key, the chances are that the remove will fail to find the entry.)

What is going on?

What is going on is that you violated the contract set out clearly in the HashMap javadocs. Don't do that!