Here's code to find and print strings of any desired hashCode
value:
public static int findIntInverse(int x) {
// find the number y such that as an int (after overflow) x*y = 1
// assumes x is odd, because without that it isn't possible.
// works by computing x ** ((2 ** 32) - 1)
int retval = 1;
for (int i = 0; i < 31; i++) {
retval *= retval;
retval *= x;
}
return retval;
}
public static void findStrings(
int targetHash,
Iterable<String> firstParts,
Iterable<String> midParts,
Iterable<String> lastParts) {
Map<Integer, String> firstHashes = new HashMap<>();
for (String firstPart : firstParts) {
firstHashes.put(firstPart.hashCode(), firstPart);
}
int maxlastlen = 0;
int maxmidlen = 0;
for (String midPart : midParts) {
maxmidlen = Math.max(midPart.length(), maxmidlen);
}
for (String lastPart : lastParts) {
maxlastlen = Math.max(lastPart.length(), maxlastlen);
}
List<Integer> hashmuls = new ArrayList<>();
String baseStr = "\u0001";
for (int i = 0; i <= maxmidlen + maxlastlen; i++) {
hashmuls.add(baseStr.hashCode());
baseStr += "\0";
}
// now change each hashmuls into its negative "reciprocal"
for (int i = 0; i < hashmuls.size(); i++) {
hashmuls.set(i, -findIntInverse(hashmuls.get(i)));
}
for (String lastPart : lastParts) {
for (String midPart : midParts) {
String tail = midPart + lastPart;
Integer target = hashmuls.get(tail.length()) * (tail.hashCode() - targetHash);
if (firstHashes.containsKey(target)) {
System.out.print(firstHashes.get(target));
System.out.println(tail);
}
}
}
}
Some interesting finds found by using a list of common English words to seed each part:
sand nearby chair
king concentration feeling
childhood dish tight
war defensive to
ear account virus
Using just Arrays.asList(" ")
as midParts
and a large English word list for firstParts
and lastParts
, we find the well-known pollinating sandboxes
as well as revolvingly admissable
, laccaic dephase
, toxity fizzes
, etc.
Note that if you give findStrings
a large list of size N for both firstParts
and lastParts
and a short fixed list for midParts
, it runs in O(N) time.