منع مفاتيح قيم التجزئة المختلفة من الهبوط في نفس الدلو مع unordered_set

Question

قد يكون هذا سؤالًا سخيفًا ، ولكن هنا يذهب:

لقد قمت بتجميع قاموس الكلمات في طاولة التجزئة القائمة على unordered_set. تم صنع وظيفة التجزئة الخاصة بي عن عمد "سيئة" ، حيث أن جميع الأوتار التي تحتوي على نفس مجموعة الرسائل سوف تجزئة بنفس القيمة. لقد حاولت في البداية تجاوز سلوك وظائف التجزئة العادية ، واستخدم "رسم بياني تردد" للأحرف في كل كلمة كقيمة تجزئة (التي تعلمتها كانت مستحيلة :)) ، ولكن أحد المواضيع اقترح باستخدام 26- bitmask لتحقيق الشيء نفسه. تعمل وظيفة التجزئة بشكل جيد و dandy حتى الآن.

على سبيل المثال ، في مخططي ، تم تجزئة التجزئة والاستشهاد بها بنفس القيمة ، 1049144. كانت فكرتي هي أنه أعطيت مجموعة من الحروف ، أردت أن أجد جميع الكلمات التي تحتوي على رسائل من تلك المجموعة.

أظن أنني لم أفهم تمامًا مفهوم التجزئة (أو أن الكود الخاص بي خاطئ) ، حيث لا يمكنني شرح السلوك الذي واجهته تمامًا:
قررت البحث عن كل الكلمات التي تتألف من رسائل من السلسلة "Liven". كان مخرجاتي (مع مفتاح التجزئة) كما يلي:

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

كيف على الأرض هبطت كورتسيد هناك؟ كما يمكن أن نرى ، يكون له قيمة تجزئة مختلفة من الكلمات الثلاث المتبقية. أين يكمن الخطأ مع فهمي/تنفيذ جدول التجزئة؟

الكود الذي أنتج أعلاه الإخراج:

    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 وقارن النتائج إذا كان هذا هو ما يحتاج إلى القيام به).