How to write hashCode method for a particular class?

Question

I'm trying to generate a hashCode() method for my simple class but i'm not getting anywhere with it. I would appreciate any help. I've implemented the equals() method, which looks as follows, and would also like to know if I need to implement compareTo() method. I've imported java.lang.Character to use character.hashCode() but it doesn't seem to work.

private class Coord{
    private char row;
    private char col;
    public Coord(char x, char y){
        row = x;
        col = y;
    }
    public Coord(){};

    public char getX(){
        return row;
    }

    public char getY(){
        return col;
    }

    public boolean equals(Object copy){
        if(copy == null){
            throw new NullPointerException("Object entered is empty");
        }
        else if(copy.getClass()!=this.getClass()){
            throw new IllegalArgumentException("Object entered is not Coord");
        }
        else{
            Coord copy2 = (Coord)copy;
            if(copy2.row==this.row && copy2.col==this.col)
                return true;
            else
                return false;
        }
    }

}

Thanks in advance...

The comparTo() method that is giving me java.lang.Comparable casting error..

public int compareTo(Object copy){
        if(copy==null){
            throw new NullPointerException("Object entered is empty");
        }
        else if(copy.getClass()!=this.getClass()){
            throw new IllegalArgumentException("Object entered is not Coord");
        }
        else{
            Coord copy2 = (Coord)copy;
            if(copy2.row==this.row && copy2.col==this.col){
                return 0;
            }
            else if(copy2.col < this.col){
                return -1;
            }
            else{
                return 1;
            }
        }
    }

thanks...

Haldis

I think Overriding equals and hashCode in Java will help you. – Luddite

Answer 1

To implement hashCode, you override the default implementation from Object:

@Override
public int hashCode()
{
    return row ^ col;
}

This isn't really an ideal hash, since its results are very predictable and it is easy for two different Coord objects to return the same value. A better hash would make use of the built-in Arrays class from java.util (http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html):

@Override
public int hashCode()
{
    return Arrays.hashCode(new Object[]{new Character(row), new Character(col)});
}

You can use this method to generate a pretty good hash with any number of fields.

To implement compareTo, you'll want your class to implement Comparable:

public class Coord implements Comparable<Coord>

Once you've done this, you can make compareTo take an argument of type Coord rather than type Object, which will save you the trouble of checking its type.

Minnow

You don't need Java 7 if you use Arrays.hashCode(Object[] args) which has been in Java since 1.5 – Doralynne

@Doralynne I've also written a comparTo() method thatlooks like public int compareTo(Object copy){ if(copy==null){ throw new NullPointerException("Object entered is empty"); } else if(copy.getClass()!=this.getClass()){ throw new IllegalArgumentException("Object entered is not Coord"); } else{ Coord copy2 = (Coord)copy; if(copy2.row==this.row && copy2.col==this.col){ return 0; } else if(copy2.col < this.col){ return -1; } else{ return 1; } } } But I keep getting Coord cannot be cast to java.lang.Comparable. May I know why? – Haldis

@AdityaGore You should ask that in a separate question. – Doralynne

@Doralynne Sorry about that. I've edited my question and added the additional content here. I don't know if two different posts for similar question would be advisable!! – Haldis

You say return row ^ col; "isn't really an ideal hash, since ...it is easy for two different Coord objects to return the same value." I was reading an article and it says, "It is a popular misconception that hashCode provides a unique identifier for an object. It does not." Could you elaborate on this issue? Thanks! – Undulate

Answer 2

Hashcode is an int (32 bits), your data is char (16 bits), so I would probably just do:

@Override
public int hashCode() {
    return (row << 16) + col;
}

This puts the bits from row in the first 16 bits and the bits from col in the last 16 bits, so this is a perfect hash function for this class.

If you refactor your class to be more complicated, I recommend using nullptr's answer.

---

To use Comparable, do:

public class Coord implements Comparable<Coord>

Doralynne

Forgive me if I'm wrong, but you will never have collisions; the possible objects seem to map 1-to-1 with the possible hashCodes. And this should be really fast, so this is an awesome answer. – Semiquaver

Yep. "Fairly unlikely" is understating it. This is actually a perfect hash function for a pair of chars; two objects will have the same hash code if, and only if, they represent equal values. – Projectile

@CoryKendall Well, remember, a HashMap uses modulus on the hashCode() value, it doesn't contain 2^32 possible cells. So for certain characters and moduluses and HashMap sizes, it will still have collisions. However, I agree I could have phrased it better :) – Doralynne

@CoryKendall I changed the wording to be more accurate ;) – Doralynne

Answer 3

I found very valuable information concerning this topic and many other topics in the Effective Java book, written by Joshua Bloch. Look at page 45 for further information about hashCode() and equals().

If you use an IDE like Eclipse you can let it generate the hashCode() and equals() methods. For your class the result would be:

class Coord implements Comparable<Coord> {

    private char row;
    private char col;

    public Coord(char x, char y) {
        row = x;
        col = y;
    }

    public Coord() {
    };

    public char getX() {
        return row;
    }

    public char getY() {
        return col;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + col;
        result = prime * result + row;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Coord other = (Coord) obj;
        if (col != other.col)
            return false;
        if (row != other.row)
            return false;
        return true;
    }

    public int compareTo(Coord param) {
        // Implementation according to http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html
        return 0;
    }

}

Cahier

I know this is a pretty typical implementation, but it's got some tricky numerical downsides. If you have just two components you're hashing - such as here - and they both have the same value (not an unusual occurence), this is equivalent to 32*hash+offset which has 5 less bits of entropy than your source hash. Not ideal. – Vaporific

Answer 4

similar to durron597's answer, you can try this if your input is bounded by char (between 0 and 65535 )

public int hashCode(){
   return row * 100000 + col;
}

Seamy

This answer is redundant, and while it's correct, it's tricky because it includes a non-obvious magic number that only works because it's greater than or equal to 65536 – Vaporific