Hash

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

Hash

C++

std::hash

Python

Python's hash is randomized, the hash value stays the same in one process, but will change in another invocation.

>>> hash("asdf")
-6638445151105855253
>>> hash("asdf")
-6638445151105855253

# Restart

>>> hash("asdf")
5905973160914177863

Java

Integer.valueOf(value.hashCode());

Message Digest

Read more about crypto hash function here

Python

>>> hashlib.md5(b"hello").hexdigest()
'5d41402abc4b2a76b9719d911017c592'

Java

jshell> import java.security.MessageDigest

jshell> MessageDigest md = MessageDigest.getInstance("MD5")
md ==> MD5 Message Digest from SUN, <initialized>

Get digest as byte array:

jshell> byte[] a = md.digest("hello".getBytes())
a ==> byte[16] { 93, 65, 64, 42, -68, 75, 42, 118, -71, ...  -111, 16, 23, -59, -110 }

Convert the byte array to Hex String:

jshell> IntStream.range(0, a.length).mapToObj(i -> String.format("%02X", a[i])).collect(Collectors.joining())
$40 ==> "5D41402ABC4B2A76B9719D911017C592"