Gibt es eine String-Hash-Funktion, die unterstützt h (x) + h (y) = h (x + y)

Question

Ich versuche Platz zu sparen, indem Sie Hash-Werte von Zeichenfolgen. Ich habe eine sehr spezifische Anforderung, deren vereinfachte Beschreibung wie folgt lautet:

Ich habe zwei Sätze von Zeichenfolgenwerten und einen Wert wird in der Laufzeit bereitgestellt. Ich muss eine Liste aller Zeichenfolgen aus der zweiten Menge abrufen, die mit einer Zeichenfolge aus der ersten Menge beginnt und mit dem Abfragewert endet. Hier ist eine deutlich vereinfachte Darstellung und Beschreibung:

set1: 
my_test_val_1 
my_test_val_2 

set2: 
my_test_val_1_extended_to_another_value 
my_test_val_2_extended_as_well 

Mein Ziel Hash-Werte dieser Sätze wie in zu halten ist:

set1: 
hash(my_test_val_1) 
... 

set2: 
hash(my_test_val_1_extended_to_another_value) 

auf Platz zu sparen und wenn ‚_extended_to_another_value‘ kommt als Abfrage, verwenden, um die Hash-Funktion mit distributive Eigenschaft über zusätzlich zu tun:

hash(my_test_val_1) + hash('_extended_to_another_value') = hash_value_to_search 

Meine Suche versucht, eine Hash-Funktion zu finden, das diese Eigenschaft unterstützt hat die meisten p gescheitert robably aufgrund nicht die richtigen Keywords für die Suche verwendet wird, so dass selbst wenn Sie die richtigen Bedingungen für das, was beschreiben kann ich oben bin zu beschreiben, wäre es

Answer 1

Hier helfen ist ein:

import java.util.Random; 
public class StringHasher { 
    private static int[] CHAR_HASHES = new int[65536]; 
    static { 
     Random rng = new Random(); 
     for(int k = 0; k < 65536; k++) 
      CHAR_HASHES[k] = rng.nextInt(); 
    } 
    public static int hash(String s) { 
     int result = 0; 
     for(int k = 0; k < s.length(); k++) { 
      result += CHAR_HASHES[s.charAt(k)]; 
     } 
     return result; 
    } 
} 

Es stellt sich heraus, dass Ein solcher Hash muss durch das Addieren aller Hashes der Zeichenketten der Zeichenkette konstruiert werden - andernfalls würde zum Beispiel h("hello") = h("h") + h("e") + h("l") + h("l") + h("o") nicht halten.

Hinweis: Dies bedeutet, dass Sie keinen sehr kollisionsresistenten Hash haben können, da jeder String, der die gleichen Zeichen enthält, den gleichen Hash hat, wie im vorherigen Absatz.

Die Auswahl zufälliger Werte für den Hash jeder einzelnen Zeichenkette sollte im Durchschnitt die bestmögliche Kollisionsresistenz liefern. Dies kostet 256 KiB Speicher und ist nicht die schnellste mögliche Methode und nicht wiederholbar, aber es reicht für einen Proof-of-Concept.

Answer 2

Sie können einige der Mainstream-Hash-Algorithmen verwenden und versuchen, sie mit Online-Datenbanken zu hacken. Wenn x und y kurz genug sind, könnten Sie es in den MD5- oder SHA-Online-Cracked-Hashes-Datenbanken finden, und wenn Sie es entschlüsseln, können Sie mit Ihrem Algorithmus fortfahren.

Wenn Ihre Anwendung online ist, könnte sie diesen Ansatz verwenden. Der Nachteil ist, dass Sie in einigen Fällen einen falschen Wert bekommen, der denselben Hash-Code wie der richtige hat, aber die Wahrscheinlichkeit dafür ist ziemlich niedrig.

Dies ist im Grunde ein Hack, aber Sie tun diese Art von Sachen mit Ihrer Anforderung, so dass es für Sie akzeptabel sein könnte. Hier

ist ein Beispiel für Online-Hash-Datenbanken:

• http://www.md5online.org/
• http://www.dehashme.com/