Предотвращение ключа разных хеш-ценностей от посадки в одном ведре с неупоряженным_set

Question

Это может быть глупым вопросом, но здесь идет:

Я хешил словарь слов в неожиданный хеш-таблица на основе Unuporded_set. Моя хеш-функция была сделана преднамеренно «плохим», в том, что все строки, содержащиеся в том же наборе букв, будут таскать одинаковое значение. Я изначально пытался перевернуть нормальное поведение хеш-функции и использовать «частотную гистограмму» букв в каждом сложенном виде как хеш-ценность (который я узнал, было невозможно :)), но один из потоков, предложенных с использованием 26- Битшая ратушка для достижения того же. Хеш-функция работает нормально, а данди далеко.

Например, по моей схеме, свидетельствуют и цитируют хэш к тому же величине, 1049144. Моя идея заключалась в том, что дали набор букв, я хотел найти все слова, содержащие буквы из этого набора.

Я догадаюсь, что я не совсем понял концепцию хеширования (или моего кода неправомерно), так как я не могу объяснить поведение, которое я столкнулся с:
Я решил искать все слова, состоящие из букв из струны «живанные». Мой вывод (с ключом HASH) был следующим:

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 и сравните результаты, если это было то, что нужно сделать).