Hashcode Caching by String

Tweet

Caching the hashcode of an object is very useful in operations where it needs to be calculated frequently. It avoids the recalculation of hashcode again and again and thus increase application performance.

One such operation where hashcode caching is very useful is using an object as a key in maps like HashMap.

Strings are frequently used as keys in maps so it is a best case for caching the hashcode. String class has a built-in hashcode caching mechanism.

According to Java API Docs the hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.) 

It shows that hashcode of a String object depends on its contents.

Now for caching the hashcode for an object whose hashcode depends on its contents, it is necessary for that object to be [immutable]. Otherwise when contents of that object would be changed then hashcode also get changed. Thus caching of hashcode of a such mutable object is of no use. Since strings in Java are immutable we can cache its hashcode.

If you look ito the source code of String class, you will find following definition of hashCode() method :

  1494       public int hashCode() {
 1495           int h = hash;
 1496           if (h == 0 && count > 0) {
 1497               int off = offset;
 1498               char val[] = value;
 1499               int len = count;
 1500  
 1501               for (int i = 0; i < len; i++) {
 1502                   h = 31*h + val[off++];
 1503               }
 1504               hash = h;
 1505           }
 1506           return h;
 1507       }

At  line  1495, you will see

  int h = hash;

Here variable h is assigned to a variable hash. This variable hash is used to store the haschode for a String object. hash variable is defined at line 122 as:

    122       /** Cache the hash code for the string */
  123       private int hash; // Default to 0

Hashcode for strings are cached on per object basis i.e each String object's hashcode is stored in this private variable hash.

Whenever hashCode() method of String class is called, the value of variable hash is checked whether it is 0 or not as indiated by line 1495 and 1496. Variable hash equals to 0 means that hashcode() method is being called first time and hashcode has not been calculated yet.

If hash is equals to 0, only then hashcode for correspoding String object is calculated and cached in variable hash as shown in line 1504.

So when the next time hashCode() for the same String object  is called, value of hash does not come out to be 0 and hashcode is not recalcuated but is reused as stored in variable hash.

I would like to know your comments and if you liked the article then please share it on social networking buttons.

Tweet