Предотвращение попадания ключей с разными значениями хеша в одно и то же ведро с помощью unordered_set - PullRequest
Новая
       60

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

1 голос
/ 30 октября 2010

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

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

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

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

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

Как, черт возьми, CURTSEYED приземлился там? Как видно, он имеет хеш-значение, отличное от остальных трех слов. Где ошибка лежит в моем понимании / реализации хеш-таблицы?

Код, выдаваемый над выводом: 

<code>
    typedef std::unordered_set&lt std::string, my_string_hash_function, my_string_equality&gt 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;
   }
};
</code>

Ответы [ 2 ]

3 голосов
/ 30 октября 2010

Различные значения хеш-функции не обязательно окажутся в разных сегментах.Обычно в хеш-таблице выбирается сегмент, основанный на hash_value % number_of_buckets, поэтому хеши, равные по модулю количеству сегментов, попадут в один и тот же сегмент.

По сути, вы не можете гарантировать, что значение хеш-функции отображается вкакое ведро.

0 голосов
/ 21 декабря 2010

Я думаю, у вас также есть потенциальная ошибка в my_string_equality ... разве вы просто не хотите использовать обычный std::string::operator==()?AFAIK. Вы должны делать сравнение фактических значений объекта, а не сравнение их хеша (контейнер уже знает значение хеша, он может просто вызвать my_string_hash_function и сравнить результаты, если это было то, что ему нужно было сделать).

...