CODEWITHSUNDEEP
javahashmapkeyequalshashcode
Mathis Hobden
Mathis Hobden

Reputation: 356

Overridden equals not mandatory for efficient hashing keys

In all questions i saw about overridden equals and hashcode methods people always say if you override equals method you should override also hashcode method and vice versa in order to avoid problems while getting objects from Hash collections.

Personally i don't see that the vice versa is right for that purpose, Let's consider that we use an object(with attributes) as keys in a HashMap and we don't need to test the equality between two instances of that object.

If we override the hashcode method in an efficient manner(based on attributes & other rules), so we can have unique keys, in this case for the HashMap we gonna have a unique value in each bucket, and the HashMap will not use the equals method to compare values in a bucket since we have one value in each bucket.

the contract side:

Am I wrong?

Edit : (after search, below answers, and looking in the source code of HashMap)

Why should we override equals method also?

Initial conditions, unique hashcodes and no equals() overridden

Object.equals() perform a reference comparison, and this method is used in the methods put and get

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

If we don’t override equals we will not be able to retrieve values from the HashMap if we lose the reference of the keys, e.g. of keys references which are not visible to another code. The only way to read the HashMap is to use an Iterator, plus comparing the values to retrieve the exact pair:

First put: [key:Instance1Obj(144756696),  value:Person1Obj(“Baron”, “Steven”)]
Second put: [key:Instance2Obj(17488696),  value:Person2Obj(“Hewlett”, “Emily”)]

If we want to retrieve the account of Baron Steven based on his account number, we can’t only just create a new object having the same account number say Instance88Obj(144756696) and invoke the get method to retrieve the value. In this case we will have a null as a result because the get method uses a comparison based on the reference of the key, even if the hashcode will be the same.

if equals is not overridden, putting a new value through a new instance key(but having same hashcode) in order to update it, will not work, just another pair key/value will be added:

First put: [key:Instance1Obj(144756696),  value:Person1Obj(“Baron”, “Seven”)]
Second put: [key:Instance2Obj(144756696),  value:Person2Obj(“Baron”, “Steven”)]

Normally we are expecting to substitute the value “Seven” by “Steven” but the substitution will not happen 

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Conclusion :

==> If you override hashcode, override equals also.

==> If you override equals, override hashcode also.(out of this topic :))

Upvotes: 3

Views: 2007

Answers (6)

hyde
hyde

Reputation: 62906

In standard Java HashMap, equals is always used to determine if key is in bucket. If hashCode gives right bucket with just one item, but equals returns false against that one key, that means key is not in there.

If you do not override equals, it uses object reference. If you want to use object's value as key (that is, you can have different object instances with same value), instead of requiring exact same object instance (identical instances are not equal), then you need to write equals which implements comparing values.

Default hashCode is as efficient as you can have with default equals. Overriding just hashCode will probably decrease performance, without changing behaviour (equals still determines if two key objects are equal or not). Doing this is pointless.

You did not ask this, but additionally, if you override equals without overriding hashCode, then you break HashMap keys, because hashCode probably takes you to wrong bucket, and equals will not find the key, because it only checks that one bucket.

What you can do: If you can guarantee different hashCode for every item, you can write equals which compares just the hash codes. If you cache the hash code in the object, then this can improve performance, making equals to compare just two ints. With memory overhead, of course.

Upvotes: 2

barfuin
barfuin

Reputation: 17494

The value space of hash codes is orders of magnitude greater than the number of buckets in a hash map. So unless we're talking specialized Map implementations like EnumMap, you will always end up with more than one object per bucket, even given perfect hash codes.

Objects that do not override equals() will only be considered equal when they are the exact same object, regardless of their field values. Thus, overriding only hashCode() is pointless because all it would accomplish is a slight performance penalty (at least because your custom hash code takes longer to compute). It may even be a big performance penalty if the custom hash code is not perfect.

Whenever you override hashCode() and equals(), you're doing it because you want the object's field contents to matter. And that's not going to happen unless you override both.

Upvotes: 2

Stephen C
Stephen C

Reputation: 719576

The contract says that if two objects are equal that they should have the same hashcode. But in addition, hash tables work best if objects that are not equal should have different hashcodes.

If you override the default hashCode method without also overriding the default equals method, you are liable to make the behaviour of hashcode suboptimal; i.e. giving more cases where hashCode returns the same value for objects that not equal. That is liable to give you more collisions in your hash table, depending on the details of your hashCode override and the instances used by your application. The end result would be a measurable drop in performance.

So while the "vice versa" is not strictly required for correct application behaviour, the advice is still valid in general. It is best if your equal and hashCode methods have matching semantics.

Upvotes: 1

Wins
Wins

Reputation: 3460

different hashcodes leads to not equal objects ==> it says "leads" not says "always". Two equal objects always return the same hash code but two non equal objects very hardly return the same hash code if the hashcode method is not overridden.

Upvotes: 0

Tim B
Tim B

Reputation: 41208

It is possible to avoid implementing equals, or to avoid implementing hashcode. In both cases you open yourself to a world of potential pain. After all remember that the Hash is used to separate objects into buckets, and then the objects within the buckets need checking for equality still, you are relying on the collection objects you are using behaving in exactly the way you need.

The guidelines are there to prevent a lot of problems and there is no good reason to avoid following them other than to try and be clever and by doing so open yourself up for a load of problems in the future.

Upvotes: 1

Dawood ibn Kareem
Dawood ibn Kareem

Reputation: 79875

If your class uses the equals method from Object, then any idempotent hashCode implementation is fine. If it uses the equals method from some superclass other than Object, then you need to make sure that your hashCode implementation is compatible therewith.

Upvotes: 4

Related Questions