Java hashCode()

From Wikipedia, the free encyclopedia

Each object class in the Java language provides an implementation of the hashCode() method. The output of this method is a 32-bit signed integer and the results are intended to be evenly distributed for varied inputs so as to avoid clustering when used in HashMaps and other structures that store objects in buckets based on their hashCode().

For the java.lang.String class, for instance, a hash code is computed according to the formula:

s[0] * 31^{n − 1} + s[1] * 31^{n − 2} + ... + s[n − 1]

using Java int (32-bit) arithmetic, where s[i] is the ith character of the string, and n is the length of the string.

This is not a cryptographically secure hash algorithm.

[edit] Usage in Java

The following example shows how a custom object (here named Employee) might implement the public int hashCode() method:

public class Employee{
    private int employeeId;
    private String firstName;
    private String lastName;
    private Department dept;
 
    /* other methods would be in here somewhere */
 
    public int hashCode() {
        int hash = 1;
        hash = hash * 31 + lastName.hashCode();
        hash = hash * 29 + firstName.hashCode();
        hash = hash * 17 + employeeId;
        hash = hash * 13 + (dept == null ? 0 : dept.hashCode());
        return hash;
    }
}

[edit] Sample Implementations of the Algorithm in Various Languages

[edit] In Java

NOTE: This is not the implementation of hashCode() in java.lang.String, which is overly complicated for this example. This is an example of how one might implement the algorithm as a static method.

public static int hashCode(String input) {
    int h = 0;
    int len = input.length();
    for (int i = 0; i < len; i++) {
        h = 31 * h + input.charAt(i);
    }
    return h;
}

[edit] In ActionScript (Flash)

function hashCode(string) {
    var h = 0;
    for (var i = 0; i < string.length; i++) {
        h = (((31 * h) >> 0) + string.charCodeAt(i)) >> 0;
    }
    return h;
}

NOTE: The >> operator behaves as described in the ActionScript documentation, which includes conversion of the inputs to 32-bit integers:
"Operator (bitwise); converts expression1 and expression2 to 32-bit integers, and shifts all of the bits in expression1 to the right by the number of places specified by the integer resulting from the conversion of expression2 . Bits that are shifted to the right are discarded. To preserve the sign of the original expression , the bits on the left are filled in with 0 if the most significant bit (the bit farthest to the left) of expression1 is 0, and filled in with 1 if the most significant bit is 1."