異なるハッシュ値のキーがoderd_setで同じバケツに着陸するのを防ぐ

StackOverflow https://stackoverflow.com/questions/4056210

質問

これはばかげた質問かもしれませんが、ここにあります：

単語の辞書をUnordered_setベースのハッシュテーブルにハッシュしました。私のハッシュ関数は意図的に「悪い」ものにされました。同じ文字のセットを含むすべての文字列が同じ値にハッシュするからです。私は最初、通常のハッシュ関数の動作をオーバーライドし、各単語の文字の「周波数ヒストグラム」をハッシュ値として使用しようとしました（これは不可能でした:)）が、26-を使用して提案されたスレッドの1つ同じことを達成するためにビットビットマスク。ハッシュ関数はこれまでに正常に動作し、ダンディです。

たとえば、私のスキームでは、Hashを同じ値に引用して引用しました1049144。

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

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

いじめっぱいの土地は一体どうやって着地したのですか？ご覧のとおり、残りの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

私のハッシュ関数： 

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;
   }
};
役に立ちましたか？

解決

異なるハッシュ値は、必ずしも異なるバケツで終わるとは限りません。通常、ハッシュテーブルはに基づいてバケツを選択します hash_value % number_of_buckets, 、したがって、等しいモジュロのハッシュは、バケツの数が同じバケツに巻き込まれます。

基本的に、どのハッシュ値がどのバケットに表示されるかを保証することはできません。

他のヒント

あなたも潜在的なバグを持っていると思います my_string_equality...通常のものを使いたくないだけです std::string::operator==()？ afaikハッシュの比較ではなく、実際のオブジェクト値の比較を行う必要があります（容器はすでにハッシュ値を知っています。 my_string_hash_function それが必要なことである場合、結果を比較してください）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top