В поисках некоторого детерминированного хеша для целых чисел (с несколькими прогонами, с несколькими машинами) я наткнулся на boost::hash_combine(size_t & seed, T const& v)
, К сожалению, в документация заявлено, что
Эта хеш-функция не предназначена для общего использования и не гарантируется, что она будет одинаковой при отдельных запусках программы, поэтому, пожалуйста, не используйте ее для постоянного хранения или обмена данными.
Однако, просматривая реализацию, я не увидел ни одного подозрительного кода, который может вызывать расходящееся поведение в отдельных прогонах — только некоторое умножение и сложение (с возможными переполнениями), операции сдвига битов и операции xor, все с использованием констант. Более того, хешер вел себя последовательно, когда выполнялся несколько раз.
Так где же актуальная проблема, которая запрещает гарантировать детерминизм во всех сериях?
Вклеиваем под самые интересные произведения:
template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
boost::hash<T> hasher;
return boost::hash_detail::hash_combine_impl(seed, hasher(v));
}
template <typename T>
typename boost::hash_detail::basic_numbers<T>::type hash_value(T v)
{
return static_cast<std::size_t>(v);
}
inline void hash_combine_impl(boost::uint64_t& h,
boost::uint64_t k)
{
const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
const int r = 47;
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
// Completely arbitrary number, to prevent 0's
// from hashing to 0.
h += 0xe6546b64;
}
Причина в том, что хеш-коды часто используются в хеш-таблицах. Злонамеренный пользователь, пытающийся атаковать службу (которая использует код C ++ с использованием хеш-таблиц), может существенно снизить его производительность, принудительно вызывая коллизии хеш-функции для элементов, вставленных в хеш-таблицу (при этом производительность обычных операций изменяется от O (1) до O (N)). ). При каждом запуске использовать разные хэш-функции, это становится намного сложнее.
std::hash
стандартизированы как это тоже. Цитировать https://en.cppreference.com/w/cpp/utility/hash:
Хеш-функции требуются только для получения одинакового результата для одного и того же ввода в рамках одного выполнения программы; это позволяет посолить хэши, которые предотвращают столкновения DoS-атак. (начиная с C ++ 14)
Других решений пока нет …