防止不同的哈希值的键值从降落在unordered_set同一个桶

Question

这可能是一个愚蠢的问题，但在这里有云：

我散列单词的辞典成unordered_set基于散列的表。我的散列函数有人故意“坏”，因为包含相同的一组字母的所有字符串将返回相同的数值。我最初尝试过乘坐正常散列函数的行为，并且使用字母的“频率直方图”中的每个字作为散列值（我了解到是不可能:)），但其中一个线程使用建议的26-位位掩码来实现相同的。散列函数的工作原理非常愉快迄今。

例如，在我的计划，CITIED并列举散列值相同，1049144.我的想法是，给定一组字母，我想找到所有包含从集合中的字母词。

我猜测，我还没有完全明白散列的概念（或我的代码是完全错误的），因为我不能完全解释我遇到的行为：点击 我决定去寻找其中包括从字符串“搞活”字母的所有单词。 我的输出（与散列密钥）如下：

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

如何在地球上没有CURTSEYED土地在那里？如可以看到的，它具有从剩余的三个词的不同的散列值。哪里有故障的谎言与哈希表的我的理解/实施？

代码，上面产生的输出：

    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

不同的散列值并不一定会在不同的桶中结束。通常一个哈希表将选择基于hash_value % number_of_buckets铲斗，使得相等模散列桶的数量将在同一桶中卷起。

从本质上讲，你不能保证任何有关其哈希值出现在桶中。

Answer 2

我想你也有在my_string_equality了潜在的错误......难道你只想使用常规std::string::operator==()？据我所知，你应该做的实际对象值的比较，而不是他们的哈希值进行比较（容器已经知道的哈希值，它可能只是调用my_string_hash_function并比较结果，如果这是什么需要做的）。