Hash function based on ISBN

Question

I'm trying to create a hash function for my own custom class. It uses a string value of 4 chars as a key, which is unique to every object, which I then encode using getBytes(), the part actually used to calculate to the hash value

    public int hashCode() {
        String fixedISBN = getIsbn().toString().replace("-", "");
        fixedISBN = fixedISBN.substring(fixedISBN.length() - 4, fixedISBN.length());
        byte[] binary  = fixedISBN.getBytes();
        String result = "";
        for(byte b: binary){
            result += b;
        }
        int hashValue = Integer.parseInt(result);
        return hashValue * 53;
    }

fixedISBN will always be a number ranging from somewhere between 1-9999. so fixedISBN for one object of this class can be 3321 will another object's fixed ISBN can be 209. Will this amount to a good hash function?

Answer 1

Main points for a good hash function (to be used, for example, in HashMap)

1. The hash function is as fast as possible
2. The hash function "uniformly" distributes the data across the entire set of possible hash values.
3. The hash function generates very different hash values for similar objects.

Your code:

• Has String manipulation replaceAll() that is not fast. So that rules out the point 1.
• Does not spread the input over the range uniformly, but Gaussian.
• Does not give similar object very different values

So, I would not consider it a good hash function :)

If you want to read more, the wikipedia has a great start.

Answer 2

Well, it all depends on your definition of a "good" hash function. Provided the function is consistent with the equals() method, one could return a constant and it would work (but might degrade performance).

Some of this is really weird. If fixedISBN starts out as "ABC123":

• First you reduce it to "C123"
• The you build result as "67495051"
• Then you convert that to an integer 67495051.

In this case, provided the fixedISBN is digits, you are going to wind up with one of 3710000 possible values. This is because you merely concatenate the digits character values. Try making result an int and changing the line inside the loop to something like result = result * 253 + b; (You could do * 10 if you've guaranteed only digits.) (Note that ISBN10s allow the character "X" in the last place. This changes a few things, but not many.)

Some changes I would recommend:

• Don't use getISBN() to get the key. Read it directly from your private variables. This allows the accessor to be make the data pretty if it needs to, and shows that your method is a core internal bit.
• Avoid the toString(). If getISBN() is actually an object, maybe you should just be calling it's hashCode() method.
• If you are getting fixedISBN as a string, why not just use that string's hashCode() as your own?
• The final * 53 is odd. You might consider adding a constant if you are using the hash of something else, just to make your hash different in case both are added to a HashSet or the like. That your multiplier is prime is good.

One other point: hashcode() should be fast. By that standard, this is not a good hash function. You would be better off if no objects were created in the function.

Answer 3

You seem to be missing the point. Range of hashcodes is not that important, variability is.

You throw away much of the variability of your data. The last 4 digits of an ISBN number may vary fastest, but there are more than 9999 books, so the other digits do vary, so they should be used in deriving the hashcode.

The developers of Java put a lot of thought into their designs, so in general you shouldn't rush to reinvent the wheel - make use of hashcode methods in the standard class libraries, rather writing your own. I would strip dashes or spaces from.the ISBN number and then use String.hashcode(), or possibly Long.parseLong().hashcode().

Given that you need to normalize (strip dashes or spaces) when comparing for equality as well, I would expect to do this in the class constructor and store that value. The toString() method would be responsible for formatting the ISBN for human consumption.

This turns out to be a good argument for storing the ISBN as a Long, as that makes the equals and hashcode methods simple and efficient.

If the hashcode is going to be heavily used it's worth calculating it once, perhaps in the constructor, and storing it rather recalculating at each use.