Finden Sie eine Kollision Zeichenfolge mit einer bestimmten Hash-Funktion

Question

ich einen String anna haben, in denen Werte von Zeichen in der Zeichenfolge sind a = 1, n = 14 (You can compute the value of other chars like (char - 96) und Hash-Funktion, die wie folgt aussieht:

int hashCode(string s) // s = "anna"; 
{ 
    k = 0; 
    for (int i = 0; i < s.length(); i++) 
     k = (7 * k + 3 * s[i]) % 61; 
    return k; 
} 

Wie kann ich einen String der Länge finden 3 Wo passiert Kollision (etwas schlaues)? Die einzige Möglichkeit, die mir in den Sinn kommt, ist k von anna zu berechnen, was 29 ist und dann irgendwie an eine andere Zeichenfolge der Länge 3 denken, die 29 ergibt.

Answer 1

Warum generieren Sie nicht einfach alle Strings der Länge 3 und berechnen ihre Hashes (tatsächlich können Sie aufhören, wenn alle 61 möglichen Werte von Hash-Funktionen erreicht werden können)? Die Anzahl der Optionen ist nicht zu groß.

Eine mögliche Optimierung: Wenn Sie mehrere Abfragen beantworten müssen (z. B. eine Zeichenfolge geben, eine Zeichenfolge der Länge 3 mit dem gleichen Wert der Hash-Funktion suchen), können Sie alle Zeichenfolgen der Länge 3 generieren und ihre Hashes berechnen um eine Karte zu erstellen hash -> a string of length 3 with this hash. Sobald Sie diese Map haben, ist die Suche nach einer Zeichenkette der Länge 3 mit dem gleichen Hash wie die angegebene Map nur eine Suche nach einer Map.