8

In looking at different options for overriding hashCode(), I was directed to Objects.hashCode(Object[]) in Google's guava-libraries (javadoc). The javadoc states that it delegates to Arrays.hashCode(Object[]). Is it safe to use this method in many different object types? Isn't this prone to hash collision, or is this not likely simply because containers usually only contain one type of object?

As a simple example, consider the following classes,

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(name);
    }
}

public class HashCodeDriver {
    public static void main(String[] args) {
        final String name = "moe";
        Student s = new Student(name);
        Teacher t = new Teacher(name);

        long studentHash = s.hashCode();
        long teacherHash = t.hashCode();
        System.out.println("studentHash=" + studentHash + " teacherHash=" + teacherHash);
        if(studentHash == teacherHash) {
            System.out.println("hash codes match");
        }
        else {
            System.out.println("hash codes don't match");
        }
    }
}

Output:

studentHash=108322 teacherHash=108322
hash codes match

The objects are two different types but are generating the same hash code. Isn't this a problem? Should I pass in the class as the first parameter to prevent this collision? For example,

public class Student {
    private final String name;

    public Student(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Student.class, name);
    }
}

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(Teacher.class, name);
    }
}

Is this why the javadoc warns about only supplying a single object to this method? From the javadoc,

Warning: When a single object is supplied, the returned hash code does not equal the hash code of that object.

3 Answers 3

6

It's not a problem when 2 different objects of 2 different types have the same hash code.

Hopefully, when you are going to build your HashMap you are not going to mix Students and Teachers as the keys to that map. And even in the case when you want to do HashMap<Object, Object> you will be OK, because

assertFalse( new Teacher( "John Smith" ).equals( new Student( "John Smith" ) );

This is why it's important to override both hashCode and equals.

The only drawback of delegating to Arrays.hashCode(Object[]) may be that sometimes it may be too expensive from the performance point of view.

For example, in your case, this would be a much better hash method for either Teacher or Student.

@Override
public int hashCode() {
    return name.hashCode();
}
8
  • 1
    This conversation is a bit reversed. Usually, developers override equals and forget hashcode. I don't see how HashMap<Object, Object> would be ok in this case. Where did your assertFalse come from? I can't find it in HashMap. From what I see, HashMap only uses hashCode, not equals. So, two different type objects could collide, and that's why I'm leery of Objects.hashCode(Object[]). I agree that it's always important to override hashCode and equals as a pair, but from my understanding, if two objects have the same hash code, they should be equal and vise versa. Commented May 28, 2011 at 5:04
  • 2
    @nondescript1 - I guess you misunderstood equals and hashcode contract - you must override hashcode when you override equals and two equal objects should produce same hashcode but it's not vice versa. the general contract of Object#hashcode says - 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 hashtables.
    – Premraj
    Commented May 28, 2011 at 10:43
  • 3
    @nondescript1 - and about your statement "From what I see, HashMap only uses hashCode, not equals" > how you conclude this? can you point me the doc/spec link? As per my understanding the HashSet will store the object in hash buckets by using hashcode value but will call equals on it to compare the equality. So if your Teacher and Student returns the same hashcode they will be placed in the same bucket but if you want to get Teacher from Map it will check the equals and then will return you the valid Teacher or null, so there won't be any collision.
    – Premraj
    Commented May 28, 2011 at 10:55
  • @Falcon - you're correct. I guess my understanding of both hashCode and hash-backed containers was off. I was simply perusing the open source for HashMap. Is there a better documentation to refer to? So, are we concluding that Objects.hashCode(Object[]) is safe for most use cases then? Commented May 28, 2011 at 14:31
  • 1
    @Falcon, @nondescript1. I am not talking about hash distribution performance of Arrays.hashCode, it's fine. This is purely talking about doing too much in a simple case presented here. If you are delegating to Arrays.hashCode( Object[] ), then you are taking performance hit by at least constructing an array. My point here is, if your object has only a single field, in most cases it's fine to delegate to hashCode of that field. Commented May 28, 2011 at 17:29
3

The warnings only says that x.hashCode() != Objects.hashCode(x) is true. (Okay, this is true most of the time. They could still collide for some values. It's actually not equal for most objects.)

A valid hashCode/equals implementation is:

public class Teacher {
    private final String name;

    public Teacher(String name) {
        this.name = name;
    }

    @Override public equals(Object obj){
        if(obj == this) return true;
        if(!(obj instanceof Teacher)) return false;
        return Objects.equal(name, ((Teacher) obj).getName());
    }

    @Override public hashCode(){
        return 0;
    }
}

This is a valid although all hash values collide. From hashCode() javadoc:

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.

The difference to a "normal" implementation is that the performance of this code will be much worse. HashMaps for example will degenerate to a lists like performance for lookups.

Even with this implementation:

@Override
public int hashCode() {
    return Objects.hashCode(Teacher.class, name);
}

it's possible (but very unlikely) that the hash values of different classes collide. This is the case if the hashes of the class names are the same for both classes.

This kind of optimization should be a last resort when there are a lot of instances from different types with the same name in a collection that uses hashCode() internally. The overall efect will be limited: if you have n types you have at most n collisions due to this scenario. Other factors are probable to dominate the performance characteristics.

1
  • in your equals implementation the line - if(!(obj instanceof Teacher)) return true; should return false instead of true
    – Premraj
    Commented May 28, 2011 at 11:02
0

If you are mixing many different concrete types in the same map's key set, you can still use Objects.hashCode() and minimize collisions by xoring the output with a different value per concrete type.

class Class1 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0x12b7eff8;
  }
}

class Class2 {
  public int hashCode() {
    return Object.hashCode(...) ^ 0xe800792b;
  }
}

By xoring with a value that is randomly chosen, but stable per-concrete class, you eliminate the chance of collisions that might occur solely because the arguments to Object.hashCode are equivalent.

Warning: When a single object is supplied, the returned hash code does not equal the hash code of that object.

Is this why the javadoc warns about only supplying a single object to this method? From the javadoc,

No. This warning is not about the chance of collisions between instances of different concrete classes that have the same members. It is instead warning about false negatives in hashcode matches due to an assumption that the hash of a single value is the same as that of the singleValue.hashCode().

For example, look at the assumption made below in the incorrect fast track code that tries to avoid an equality check by using cached hash codes:

class Name {
  int cachedHashCode;

  ...
}

class Person {
  int cachedHashCode;  // 0 if not computed

  private final Name name;

  public boolean hasName(Name n) {
    return ((cachedHashCode != 0 && n.cachedHashCode != 0) 
            && cachedHashCode == n.cachedHashCode)
        || n.equals(name);
  }

  public int hashCode() {
    if (cachedHashCode == 0) { cachedHashCode = Object.hashCode(name); }
    return cachedHashCode;
  }
}
4
  • I suppose that Object.hashCode(...) ^ 0x12b7eff8 destroys the distribution of values for one type. Object.hashCode(0x12b7eff8, ...) should be okay. Object.hashCode(..., getClass().getName()) may be a bit more readable. Commented May 28, 2011 at 5:15
  • @Thomas, What do you mean by "destroys the distribution?" Commented May 28, 2011 at 16:42
  • I thought that all bit operations change the distribution (simplest example hashCode | Integer.MAX_VALUE). Well, exor is the one that does not change the distribution of values. They are still equality distributed. Commented May 28, 2011 at 17:19
  • @Thomas Jung, yep. Neither xor nor xnor decrease the number of bits of entropy. Commented May 28, 2011 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.