Prévention des clés de différentes valeurs de hachage de se poser dans le même seau avec unordered_set

Question

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

Je haché un dictionnaire de mots dans un hachage table à base unordered_set. Ma fonction de hachage a été fait intentionnellement « mauvais » dans la mesure où toutes les chaînes qui contiennent le même ensemble de lettres serait hachage à la même valeur. J'ai d'abord essayé de l'emporter sur le comportement de la fonction de hachage normale, et utiliser un « histogramme de fréquence » des lettres de chaque mot comme une valeur de hachage (que j'ai appris était impossible :)), mais l'un des fils a suggéré d'utiliser un 26- bit bitmask pour obtenir le même. La fonction de hachage fonctionne très bien et dandy jusqu'à présent.

Par exemple, dans mon schéma, CITIED et hachage CITÉS à la même valeur, 1049144. Mon idée était donné une série de lettres, je voulais trouver tous les mots contenant des lettres de cet ensemble.

Je devine que je ne l'ai pas bien compris le concept de hachage (ou mon code est simplement faux), que je ne peux pas expliquer tout à fait le comportement que je rencontrais:
J'ai décidé de chercher tous les mots qui se composait de lettres de la chaîne « LIVEN ». Ma sortie (avec la clé de hachage) se présente comme suit:

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

Comment avez la terre là-bas fit la révérence? Comme on peut le voir, il a une valeur de hachage différent des trois autres mots. D'où vient le mensonge de défaut avec ma mise en œuvre de / compréhension 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 

My hash function :

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

Comparison function :

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

Les différentes valeurs de hachage se termine pas nécessairement dans des seaux différents. En général, une table de hachage choisira un seau en fonction de hash_value % number_of_buckets, de sorte hash qui sont égales modulo le nombre de godets se vent dans le même seau.

Pour l'essentiel, vous ne pouvez pas quoi que ce soit de garantie dont la valeur de hachage apparaît dans laquelle seau.

Answer 2

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