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"