CODEWITHSUNDEEP
javahashcodeinteger-hashing
Hristo
Hristo

Reputation: 46497

what would be a good hash function for an integer tuple?

I have this class...

public class StartStopTouple {

    public int iStart;
    public int iStop;
    public int iHashCode;

    public StartStopTouple(String start, String stop) {
        this.iStart = Integer.parseInt(start);
        this.iStop = Integer.parseInt(stop);
    }

    @Override
    public boolean equals(Object theObject) {

        // check if 'theObject' is null
        if (theObject == null) {
            return false;
        }
        // check if 'theObject' is a reference to 'this' StartStopTouple... essentially they are the same Object
        if (this == theObject) {
            return true;
        }

        // check if 'theObject' is of the correct type as 'this' StartStopTouple
        if (!(theObject instanceof StartStopTouple)) {
            return false;
        }

        // cast 'theObject' to the correct type: StartStopTouple
        StartStopTouple theSST = (StartStopTouple) theObject;

        // check if the (start,stop) pairs match, then the 'theObject' is equal to 'this' Object
        if (this.iStart == theSST.iStart && this.iStop == theSST.iStop) {
            return true;
        } else {
            return false;
        }
    } // equal() end

    @Override
    public int hashCode() {
        return iHashCode;
    }
}

... and I define equality between such Objects only if iStart and iStop in one Object are equal to iStart and iStop in the other Object.

So since I've overridden equals(), I need to override hashCode() but I'm not sure how to define a good hash function for this class. What would be a good way to create a hash code for this class using iStart and iStop?

Upvotes: 2

Views: 3032

Answers (3)

ratchet freak
ratchet freak

Reputation: 48206

the simplest might be best

iHashCode = iStart^iStop;

the XOR of the two values

note this will give equal hashcodes when start and stop are swapped

as another possibility you can do 

iHashCode = ((iStart<<16)|(iStart>>>16))^iStop;

this first barrel shifts start by 16 and then xors stop with it so the least significant bits are put apart in the xor (if start is never larger than 65k (of more accurately 2^16) you can omit the (iStart>>>16) part)

Upvotes: 2

toto2
toto2

Reputation: 5326

From Bloch's "Effective Java":

int iHashCode = 17;
iHashCode = 31 * iHashCode + iStart;
iHashCode = 31 * iHashCode + iStop;

Note: 31 is chosen because the multiplication by 31 can be optimized by the VM as bit operations. (But performance is not useful in your case since as mentioned by @Ted Hopp you are only computing the value once.)

Note: it does not matter if iHashCode rolls over past the largest int.

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234807

I'd be tempted to use this, particularly since you're going to memoize it:

Long.valueOf((((long) iStart) << 32) | istop)).hashcode();

Upvotes: 2

Related Questions