C++: Vorschläge über eine Hash-Funktion für eine Folge von Strings in dem die Reihenfolge der Saiten irrelevant ist

Question

Angenommen, Sie haben diese beiden Sequenzen von Strings

abc cba bc

bc abc cba

Ich versuche, um ein Mapping für solche Sequenzen zu erzeugen (die Sequenz ist auch eine Zeichenkette), so dass die obigen zwei Sequenzen in den gleichen Bucket abgebildet werden.

Mein erster Gedanke wäre, die Ergebnisse einer Hash-Funktion hinzuzufügen, die auf jeden String separat angewendet wird. Auf diese Weise spielt ihre Reihenfolge keine Rolle. Wenn ich die Hashfunktion auf den Sequenzstring als Ganzes anwenden würde, wäre das Hashergebnis natürlich anders.

Allerdings bin ich sehr neu in der Welt der String Hashing-Funktionen und ich habe keine Ahnung, ob dieser Ansatz effizient wäre.

In dieser Website http://www.partow.net/programming/hashfunctions/index.html

ich viele verschiedene Implementierungen für String Hashing gefunden, aber ich bin nicht sicher, welche wäre die „beste“ für meine Bedürfnisse sein.

Einige technische Details zu jeder Zeichenfolge in der Sequenz bestehen darin, dass jede von ihnen nicht mehr als 25 Zeichen enthält. Außerdem hat jede Sequenz nicht mehr als 3 Strings.

Fragen

1. würde dieser Ansatz zu jeder Zeichenfolge der Sequenz arbeiten, um die Ergebnisse einer Zeichenfolge Hashing-Funktion hinzuzufügen?

2. Wenn ja, welche String Hashing-Funktion sollte ich verwenden, die eine geringe Anzahl von Kollisionen geben und auch zeitsparend sein würde?

Danke im Voraus

Answer 1

Gerade die Idee Demonstration (sehr ineffizient String Kopieren), die Komplexität O (NlogN) wobei N die Größe des Schlüssels (=== O (1), wenn haben Sie Ihre Schlüssel konstante Länge zum Zeitpunkt der Kompilierung bekannt ist), ich glaube nicht, dass Sie besser Komplexität tun können:

#include <boost/functional/hash.hpp> 
#include <set> 
#include <algorithm> 

std::size_t make_hash(
    std::string const& a, 
    std::string const& b, 
    std::string const& c) 
{ 
    std::string input[] = {a,b,c}; 
    std::sort(input, input + (sizeof(input)/sizeof(*input))); 
    return boost::hash_range(input, input + (sizeof(input)/sizeof(*input))); 
} 

#include <iostream> 
// g++ -I.../boost_1_47_0 string_set_hash.cpp 
int main() 
{ 
    std::cout << make_hash("abc", "bcd", "def") << std::endl; // 46247451276990640 
    std::cout << make_hash("bcd", "def", "abc") << std::endl; // 46247451276990640 
} 

Ein Fragment von boost/funktional/hash.hpp Referenz:

template <class T> 
inline void hash_combine(std::size_t& seed, T const& v) 

{ 
    boost::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

template <class It> 
inline std::size_t hash_range(It first, It last) 
{ 
    std::size_t seed = 0; 

    for(; first != last; ++first) 
    { 
     hash_combine(seed, *first); 
    } 

    return seed; 
} 

Answer 2

Was auch immer Hashing functio n Sie wählen, Sie wollen ein Operator für die endgültige Kombination jedes einzelnen Hash das wäre:

• commutative
• assoziativen

die Summe, das Produkt und die exklusive oder in den Sinn kommen als Kandidaten für integrale Werte. Also ja, Hinzufügen würde funktionieren. Sie würden immer noch Kollisionen mit nicht verwandten Sequenzen haben, die aufgelöst werden müssen, also würden Sie eine String-Vergleichsfunktion benötigen, aber Permutationen der gleichen Menge von Strings würden im selben Bucket landen.

Sie können auch die Reihenfolge der Operationen umkehren: Fügen Sie die Zeichenfolgen zuerst zusammen (z. B.Hinzufügen von "ab" und "cba" wird ('a' + 'c') ('b' + 'b') ('\ 0' + 'a') mit Übertragsfortpflanzung für Summe oder Produkt, also ist xor vielleicht ein interessanter Kandidat) und wenden Sie dann eine Hash-Funktion an. Man könnte sogar diese beiden Operationen kombinieren, während sie durchführen (Pseudo-Code folgt):

int hash(string a, string b, string c){ 
    int r = 0, k; 
    int m = max(a.length(), max(b.length(), c.length())); 
    for (int i = 0; i < m; i++) { 
     k = (i < a.length()? a[i] : 0)^
       (i < b.length()? b[i] : 0)^
       (i < c.length()? c[i] : 0); 
     r = hash(r,k); 
    } 
    return r; 
} 

Mit hash die inkrementelle Hashing-Funktion. Ein einfacher Modulo gegen eine Primzahl, die groß genug ist (dh größer als die erwartete Größe des Bucket-Arrays) sollte für normale Zwecke in Ordnung sein. Eine ganz andere (und bessere?) Lösung ist einfach die Reihenfolge zu sortieren (3 Einträge bedeutet quasi konstante Zeit), dann eine geordnete Karte mit der Vergleichsfunktion unter Berücksichtigung der Strings als "Ziffer" einer 3-stelligen Zahl zu erstellen . Aber das ist nicht im Rahmen der Frage.

Answer 3

Ich würde jedes Element einzeln Hash.

Dann sortieren Sie diese Hashes. Sortierung 3 size_t ist schnell.

Dann Kette diese Hashes. Ihre Bibliothek verfügt möglicherweise über Hash-Kettenfunktionen oder verwendet sogar mit Überlaufumbruch.

Vermeiden Sie xor, weil xoder zwei identische Hash-Werte Null ist. Und Hash von identischen Strings ist identisch. So kann ein naives Xor zu (a,a,b) und (c,c,b) mit der gleichen Hash-Ausgabe führen, die saugt.