hashCode : Java Glossary


hashCode

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 Calculating Aggregate HashCodes with XOR
HashCode Misconceptions Tips
String.hashCode Custom hashCode
Object.hashCode The Catch
equals and hashCode Learning More
Simple HashCodes Links

HashCodes in a Nutshell

If you want to file something away for later retrieval, it can be faster if you file it numerically rather than by a long alphabetic key. A hashCode is a way of computing a small (32-bit) digest numeric key from a long String or even an arbitrary clump of bytes. The numeric key itself is meaningless and the hashCode functions for computing them can look a bit insane. However, when you go to look for something, you can do the same digest calculation on the long alphabetic key you are looking for, and no matter how bizarre an algorithm you used, you will calculate the same hashCode, and will be able to look up numerically with it. Of course there is always the possibility two different Strings will have the same digest hashCode. However, even then, all is not lost; it greatly narrows down the search, hence speeding it up. A Hashtable goes a step further, scrunching down the hashCode even further to an even smaller number that it can use to directly index an array, usually by dividing it by some (ideally prime) number and taking the remainder.

HashCode Misconceptions

String.hashCode Implementation

In JDK (Java Development Kit) 1.0+ and 1.1+ the hashCode function for long Strings worked by sampling every nth character. This pretty well guaranteed you would have many Strings hashing to the same value, thus slowing down Hashtable lookup. In Java version 1.2 the function has been improved to multiply the result so far by 31 then add the next character in sequence. This is a little slower, but is much better at avoiding collisions.

Object.hashCode Implementation

The default hashCode() method uses the 32-bit internal JVM (Java Virtual Machine) address of the Object as its hashCode. However, if the Object is moved in memory during garbage collection, the hashCode stays constant. This default hashCode is not very useful, since to look up an Object in a HashMap, you need the exact same key Object by which the key/value pair was originally filed. Normally, when you go to look up, you don’t have the original key Object itself, just some data for a key. So, unless your key is a String, nearly always you will need to implement a hashCode and equals method on your key class. Object.hashCode in a native method.

The Gemini Twins: equals and hashCode

Equal hashCodes in general are not sufficient to ensure Object equality. However, if the hashCodes are not equal, you know the Objects can’t possibly be equal. Consider how many 50-character Strings there are (65535^50) and how many possible hashCodes there are (2^32). It should be obvious there are way more Strings than hashCodes. So the same hashCode has to be reused over and over for different Strings.

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:

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

Let us say you hand three ints in your Object. field1 had a range 0..99, field2 had a range -10..+10 and field3 has a range 100..1000 you could pack them into a unique, dense hashCode like this: The formula would be:

Calculating Aggregate hashCodes with XOR (exclusive OR)

The xor ^ operator is useful in computing hashing functions. To create a hashCode based on two fields, compute the hashCodes of the two fields separately and xor them together with the ^ operator. To create an hash on all the elements of an array you could xor all the values together. The result independent of the order. If you want the order to matter, use some digest function. xor also has the odd properly that if you have a pair of identical hashCodes xored together, it is as if they were not there. When you are expecting duplicates, you might want to use some other combining technique.

XOR has the following nice properties:

The nasty properties of XOR are: Here is another approach that would work better if you had two Strings in your Object. It gives a different hash code for your two Objects when:
// object1 has
o1.string1 = "apple";
o1.string2 = "orange";
// and object2 has
o2.string1 = "orange";
o2.string2 = "apple";
It works like this to combine hash codes of the fields in your object:

Here is how to write a hashCode to combine fields:

Here is roughly how String.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.

Consider using an CRC-32 or an Adlerian digest for your hashCode when you can reduce the key part of your Object to a long string of bytes. This give a nice even spread over the range of possible integers.

Tips

When Do You Need A Custom equals and hashCode?

The hashCode method only gets invoked when you use the Object as the key to a Hashtable. It is not used when the Object is merely a Hashtable value. Most of the time your Hashtable keys are simple Strings, so you rarely need to write custom equals and hashCode methods. When you use a HashSet to help you check for duplicate Objects, then you likely will need a custom equals and hashCode method. There your Objects act as both key and value.

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

The One Key Catch

You can define only one hashCode/equals method for your HashSet Objects. That limits you to one type of HashSet lookup for your Objects. There is no equivalent to Comparator for HashSets. You can look up your Objects by only one key, though that key might contain several fields. You can’t have several HashSets each accessing the same Objects by different keys. You can of course have several HashSets each accessing a different subset of the same group of Objects using the same key.

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.

Learning More

Oracle’s Javadoc on Object.hashCode() : available:
Oracle’s Javadoc on Object.equals( Object ) : available:
Oracle’s Javadoc on Arrays.hashCode() : available:
Oracle’s Javadoc on Arrays.deepHashCode() : available:
Oracle’s Javadoc on System.identityHashCode : available:

This page is posted
on the web at:

http://mindprod.com/jgloss/hashcode.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

J:\mindprod\jgloss\hashcode.html
logo
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.
Blog
IP:[65.110.21.43]
Your face IP:[54.83.224.203]
You are visitor number