1

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

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

例如，在我的方案中，CITIED 和 CITED 哈希到相同的值，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;
   }
};
4

2 回答 2

3

不同的哈希值不一定会在不同的桶中结束。通常，哈希表会根据 选择一个桶hash_value % number_of_buckets，因此以桶数为模的哈希值将在同一个桶中结束。

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

于 2010-10-29T22:02:15.000 回答
0

我认为你也有一个潜在的错误my_string_equality......你不想使用常规std::string::operator==()吗？AFAIK，您应该比较实际的对象值，而不是比较它们的哈希值（容器已经知道哈希值，my_string_hash_function如果这是它需要做的，它可以调用并比较结果）。

于 2010-12-21T04:22:40.193 回答