clés de différentes valeurs Prévention de hachage de l'atterrissage dans la même seau avec unordered_set

Question

Cela pourrait être une question stupide, mais voilà:

Je dictionnaire des hachés mots dans une table de hachage basée sur unordered_set. Ma fonction de hachage a été intentionnellement "mauvaise", en ce sens que toutes les chaînes contenant le même jeu de lettres auraient la même valeur. J'ai d'abord essayé de surpasser le comportement normal de la fonction de hachage, et d'utiliser un "histogramme de fréquence" des lettres dans chaque mot comme une valeur de hachage (que j'ai appris était impossible :)), mais l'un des fils suggérait bit bitmask pour atteindre le même. La fonction de hachage fonctionne bien et dandy jusqu'à présent. Par exemple, dans mon schéma, CITIED et CITED hachage à la même valeur, 1049144. Mon idée était que donné un ensemble de lettres, je voulais trouver tous les mots contenant des lettres de cet ensemble.

Je suppose que je n'ai pas encore compris le concept de hachage (ou mon code est tout à fait faux), car je ne peux pas tout à fait expliquer le comportement que j'ai rencontré:
J'ai décidé de chercher tous les mots qui consistaient de lettres de la chaîne "LIVEN". Ma sortie (avec la clé de hachage) était comme suit:

VENVILLE,4215328 
LEVIN,4215328 
ENLIVEN,4215328 
CURTSEYED,37486648 

Comment avez là la terre fit la révérence? Comme on peut le voir, il a une valeur de hachage différente des trois mots restants. Où est la faute à ma compréhension/mise en œuvre de la table de hachage?

Code qui produit ci-dessus sortie:

    typedef std::unordered_set< std::string, my_string_hash_function, my_string_equality> Dict  
    DictHash dict;  
    DictHash::const_local_iterator c_l_itr; 

    DictHash::size_type bs = dict.bucket (std::string ("LIVEN")); 
    for (c_l_itr = dict.begin(bs); c_l_itr != dict.end(bs); c_l_itr++) 
     std::cout

Ma fonction de hachage:

struct my_string_hash_function 
{ 
    std::size_t operator()(const std::string& s) const 
    { 
     unsigned long hash = 0; 
     std::string::const_iterator itr; 

     for (itr = s.begin(); itr != s.end(); itr++) 
    hash |= 2 << (*itr - int('A')); 

     return hash; 
    } 
}; 

Fonction de comparaison:

struct my_string_equality 
{ 
    bool operator()(const std::string& s1, const std::string& s2) const 
    { 
     if (s1.length() != s2.length()) 
    return false; 

     unsigned int hash1 = 0, hash2 = 0; 
     const char *str1, *str2; 
     int i,len; 

     len = s1.length(); 
     str1 = s1.c_str(); 
     str2 = s2.c_str(); 

     for (i = 0; i < len; i++) 
     { 
      hash1 |= 2 << (str1[i] - (int)'A'); 
      hash2 |= 2 << (str2[i] - (int)'A'); 
     } 

     return hash1 == hash2; 
    } 
}; 

Answer 1

différentes valeurs de hachage ne se termine pas nécessairement dans différents seaux. En règle générale, une table de hachage choisira un compartiment basé sur hash_value % number_of_buckets, donc des hachages qui sont égaux modulo le nombre de seaux se retrouvera dans le même seau. Fondamentalement, vous ne pouvez pas garantir quoi que ce soit sur la valeur de hachage qui apparaît dans quel compartiment.

Answer 2

Je pense que vous avez aussi un bug potentiel dans le my_string_equality ... vous ne voulez pas simplement utiliser le std::string::operator==() régulier? AFAIK vous devriez faire une comparaison des valeurs réelles d'objet, pas une comparaison de leur hachage (le récipient connaît déjà la valeur de hachage, il pourrait juste appeler my_string_hash_function et comparer les résultats si c'était ce qu'il devait faire).