Неожиданное столкновение с std :: hash

Question

Я знаю, что хеширование бесконечного числа строк в 32b int должно вызывать коллизию, но я ожидаю от функции хеширования хорошего распределения.

Разве не странно, что эти 2 строки имеют одинаковый хэш?

size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
//hash0 == hash1

Я знаю, что могу использовать boost::hash<std::string> или другие, но я хочу знать, что не так с std::hash. Я использую это неправильно? Разве я не должен как-то "затравить" это?

Answer 1

Нет ничего плохого в том, что вы используете std::hash. Проблема заключается в том, что специализация std::hash<std::string>, предоставляемая реализацией стандартной библиотеки, поставляемой в комплекте с Visual Studio 2010, использует только подмножество символов строки для определения значения хеша (предположительно по соображениям производительности). По совпадению последний символ строки из 14 символов не является частью этого набора, поэтому обе строки выдают одно и то же значение хеш-функции.

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

Подробнее см. В реализации в заголовочном файле xfunctional (начиная со строки 869 в моей копии) и §17.6.3.4 стандарта C ++ ( последний открытый проект ).

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

Answer 2

Точный алгоритм хеширования не указан стандартом, поэтому результаты могут отличаться.Алгоритм, используемый VC10, похоже, не учитывает все символы, если длина строки превышает 10 символов;оно продвигается с шагом 1 + s.size() / 10.Это законно, хотя и с точки зрения QoI, довольно обидно;Известно, что такие хэш-коды работают очень плохо для некоторых типичных наборов данных (например, URL).Я настоятельно рекомендую заменить его хешем FNV или хешем на основе простого числа Мерсенна:

хеш FNV:

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = (16777619 * result)
                    ^ static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

простого хеша Mersenne:

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = 127 * result
                   + static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

(Хеш FNV предположительно лучше, но основной хеш Mersenne будет быстрее на многих машинах, потому что умножение на 127 часто значительно быстрее, чем умножение на 2166136261.)

Answer 3

Скорее всего, вы должны получить разные значения хеша.Я получаю различные значения хеша (GCC 4.5):

hashtest.cpp

#include <string>
#include <iostream>
#include <functional>
int main(int argc, char** argv)
{
size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n";
return 0;
}

Вывод

# g++ hashtest.cpp -o hashtest -std=gnu++0x
# ./hashtest
16797002355621538189 != 16797001256109909978

Answer 4

Вы не выполняете функцию хеширования, вы можете просто посолить их.

Функция используется правильно, и это столкновение может быть просто случайным.

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

Answer 5

Хеш-функция TR1 и новейший стандарт определяют правильные перегрузки для таких вещей, как строки. Когда я запускаю этот код, используя std :: tr1 :: hash (g ++ 4.1.2), я получаю разные значения хеш-функции для этих двух строк.