Java uses a rolling hash that should work for you
From java.lang.String
:
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
The idea is to calculate the hash as :
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
To deal with overflow, you can add a step where the hash is checked against 18446744073709551615
and if it is larger take the mod
of the hash and 18446744073709551615
.