Hash

Last Updated: 2021-12-15

Java source code to calculate the hash of a string:

// Source code: String.java
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Tests:

System.out.print("a".hashCode());
//97

System.out.print("aa".hashCode());
//3104 = 31*97 + 97

System.out.print("abc".hashCode());
// 96354 = 31 * 31 * 97 + 31 * 98 + 99

And it may be negative:

System.out.print("abcdefghijklmnopqrstuvwxy".hashCode());
//-1908758419

Resolve Collision

closed and open hashing

• Linear Probing
• Quadratic probing is an open addressing scheme in computer programming for resolving collisions in hash tables
• LinkedList

Others

• Consistent Hashing: https://en.wikipedia.org/wiki/Consistent_hashing
• Rendezvous Hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing