C++: suggerimenti su una funzione hash per una sequenza di stringhe in cui l'ordine delle corde è irrilevante

Question

Diciamo che avete questi due sequenze di stringhe

abc cba bc

bc abc cba

sto cercando per creare una mappatura per tali sequenze (la sequenza è anche una stringa) in modo che le due sequenze di cui sopra siano mappate nello stesso bucket.

Il mio primo pensiero sarebbe quello di aggiungere i risultati di una funzione di hashing che viene applicata a ciascuna stringa separatamente. In questo modo il loro ordine non ha importanza. Se avessi applicato la funzione di hashing alla stringa di sequenza nel suo complesso, allora ovviamente il risultato dell'hash sarebbe diverso.

Tuttavia, sono molto nuovo nel mondo delle funzioni di hashing delle stringhe e non ho idea se questo approccio sarebbe efficiente.

In questo sito http://www.partow.net/programming/hashfunctions/index.html

ho trovato molte implementazioni diverse per l'hashing della stringa, ma non sono sicuro quale sarebbe il "migliore" per le mie esigenze.

Alcuni dettagli tecnici su ciascuna stringa nella sequenza sono che ognuno di essi non avrà più di 25 caratteri. Inoltre, ciascuna sequenza non avrà più di 3 stringhe.

Domande

1. Sarebbe questo approccio di aggiungere i risultati di una funzione di hashing stringa per ciascuna stringa del lavoro successione?

2. In caso affermativo, quale funzione di hashing dello stringhe dovrei usare per ottenere una bassa quantità di collisioni ed essere anche efficiente nel tempo?

Grazie in anticipo

Answer 1

Solo l'idea di dimostrazione (molto inefficiente stringa di copia), la complessità O (N log N) dove N è la dimensione della chiave (=== O (1) se le chiavi hanno lunghezza costante noto al momento della compilazione), non credo che si può fare meglio la complessità:

#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 
} 

Un frammento di boost/funzionale/hash.hpp per riferimento:

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

Qualunque sia hashing functio n si sceglie, si vuole un operatore per la combinazione finale di ogni singolo hash, che sarebbe:

• commutativa
• associativa

la somma, il prodotto, e l'esclusiva o venire in mente come candidati per i valori integrali. Quindi sì, l'aggiunta funzionerebbe. Avresti comunque delle collisioni su sequenze non correlate che devono essere risolte, quindi avresti bisogno di una funzione di confronto delle stringhe, ma le permutazioni dello stesso insieme di stringhe finirebbero nello stesso bucket.

È inoltre possibile invertire l'ordine di operazione: aggiungere prima le stringhe in base al carattere (ad es.aggiungendo "ab" e "cba" diventa ('a' + 'c') ('b' + 'b') ('\ 0' + 'a') con propagazione di carry per somma o prodotto, quindi forse xor è un candidato interessante qui), e quindi applicare una funzione di hash. Si potrebbe anche combinare queste due operazioni durante l'esecuzione di loro (pseudo codice segue):

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; 
} 

Con hash la funzione di hashing incrementale. Un semplice modulo contro un numero primo abbastanza grande (cioè maggiore della dimensione prevista dell'array di benne) dovrebbe andar bene per scopi normali.

Una soluzione completamente diversa (e migliore?) È semplicemente ordinare la sequenza (3 voci significa tempo quasi costante), quindi creare una mappa ordinata con la funzione di confronto considerando le stringhe come una "cifra" di un numero di 3 cifre . Ma questo è fuori dalla portata della domanda.

Answer 3

Vorrei eliminare ogni elemento singolarmente.

Quindi ordinare gli hash. L'ordinamento 3 size_t è veloce.

Quindi incatenare questi hash. La tua libreria potrebbe avere funzioni a catena hash, o addirittura usare hash(a+b+c) con un overflow.

Evitare xor, perché xo due valori hash identici è zero. E l'hash di stringhe identiche è identico. Quindi un ingenuo xor può portare a (a,a,b) e (c,c,b) con lo stesso output hash, che fa schifo.