Formula

This method computes the hash code for a String. The hash code for a String object is calculated as:

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

In this formula:

  • s[i] denotes the ith character of the String (using zero-based indexing).
  • n is the length of the String.
  • ^ denotes exponentiation.

Using integer arithmetic, the Java hashCode() method iterates over each character of the String and calculates the hash value. For an empty string, the hash code is defined to be 0.

Formula in integer arithmetic

The implementation uses integer arithmetic to avoid potential overflow issues by utilizing a prime number 31 in the calculation, which tends to provide a better distribution of hash values. The final formula looks like this using integer arithmetic:

hash = 31 * hash + s[i]

- for each character `s[i]` in the string.

Breakdown of the Formula

Here’s a step-by-step explanation of how the hash code is computed for the string “hello”:

  • Characters: h = 104, e = 101, l = 108, l = 108, o = 111
  • Length (n): 5

Using the formula:

hash = 31^(4) * 'h' + 31^(3) * 'e' + 31^(2) * 'l' + 31^(1) * 'l' + 31^(0) * 'o'
    = 31^4 * 104 + 31^3 * 101 + 31^2 * 108 + 31^1 * 108 + 31^0 * 111
    = 923521 * 104 + 29791 * 101 + 961 * 108 + 31 * 108 + 1 * 111
    = 96042064 + 3007091 + 103788 + 3348 + 111
    = 99253161

The hash code for the string “hello” is computed as hash = 99253161.

Implementation of hashCode() in Java String class

public int hashCode() {
    int h = 0;
    int n = length();
    for (int i = 0; i < n; i++) {
        h = 31 * h + charAt(i);
    }
    return h;
}
  • h starts at 0.
  • It iterates through each character of the string, multiplying the current hash by 31 and adding the ASCII value of the character.

Example Usage

 import java.io.*;
 
 public class Test {
     public static void main(String args[]) {
         String Str = "Welcome to k5kc.com";
         System.out.println("Hash code for \"" + str + "\": " + str.hashCode());
     }
 }

Explanation:

  • A string "Welcome to k5kc.com" is created.
  • The hashCode() method is called on this string.
  • The hash code is printed.

Summary

The hashCode() method in Java’s String class uses a precise and efficient algorithm to compute a hash value based on the prime number 31. This helps in achieving a good distribution of hash values, thereby minimizing collisions in hash-based collections like HashMap and HashSet.

This method is both efficient and effective, ensuring that Java developers can trust the hashCode() method to provide consistent and well-distributed hash values for strings.