Prevenire chiavi di diversi valori di hash di atterrare in stesso secchio con unordered_set

Question

Questa potrebbe essere una domanda stupida, ma qui va:

I hash un dizionario di parole in un hash-table basata unordered_set. La mia funzione di hash è stato fatto intenzionalmente "cattivo", nel senso che tutte le stringhe che contenevano lo stesso insieme di lettere sarebbero hash allo stesso valore. Inizialmente ho cercato di over-corsa il comportamento normale funzione hash, e utilizzare un "istogramma frequenza" delle lettere di ogni parola come un valore hash (che ho imparato è impossibile :)), ma uno dei fili suggerito di utilizzare un 26- bit maschera di bit per ottenere lo stesso. La funzione di hash funziona bene e dandy finora.

Per esempio, nel mio schema, CITIED e hash citati per lo stesso valore, 1049144. La mia idea era che, dato un insieme di lettere, volevo trovare tutte le parole che contengono lettere di quel set.

sto indovinando che non ho capito bene il concetto di hashing (o il mio codice è sbagliato pianura), come non riesco a spiegare il comportamento che ho incontrato:
Ho deciso di cercare per tutte le parole che consisteva di lettere della stringa "vivacizzare". La mia uscita (con tasto cancelletto) è stato il seguente:

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

Come sulla terra ha terra ci fece un inchino in su? Come si vede, ha un valore hash differente dalle rimanenti tre parole. Dove sta la colpa con la mia implementazione / comprensione della tabella hash?

Il codice che prodotto al di sopra di uscita:

    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

Diversi valori hash non sarà necessariamente finire in diversi secchi. Generalmente una tabella hash sceglierà un secchio sulla base di hash_value % number_of_buckets, in modo hash che sono uguali modulo il numero di bucket finiranno nello stesso secchio.

In sostanza, non si può garantire nulla che appare valore hash in cui secchio.

Answer 2

Credo che hai anche avuto un potenziale bug nel my_string_equality ... non si vuole solo utilizzare il std::string::operator==() regolare? Per quanto ne so si dovrebbe fare un confronto tra i valori oggetto reale, non un confronto tra loro hash (il contenitore già conosce il valore hash, si potrebbe chiamare my_string_hash_function e confrontare i risultati se questo era quello che doveva fare).