c++ - 使用 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 

<p>My hash function : </p> <pre><code>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; } }; </code></pre> <p>Comparison function : </p>

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 选择一个桶，因此以桶数为模的相等哈希值将在同一个桶中结束。

从本质上讲，您无法保证哪个哈希值出现在哪个桶中。