1

これはばかげた質問かもしれませんが、次のようになります。

単語の辞書を unordered_set ベースのハッシュ テーブルにハッシュしました。私のハッシュ関数は、同じ文字セットを含むすべての文字列が同じ値にハッシュされるという点で、意図的に「悪い」ものにされました。私は当初、通常のハッシュ関数の動作をオーバーライドし、各単語の文字の「頻度ヒストグラム」をハッシュ値として使用しようとしました (これは不可能だとわかりました :) ) が、スレッドの 1 つが 26-同じことを達成するためのビットビットマスク。これまでのところ、ハッシュ関数は問題なく動作します。

たとえば、私のスキームでは、CITIED と CITED は同じ値 1049144 にハッシュされます。私のアイデアは、文字セットが与えられた場合、そのセットの文字を含むすべての単語を見つけたいというものでした。

私が遭遇した動作を完全に説明できないため、ハッシュの概念を完全に理解していない (またはコードが明らかに間違っている) と推測しています:
文字列の文字で構成されるすべての単語を探すことにしました。 LIVEN」。私の出力（ハッシュキー付き）は次のとおりです： 

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

CURTSEYED は一体どうやってそこに上陸したのですか? ご覧のとおり、残りの 3 つの単語とは異なるハッシュ値を持っています。ハッシュテーブルの理解/実装のどこに問題がありますか?

上記の出力を生成するコード: 


    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==()か？私の知る限り、ハッシュの比較ではなく、実際のオブジェクト値の比較を行う必要があります（コンテナはすでにハッシュ値を知っているため、my_string_hash_functionそれが必要な場合は結果を呼び出して比較するだけです）。

于 2010-12-21T04:22:40.193 に答える