Verhindern Tasten verschiedenen Hashwerte von in gleichen Eimern mit unordered_set Landung

Question

Dies könnte eine dumme Frage, aber hier geht:

gehasht ein Wörterbuch von Wörtern in eine unordered_set basierten Hash-Tabelle. Meine Hash-Funktion wurde absichtlich „schlecht“ gemacht, dass alle Zeichenfolgen, die den gleichen Satz von Briefen auf den gleichen Wert Hash würde. Ich versuchte, zunächst auf das normale Hashfunktion Verhalten over-ride, und ein „Frequenzhistogramm“ der Buchstaben in jedem Wort als ein Hash-Wert verwendet werden (was ich gelernt war unmöglich :)), aber einer der Fäden vorgeschlagen eine Verwendung 26- Bit Bitmaske das gleiche zu erreichen. Die Hash-Funktion funktioniert gut und gut so weit.

Zum Beispiel in meinem Schema, citied und Zitierte Hash auf den gleichen Wert, 1049144. Meine Idee war, dass ein Satz von Buchstaben gegeben, ich alle der Worte mit Buchstaben von diesem Satz finden wollte.

Ich vermute, dass ich nicht ganz das Konzept des Hashing verstanden (oder mein Code ist schlicht falsch), wie ich das Verhalten nicht ganz erklären kann ich gestoßen:
Ich entschied mich für alle Wörter zu suchen, die aus der Zeichenfolge „Beleben“ von Buchstaben bestand. Mein Ausgang (mit Raute-Taste) war wie folgt:

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

Wie auf der Erde landen hat curtseyed dort oben? Wie man sehen kann, hat es einen anderen Hash-Wert aus den verbleibenden drei Worten. Wo liegt der Fehler liegt mit meinem Verständnis / Implementierung der Hash-Tabelle?

-Code der oben Ausgabe erzeugt:

    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

Verschiedene Hash-Werte nicht unbedingt in verschiedenen Eimern landen. Im allgemeinen wird eine Hash-Tabelle einen Eimer basierend auf hash_value % number_of_buckets wählen werden, so Hashes, die gleich Modulo die Anzahl der Schaufeln sind in der gleichen Eimer aufzuwickeln.

Im Wesentlichen kann man nicht garantieren, etwas über die Hash-Wert angezeigt, in dem Eimer.

Answer 2

Ich glaube, Sie haben auch einen möglichen Fehler in den my_string_equality bekommen ... Sie nicht nur den regelmäßigen std::string::operator==() verwenden? AFAIK Sie sollten einen Vergleich der tatsächlichen Objektwerte tun, kein Vergleich ihrer Hash (der Behälter bereits den Hash-Wert kennt, könnte es nur my_string_hash_function nennen und die Ergebnisse vergleichen, wenn das war, was er tun musste).