How do maps check keys?

Question

This has been buzzing me for quite some time now. It's basically that whenever I want to store my own set of objects (I called it MyObject here) as keys in the map, I can't get the keyvalue unless I have the same exact object somewhere saved in my class. Even though I tried to override the equals method in MyObject, where it usually returned true when comparing 2 objects with the same values, nothing changed.

Just to give you a demonstration of what I mean:

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(2, 3);
System.out.println(map.get(2)));

Now, as you'd probably expect, it searches the map for the Integer-object 2 and then prints out 3. If the integer doesn't exist, it prints null. So far so good.

Map<String, Integer> map = new HashMap<String, Integer>();
map.put(new String("hi"), 3);
System.out.println(map.get(new String("hi")));

This one works also as expected. We're just getting the value for the key "hi".

Map<MyObject, Integer> map = new HashMap<MyObject, Integer>();
map.put(new MyObject(), 3);
System.out.println(map.get(new MyObject()));

Even though, there isn't technically a difference between "new MyObject()" and "new MyObject()", it returns null anyway, unless I saved the new MyObject as an instance in my class and used that instance as the parameter for the get-method.

Contrary to my MyObject, the map easily grabbed the key values, if the keys were Strings or Integers. Are those types just privileged or is there a way to tell the map: "Hey, the newly created object is similar with that one in that list"? How does a map compare objects?

Map will check keys depending on the implementation. HashMap uses the hashcode to do it. — porfiriopartida, Oct 02 '13 at 23:29
@porfiriopartida Is there another Map that I could use to compare two similar objects? — felix fritz, Oct 02 '13 at 23:31
Yes, there are few in the Map documentation. Just google for java.util.Map and see All Known Implementing Classes section. — porfiriopartida, Oct 02 '13 at 23:39
@Slanec Yeah, that was exactly what I was looking for. Probably just googled for the wrong tags. — felix fritz, Oct 02 '13 at 23:55

Chris Dodd · Accepted Answer · 2013-10-02T23:47:49.847

In order for two objects to be the 'same' as far as a map is concerned, their hashCode method must return the same value, and the equals method on them must return true when passed the other as an argument.

The default Object.hashCode and Object.equals methods that all objects inherit work with the object identity, so two distinct object are different, even if all of their fields are the same.

So when you write:

map.put(new MyObject(), 3);
System.out.println(map.get(new MyObject()));

assuming you have not overridden hashCode and equals in MyObject, these will be two different objects with different hashcodes that compare non-equal.

If you want your distinct objects to be the 'same' as far as a map is concerned (as classes like Integer and String do), you need to override the hashCode and equals methods:

class MyObject {
public int hashCode() { return 42; }
public boolean equals(Object o) { return o instaceof MyObject; }
};

This will make all MyObject objects the same object as far as a Map is concerned, and your code will print 3.

Now its likely that you don't want ALL MyObjects to be exactly the same -- you probably have some fields in MyObject and you want to treat them as the same only if the fields match. If which case you might want something like:

class MyObject {
Object field1;
Object field2;
int field3;
public int hashCode() { return field1.hashCode() + field2.hashCode() + field3; }
public boolean equals(Object o) {
    if (!(o instanceof MyObject)) return false;
    MyObject a = (MyObject)o;
    return field1.equals(a.field1) && field2.equals(a.field2) && field3 == a.field3; }

score 3 · Answer 2 · answered Oct 02 '13 at 23:39

For any Hash enabled data structure (like HashMap, HashSet) to work correctly its elements or keys must override hashCode() in addition to the equals() method. The reason being that the hash code is used to identify the bucket in which to put the element or key (during insertion) or search in (using equals() during a lookup).

If you do not override hashCode(), the default implementation from Object#hashCode() is used which would return different values even for the objects that you consider equivalent (the equals() method returns true for).

This is why your

