La prevención de llaves de diferentes valores hash de aterrizar en el mismo cubo con unordered_set

Question

Esto podría ser una pregunta tonta, pero aquí va:

hash un diccionario de palabras en una tabla hash basado unordered_set. Mi función hash se hizo intencionalmente "malo", en el que todas las cadenas que contenían el mismo conjunto de letras hash en el mismo valor. Inicialmente trató de pasar por encima de la conducta normal función hash, y utilizar un "histograma de frecuencias" de las letras de cada palabra como un valor hash (que supe era imposible :)), pero uno de los hilos sugirió el uso de un 26- bits de máscara de bits para lograr el mismo. La función hash funciona bien y dandy hasta el momento.

Por ejemplo, en mi esquema, -CITIED y el hash citado para el mismo valor, 1049144. Mi idea era que dado un conjunto de letras, que quería encontrar todas las palabras que contienen las letras de ese conjunto.

Supongo que no he entendido bien el concepto de hash (o mi código es incorrecto normal), ya que no puedo explicar el comportamiento que me encontré:
Me decidí a buscar todas las palabras que consistía en cartas de la cadena "LIVEN". Mi salida (con clave hash) fue la siguiente:

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

¿Cómo diablos lo hizo una reverencia tierra hasta allí? Como se puede ver, tiene un valor hash diferente de las tres palabras restantes. ¿Dónde está la falla con mi / aplicación comprensión de la tabla hash?

El código que produce por encima de la salida:

    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

Los diferentes valores hash no necesariamente terminan en diferentes cubos. En general, una tabla hash elegirá un cubo basado en hash_value % number_of_buckets, por lo que los hashes que son iguales en módulo el número de cubetas va a acabar en el mismo cubo.

En esencia, no se puede garantizar nada sobre el cual aparece valor hash en el cual cubo.

Answer 2

Creo que también tiene un fallo potencial en el my_string_equality ... no lo que desea es utilizar el std::string::operator==() regular? Que sabemos, se debe hacer una comparación de los valores de los objetos reales, no una comparación de su almohadilla (el contenedor ya se conoce el valor de hash, sólo podría llamar my_string_hash_function y comparar los resultados si eso era lo que tenía que hacer).