Definitive documentation on Java HashSet / HashMap custom object as key?

Question

I'm trying to find the definitive documentation on how to use a custom object as the key for HashMap or as the object stored in HashSet.

From reading various postings, I've somehow discovered that you're supposed to override the two methods equals() and hashCode() in the custom object (e.g. Overriding equals and hashCode in Java).

However, when I read the Oracle/Sun official Javadocs for HashSet and HashMap, they do not mention overriding these methods at all. Are these instructions buried somewhere else in the documentation? If so, where can I find them?

BeeOnRope · Answer 1 · 2016-12-06T16:27:57.097

3

You don't need to override equals and hashCode, but you do need to have consistent equals and hashCode methods.

That is, if obj.equals(obj2), then it must be the case that obj.hashCode() == obj2.hashCode(). The converse (non-equals() objects having unequal hashCode() values) should be true as often as possible for good performance, but this is not a requirement and can't always be satisfied if your objects have more than 2^32 states).

The default equals() and hashCode() methods obey this and have identity semantics - objects are only equal if they are actually the same object (obj == obj2).

If you want value semantics - for example, that two objects with the same state are equal, you should override those methods.

edited Dec 06 '16 at 16:27

answered Feb 20 '13 at 00:10

BeeOnRope

60,350
16
207
386

This does not answer my question. Where is the definitive documentation on using these two methods with HashSet/HashTree? Stackoverflow answers, as much as I appreciate them, are not definitive documentation. – stackoverflowuser2010 Feb 20 '13 at 00:25
1

There is a [good answer](http://stackoverflow.com/a/14970001/149138) below which links to Oracle javadoc for `Object`, which documents them more formally. – BeeOnRope Feb 20 '13 at 00:51
please consider using immutable datatypes! – El Hocko Feb 20 '13 at 00:57
What happens if you get a hash collision. Then `obj.equals(obj2) == false` and `obj.hashCode() == obj2.hashCode`. – Arwed Mett Sep 08 '22 at 07:52
@ArwedMett that's "fine" as described in the post. It is only required that object equality _implies_ equal hash codes, not the other way around (it is not required that equal hash codes implies equality). For good performance, however, distinct objects should have distinct hash codes with high probability. – BeeOnRope Sep 09 '22 at 04:32

Andy Thomas · Answer 2 · 2013-02-20T00:13:36.050

0

The Collections API describes contracts in terms of equals() and hashCode(). If you want multiple instances of a key to be equal to each other, then you need to override equals() and hashCode(), following the contract specified by the Object class.

The Set interface describes its contract:

More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

The contracts for equals() and hashCode() are specified by the Object class.

Here is the contract for Object.equals().
Here is the contract for Object.hashCode().

In "Effective Java," Joshua Bloch suggests that you always override hashCode when you override equals, to avoid violating those contracts.

edited Feb 20 '13 at 00:13

answered Feb 20 '13 at 00:06

Andy Thomas

84,978
11
107
151

(1) So the instructions are indirectly reached, right? HashSet leads to Set, which mentions equals(), which is defined in Object. (2) If I use TreeSet instead of HashSet, I only have to override Comparable in the custom object (or provide a Comparator to the TreeSet), right? There is no mention of equals() or hashCode() with TreeSet. – stackoverflowuser2010 Feb 20 '13 at 00:24
The contact for `equals` and `hashCode` is defined in `Object` because that's where those methods are defined. You should define them in a consistent way regardless of whether you are going to use them in a `HashSet` or not. It wouldn't make sense to have each container define their own contract for these methods, given that any object can choose only one implementation - meaning that all collections should agree on how to use these methods. Again, your focus on `overriding` is misplaced. You never have to override any of those methods - just ensure they are consistency defined. – BeeOnRope Feb 20 '13 at 00:54
@stackoverflowuser2010 they are not indirect. As I said in my answer, they are indicated in the documentation for `Set`and `Map`. Those are the interfaces that impose the restrictions, so that's where one wants to look. HashMap, HashSet, TreeSet, are simply implementations and it's not their purpose to specify the contracts, rather to honour them. – entonio Feb 20 '13 at 02:10
1

@stackoverflowuser2010 Both `Comparable` and `Comparator` discuss consistency with `equals` (and therefore implicitly `hashCode`). – Tom Hawtin - tackline Feb 20 '13 at 02:28

score 0 · Answer 3 · answered Feb 20 '13 at 00:06

0

It's discussed at length in the contract for java.lang.Object.

answered Feb 20 '13 at 00:06

user207421

305,947
44
307
483

score 0 · Answer 4 · answered Feb 20 '13 at 00:08

In the documentation for Set and Map, which are the interfaces they implement.

The requirement isn't arbitrary, it is the only way to guarantee that the methods of the interfaces work as expected - by being able to tell when keys which may be different Java objects should really be treated as the same key or not - for instance, "abc" and "ab" + "c" are different objects, but the implementation of equals ensures they are considered the same key. As to hashCode, it is needed to find the meaningful placement inside the data structure that underlies those interfaces.

score 0 · Answer 5 · edited May 23 '17 at 12:08

As far as I know, the key must be a Immutable Object.

If it is mutable, it's hash code can change after adding it to map. Then the map can have problems finding it

Setting own class as key in java Hashmap

Here is an example that illustrates this:

import java.util.HashMap;
class Test{

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

public class Main {
    public static void main(String[] args) {

        HashMap<Test, String> hm = new HashMap<>();
        Test t1 = new Test();
        hm.put(t1, "found");

        System.out.println(hm.get(t1));

        t1.i=2;

        System.out.println(hm.get(t1));


    }


}

/*
output:
found
null
*/

Definitive documentation on Java HashSet / HashMap custom object as key?

5 Answers5