Valore hash per una std :: unordered_map

Question

Secondo lo standard non è disponibile alcun supporto per i contenitori (per non dire quelli non ordinati) nella classe std::hash. Quindi mi chiedo come implementarlo. Quello che ho è:

std::unordered_map<std::wstring, std::wstring> _properties; 
std::wstring _class; 

ho pensato di iterazione le voci, calcolando i singoli hash per chiavi e valori (via std::hash<std::wstring>) e concatenare i risultati in qualche modo.

Quale sarebbe un buon modo per farlo e ha importanza se l'ordine nella mappa non è definito?

Nota: non desidero utilizzare boost.

Un semplice XOR è stato suggerito, quindi sarebbe come questo:

size_t MyClass::GetHashCode() 
{ 
    std::hash<std::wstring> stringHash; 
    size_t mapHash = 0; 
    for (auto property : _properties) 
    mapHash ^= stringHash(property.first)^stringHash(property.second); 

    return ((_class.empty() ? 0 : stringHash(_class)) * 397)^mapHash; 
} 

?

Sono davvero insicuro se questo semplice XOR è sufficiente.

Answer 1

risposta

Se per sufficiente, è dire se la vostra funzione è iniettiva, la risposta è No. Il ragionamento è che l'insieme di tutte hash rispetta la tua funzione di uscita può ha cardinalità 2^64, mentre il lo spazio dei tuoi ingressi è molto più grande. Tuttavia, questo non è veramente importante, perché non è possibile avere una funzione hash iniettiva data la natura dei tuoi input. Una buona funzione hash ha queste qualità:

• Non è facilmente invertibile. Dato l'output k, non è calcolabile fattibile nel corso della vita dell'universo per trovare m tale che h (m) = k.
• L'intervallo è distribuito uniformemente nello spazio di uscita.
• E 'difficile trovare due ingressi M e M 'tale che h (m) = h (m')

Naturalmente, le estensioni di questi davvero variano a seconda che si desidera qualcosa che è crittograficamente sicuro, o vuoi prendere qualche pezzo di dati arbitrario e semplicemente inviarlo un numero arbitrario a 64 bit. Se vuoi qualcosa di crittograficamente sicuro, scriverlo da solo non è una buona idea. In tal caso, avrai anche bisogno della garanzia che la funzione sia sensibile alle piccole modifiche nell'input. L'oggetto funzione std::hash non è richiesto per essere crittograficamente sicuro. Esiste per casi d'uso isomorfi alle tabelle hash. CPP Rerefence dice:

Per due parametri diversi k1 e k2 che non sono uguali, la probabilità che std::hash<Key>()(k1) == std::hash<Key>()(k2) dovrebbe essere molto piccola, si avvicina 1.0/std::numeric_limits<size_t>::max().

Mostrerò qui sotto come la vostra attuale soluzione non garantisce questo.

collisioni

ti darò alcune delle mie osservazioni su una variante della soluzione (non so che cosa il vostro membro _class è).

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) { 
    std::hash<std::string> h; 
    std::size_t result = 0; 
    for (auto&& p : m) { 
     result ^= h(p.first)^h(p.second); 
    } 
    return result; 
} 

È facile generare collisioni.Considerate le seguenti mappe:

std::unordered_map<std::string, std::string> container0; 
std::unordered_map<std::string, std::string> container1; 
container0["123"] = "456"; 
container1["456"] = "123"; 
std::cout << hash_code(container0) << '\n'; 
std::cout << hash_code(container1) << '\n'; 

Sulla mia macchina, la compilazione con g ++ 4.9.1, questo uscite:

1225586629984767119 
1225586629984767119 

La questione se questo importa o no si pone. Ciò che è rilevante è la frequenza con cui si avranno mappe in cui le chiavi e i valori sono invertiti. Queste collisioni si verificano tra due mappe in cui gli insiemi di chiavi e valori sono gli stessi.

ordine di iterazione

Due unordered_map istanze aventi esattamente le stesse coppie di valori-chiave non avranno necessariamente lo stesso ordine di iterazione. CPP Rerefence dice:

Per due parametri k1 e k2 che sono uguali, std::hash<Key>()(k1) == std::hash<Key>()(k2).

Questo è un requisito banale per una funzione hash. La tua soluzione evita questo perché l'ordine di iterazione non ha importanza dal momento che XOR è commutativo.

una possibile soluzione

Se non avete bisogno di qualcosa che è crittograficamente sicuro, è possibile modificare la soluzione un po 'di uccidere la simmetria. Questo approccio va bene nella pratica per tabelle hash e simili. Questa soluzione è anche indipendente dal fatto che l'ordine in un unordered_map non è definito. Utilizza la stessa proprietà utilizzata dalla soluzione (Commutatività di XOR).

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) { 
    const std::size_t prime = 19937; 
    std::hash<std::string> h; 
    std::size_t result = 0; 
    for (auto&& p : m) { 
     result ^= prime*h(p.first) + h(p.second); 
    } 
    return result; 
} 

Tutto ciò che serve in una funzione di hash in questo caso è un modo per mappare una coppia chiave-valore a un buon valore hash arbitrario, e un modo per combinare gli hash delle coppie chiave-valore utilizzando un commutativa operazione. In questo modo, l'ordine non ha importanza. Nell'esempio hash_code ho scritto, il valore hash della coppia valore-chiave è solo una combinazione lineare dell'hash della chiave e dell'hash del valore. Puoi costruire qualcosa di un po 'più complicato, ma non ce n'è bisogno.