0
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ Do you mean that you will have up to 9999 objects, each with a unique identifier? Why would you need anything more than that number as your hashcode? What value do you believe multiplying by 53 will add? More information about the format of the ISBN string would help us understand what's going on here. \$\endgroup\$ Feb 11 at 22:14
  • \$\begingroup\$ ISBN is a unique identifier every book has. It consists of 13 different letters, but only the 4 last letters are of interest to me, since those are the only ones that tend to vary. In many cases the first 9 letters are pretty much identical in many cases. I now realize that I wrote the question poorly. What I meant was that ISBN will be number value from 1 to 9999. To have a greater has value I convert it into its byte representation, which I then multiply with an arbitrary prime number to ensure a more even spread \$\endgroup\$
    – EddyDantes
    Feb 11 at 23:07
  • 1
    \$\begingroup\$ More specifically, doesn't an ISBN consist of only digits, not letters? I'm looking at en.wikipedia.org/wiki/International_Standard_Book_Number which states "The ISBN is thirteen digits long if assigned on or after 1 January 2007, and ten digits long if assigned before 2007.". If so, why not just use the digits in the ISBN as the hash code? \$\endgroup\$ Feb 12 at 2:01

3 Answers 3

1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ +1 for the last remark alone :) \$\endgroup\$ Feb 15 at 15:26
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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