hashCode : Java Glossary

The key thing to understand about hashCodes is that they need not be unique, just as close to unique as practically possible.

HashCodes in a Nutshell

HashCode Misconceptions

• Uniqueness: Some people try to use HashCodes as unique identifiers. You can’t count on hashCodes to be unique. They way they are properly used, this does not cause any serious problem.
• Denseness: Some people fret over trying to make hashCodes come out in some narrow band of numbers. The way they are used, they are trimmed down to size by taking the modulus relative to some prime or by discarding high order bits, so there is no point.
• Negative hashcodes: You can safely treat hashcodes as unsigned or signed when computing them. You don’t have to go to any special lengths to keep them positive.

String.hashCode Implementation

Object.hashCode Implementation

The Gemini Twins: equals and hashCode

The default hashCode just uses the address of the Object and the default equals method just compares addresses. If you override one of these two methods, you must override the other to match. The rules are:

• It is ok, unavoidable, but not desirable, if two Objects that do not compare equal have the same hashCode.
• Two Objects that compare equal must have the same hashCode.

So if you had a Fruit Object with a flavour and colour field, and you decided that any two Objects with the same flavour were for all intents and purposes equal, you would define your equals and hashCode methods like this:

As a rule of thumb, any time you use an Object as a key in a Map or Set (e.g. Hashtable, HashMap, HashSet, TreeMap etc.) you must redefine both equals and hashCode in such a way both incorporate that same and all the fields of the logical key. Fields in the key Object irrelevant to lookup should not be included in either method.

Simple HashCodes

Calculating Aggregate hashCodes with XOR (exclusive OR)

XOR has the following nice properties:

• It does not depend on order of computation.
• It does not waste bits. If you change even one bit in one of the components, the final value will change.
• It is quick, a single cycle on even the most primitive computer.
• It preserves uniform distribution. If the two pieces you combine are uniformly distributed so will the combination be. In other words, it does not tend to collapse the range of the digest into a narrower band.

• It treats identical pairs of components as if they were not there.
• It ignores order. A ^ B is the same a B ^ A. If order matters, you want some sort of checksum/digest such as Adlerian. XOR would not be suitable to compute the hashCode for a List which depends on the order of the elements as part of its identity.
• If the values to be combined are only 8 bits wide, there will be effectively only 8 bits in the xored result. In contrast, multiplying by a prime and adding would scramble the entire 32 bits of the result, giving a much broader range of possible values, hence greater chance that each hashcode will unique to a single Object. In other words, it tends to expand the range of the digest into the widest possible band (32 bits).
• XOR is fairly easily degraded by patterns in the data. If you are not getting an even spread, it might pay to go for a higher overhead scrambling mechanism such as Aldlerian, CRC or even MD5 or SHA1.
• If you XOR a number of small quantities the result is still a small quantity. It does not exploit the high order bits for additional variability unless you do some sort of shifting.

// object1 has
o1.string1 = "apple";
o1.string2 = "orange";
// and object2 has
o2.string1 = "orange";
o2.string2 = "apple";

Here is how to write a hashCode to combine fields:

Here is roughly howString.hashCode works

Here is a fast hash algorithm you can apply to bytes, short, chars, ints, arrays etc. I used an assembler version of

Here is a straight-forward xor hash of all the bytes. The disadvantage is the result is only 8-bits.

Tips

• Don’t sweat writing a perfect hashCode. Test your code to see if look up is the bottleneck before fussing too much.
• It is easy to concoct a variety of hashCode methods and test them far more quickly than you can mathematically analyse the tradeoffs.
• If you write a Collection that uses hashCode, stress test it with a HashCode method that always returns 0.
• If you have an expensive hashCode calculation, consider caching the result.
• The important thing about a hashCode for HashMap is that in produces lots of variability in the low order bits. As a simple check, do a histogram of the frequency of the low order byte. Ideally you should be getting all 256 possible values roughly equally. One simple way of adding variability to your hashCode function is to xor ^ high order bits onto the lower order ones.

When Do You Need A Custom equals and hashCode?

If you know the key values in advance, it is possible to construct a hashCode function that has no collisions.

The One Key Catch

In contrast, with HashMap you have more freedom. Your Objects don’t have to implement a useful hashCode/equals, but any keys you use do. Since you can define different hashCode/equals for different types of key, you can have multiple HashMaps on the same group of Objects looking up by different keys.

• Arrays are Objects and use the lame Object. hashCode. To get a proper hashCode that is based on the values in the array, you need Arrays. hashCode.
• The packing method of creating hashCodes will not work will with HashMap, because HashMap discards the high order bits of the hashCode.

Learning More