Prevenindo as chaves de diferentes valores de hash de pousar no mesmo balde com UNODERED_SET

Question

Esta pode ser uma pergunta boba, mas aqui vai:

Eu hashi um dicionário de palavras em uma mesa de hash baseada emsed_set_set. Minha função de hash foi feita intencionalmente "ruim", na medida em que todas as cordas que continham o mesmo conjunto de letras hash com o mesmo valor. Inicialmente, tentei sobrecarregar o comportamento normal da função de hash e usar um "histograma de frequência" das letras em cada palavra como um valor de hash (que eu aprendi era impossível :)), mas um dos tópicos sugeridos usando um 26- Bit BitMask para alcançar o mesmo. A função de hash funciona bem e dândi até agora.

Por exemplo, no meu esquema, citou e citou o hash pelo mesmo valor, 1049144. Minha idéia era que, dado um conjunto de letras, eu queria encontrar todas as palavras que contêm letras desse conjunto.

Suponho que não entendi bastante o conceito de hash (ou meu código está completamente errado), pois não consigo explicar o comportamento que encontrei:
Decidi procurar todas as palavras que consistiam em letras da string "Liven". Minha saída (com a chave de hash) foi a seguinte:

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

Como diabos o Curtseyed pousou lá em cima? Como pode ser visto, ele tem um valor de hash diferente das três palavras restantes. Onde está a falha com minha compreensão/implementação da tabela de hash?

Código que produziu a saída acima:

    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 

Minha função de hash:

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

Função de comparação:

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

Diferentes valores de hash não serão necessariamente em diferentes baldes. Geralmente uma tabela de hash escolher um balde baseado em hash_value % number_of_buckets, então hashes que são iguais módulos O número de baldes acabará no mesmo balde.

Essencialmente, você não pode garantir nada sobre qual valor de hash aparece em qual balde.

Answer 2

Eu acho que você também tem um bug potencial no my_string_equality... você não quer apenas usar o regular std::string::operator==()? Afaik, você deve estar fazendo uma comparação dos valores reais do objeto, não uma comparação do hash deles (o contêiner já conhece o valor do hash, ele poderia apenas chamar my_string_hash_function e compare os resultados se era isso que precisava fazer).