Inatteso imprevisto con std :: hash

Question

Conosco hashing numero infinito di string in 32b int deve generare collisione, ma mi aspetto che la funzione di hashing abbia una buona distribuzione.

Non è strano che queste 2 stringhe abbiano lo stesso hash?

size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
//hash0 == hash1 

So che posso usare boost::hash<std::string> o altri, ma voglio sapere che cosa è sbagliato con std::hash. Sto usando male? Non dovrei in qualche modo "seminarlo"?

Answer 1

Non c'è niente di sbagliato con l'utilizzo di std::hash. Il problema è che la specializzazione fornita dall'implementazione della libreria standard in bundle con Visual Studio 2010 richiede solo un sottoinsieme dei caratteri della stringa per determinare il valore hash (presumibilmente per motivi di prestazioni). Per coincidenza, l'ultimo carattere di una stringa con 14 caratteri non fa parte di questo set, motivo per cui entrambe le stringhe producono lo stesso valore di hash.

Per quanto ne so questo comportamento è conforme allo standard, il quale richiede solo che più chiamate alla funzione di hash con lo stesso argomento devono sempre restituire lo stesso valore. Tuttavia, la probabilità di una collisione di hash dovrebbe essere minima. L'implementazione VS2010 soddisfa la parte obbligatoria, ma non tiene conto di quella opzionale.

Per i dettagli, vedere l'implementazione nel file di intestazione xfunctional (a partire dalla riga 869 nella mia copia) e §17.6.3.4 dello standard C++ (latest public draft).

Se è assolutamente necessaria una funzione di hash migliore per le stringhe, è necessario implementarla autonomamente. In realtà è not that hard.

Answer 2

Non si esegue il seeding della funzione di hashing, è possibile solo "saltarli" al massimo.

La funzione è utilizzata nel modo giusto e questa collisione potrebbe essere solo fortuita.

Non è possibile stabilire se la funzione di hashing non è distribuita uniformemente a meno che non si esegua un test massivo con chiavi casuali.

Answer 3

La funzione di hash TR1 e lo standard più recente definiscono sovraccarichi appropriati per cose come le stringhe. Quando eseguo questo codice utilizzando std :: tr1 :: hash (g ++ 4.1.2), ottengo diversi valori hash per queste due stringhe.

Answer 4

Probabilmente è necessario ottenere valori hash diversi. Ottengo diversi valori di hash (GCC 4.5):

hashtest.cpp

#include <string> 
#include <iostream> 
#include <functional> 
int main(int argc, char** argv) 
{ 
size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n"; 
return 0; 
} 

uscita

# g++ hashtest.cpp -o hashtest -std=gnu++0x 
# ./hashtest 
16797002355621538189 != 16797001256109909978 

Answer 5

L'algoritmo di hash esatto non è specificato dallo standard, pertanto i risultati variano. L'algoritmo utilizzato da VC10 non sembra prendere in considerazione tutti i caratteri se la stringa è più lunga di 10 caratteri; it anticipi con un incremento di 1 + s.size()/10. Questo è legale, sebbene da un punto di vista di QoI, piuttosto deludente; tali codici hash sono noti per prestazioni molto scarse per alcuni set di dati tipici (come gli URL ).Mi piacerebbe vivamente di sostituirlo con uno un hash FNV o una basata su un primo di Mersenne:

FNV hash:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = (16777619 * result) 
        ^static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

Mersenne Prime hash:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = 127 * result 
        + static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

(La FNV l'hash è presumibilmente migliore, ma l'hash prime Mersenne sarà più veloce su molte macchine, perché moltiplicare per 127 è spesso molto più veloce della moltiplicazione per 2166136261.)