 may.get(myObject)

calls are failing in spite of myObject already being present. Since, the hash codes don't match the HashMap never looks for the key in the right bucket. Hence, your equals() never gets called here.

score 1 · Answer 3 · answered Oct 02 '13 at 23:38

To be used as the key of a Map instance in Java, a class must implement consistent hashCode() and equals(). In the absence of implementations of these methods in MyObject, the JVM will use the implementations from Object, where the two instances will NOT be equal.

porfiriopartida · Answer 4 · 2013-10-02T23:52:01.073

Map is an interface, it will check the keys depending on the implementation.

java.util.Map

All Known Implementing Classes:
  AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, 
  EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, 
  Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

HashMap is the implementation you are using there, it will use a HashTable that when you insert an object as key it will get its hashcode (which is an integer) and puts the desired object in that position, imagine that is an array of 256 elements, if your key object generates a 5, then it will store the value object to the array[5]

Here is a part of the code of the get(Object key):

HashMap.get(Object)

314     public V get(Object key) {
315         if (key == null)
316             return getForNullKey();
317         int hash = hash(key.hashCode());
318         for (Entry<K,V> e = table[indexFor(hash, table.length)];
319              e != null;
320              e = e.next) {
321             Object k;
322             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
323                 return e.value;
324         }
325         return null;
326     }

As you can see, there is a special slot for null key, hashCode belongs to Object, so all objects can have that particular integer, after that if will get the object that has as index the produced hash, indesOf hash..

Now the question is, what happens when 2 different objects produce the same hashCode?

Well, there in the get we have a loop, the hashCode is not unique between objects, it will iterate over all the objects of the same hashcode... so if we have 10 objects, 5 of them with the same hashcode and all of them stored as keys, once you try to get one of the repeated hashcodes objects, it will return 5 objects and then it will use equals to determine which is the correct.

The TreeMap will do something similar, but instead of using the hashCode, it will use the integer of the compareTo. It uses a Red-Black tree internally.

And like those two, there are many ways to implement the Map class, as long as you fit the contracts of the interface.

score 0 · Answer 5 · answered Oct 02 '13 at 23:38

Java HashMap uses the hashCode and equals methods to do its dirty work. Different kind of maps uses different ways, eg a TreeMap uses equals and compareTo since it's a sorted map.

When a problem with an HashMap like yours occurs, it means that the general contract of these methods is not fulfilled. An excerpt from Java documentation of Object class:

The equals method implements an equivalence relation on non-null object references:

It is reflexive: for any non-null reference value x, x.equals(x) should return true.
It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
For any non-null reference value x, x.equals(null) should return false.

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

The general contract of hashCode is:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

Mind that without providing a consistent implementation of the hashCode method, if equals is implemented what happens is that two elements are considered equal but its hash code is different, thus weird things (like in your example) occur.

Now, if the HashMap doesn't work as expected with your custom object then 99.99% you are not respecting one or more of these contract entries. Providing a consistent hash code for objects with composition is not so straightforward but there are many simple solutions which are enough good.

score 0 · Answer 6 · answered Oct 02 '13 at 23:41

Contrary to my MyObject, the map easily grabbed the key values, if the keys were Strings or Integers. Are those types just privileged or is there a way to tell the map: "Hey, the newly created object is similar with that one in that list"? How does a map compare objects?

Look into TreeMap in JAVA. TreeMap allows us to specify an optional Comparator object during its creation. The keys should be compatible with the comparator specified. This comparator decides the order by which the keys need to be sorted. TreeMap is slower then hashmap.

Hari · Answer 7 · 2013-10-03T00:10:01.773

Map implementations use the hashCode() method in an object to determine the key to look up in their internal data structures when you call get. In your specific example, let's assume that your MyObject class had an id property:

public class MyObject {
    private int id;

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

    public int getId() {
        return id;
    }
}

Assume you wanted the id property to be used when looking up keys in a map - irrespective of the instance of the object - you'd override the hashCode method in your class to do this:

public class MyObject {
    private int id;

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

    public int getId() {
        return id;
    }

    /**
     * Uses the Jakarta commons-lang HashCodeBuilder class to generate the hash code.
     *
     * @see http://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/builder
     * /HashCodeBuilder.html
     */


    public int hashCode() {
        return new HashCodeBuilder(1, 5)
                .append(id)
                .toHashCode();
    }

    public boolean equals(Object other) {
        if (other == null)
           return false;

        if (other == this) 
           return true;

        return (other.id == this.id);
    }
}

The documentation for HashCodeBuilder explains what the numbers 1 and 5, passed as arguments to the HashCodeBuilder, do - I picked them randomly: the documentation says that they must be unique, random, odd numbers.

How do maps check keys?

7 Answers7