使用 unordered_set 防止不同哈希值的键落在同一个存储桶中

Question

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

我将字典哈希到基于 unordered_set 的哈希表中。我的哈希函数被故意设置为“坏”，因为包含同一组字母的所有字符串都会哈希为相同的值。我最初尝试覆盖正常的哈希函数行为，并使用每个单词中字母的“频率直方图”作为哈希值（我了解到这是不可能的:)），但其中一个线程建议使用 26-位位掩码实现相同。到目前为止，哈希函数运行得很好。

例如，在我的方案中，CITIED 和 CITED 散列到相同的值 1049144。我的想法是，给定一组字母，我想找到包含该组字母的所有单词。

我猜我还没有完全理解哈希的概念（或者我的代码完全错误），因为我无法完全解释我遇到的行为：
我决定查找由字符串“LIVEN”中的字母组成的所有单词。 我的输出（带有哈希键）如下：

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 

我的哈希函数：

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

比较函数：

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==()？ AFAIK 你应该比较实际的对象值，而不是比较它们的哈希值（容器已经知道哈希值，它可以只调用 my_string_hash_function 并比较结果，如果这是它需要的）做）。