Ответ 1

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

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

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

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

Ответ 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 prime hash:

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 лучше, но основной хеш Мерсенна будет быстрее на многих машинах, потому что умножение на 127 часто значительно быстрее, чем умножение на 2166136261.)

Ответ 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

Ответ 4

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

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

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

Ответ 5

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