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