C++ std::hash<>
имеет некоторые стандартные специализации для базовых типов с фиксированным размером и семейство std::string
, которое является единственным, имеющим переменный размер памяти (и std::vector<bool>
тоже не имеет значения здесь)
как только мы склоняемся к хешированию нескольких переменных или буфера, нам нужно реализовать алгоритм хеширования, который трудно запомнить и который легко ошибиться.
std::string
можно использовать в качестве буфера (std::vector<std::byte>
лучше, я знаю), и если мы храним в нем строку utf-8 (в которой есть байты, отличные от ASCII), она, вероятно, тоже хорошо хэшируется.
в чем такой недостаток:
std::string hash_wrapper(4 * 4, '\0');
int* write_ptr = reinterpret_cast<int*>(hash_wrapper.data());
write_ptr[0] = val1;
write_ptr[1] = val2;
write_ptr[2] = val3;
write_ptr[3] = val4;
std::unordered_map<std::string, int> ht;
ht[hash_wrapper] = val;
хотя его можно заставить работать, алгоритм хеширования для std::string, скорее всего, оптимизирован для строк, поэтому он может быть очень плохим при использовании для произвольных данных, что приводит к большому количеству коллизий хэшей.
Ваш код нарушает строгое использование псевдонимов.
Ваш код крайне неясен, что он делает.
Суть хеш-карт в том, что они карты. Ваша хеш-карта переходит от неясно преобразованного строкового типа к вашим данным, а не от разумного ключа к вашим данным.
Мой совет:
Напишите объединитель хэшей или используйте тот, который кто-то опубликовал (с надлежащей атрибуцией/правами), например, boost. Комбинатор хэшей берет два хэша и делает из них один.
Расширение до объединителей хэшей, которые берут произвольную последовательность хэшей и объединяют их.
Теперь напишите короткую библиотеку.
namespace MyHash {
// by default, dispatch to std::hash:
template<class T>
std::size_t runtime_hash( T const& t ) {
return std::hash<T>{}(t);
}
// range-like support (begin/end):
template<class R>
std::size_t hash_range( R const& r );
// tuple-like support (std::get, etc):
template<std::size_t...Is, class T>
std::size_t tuple_hasher( std::index_sequence<Is...>, T const& t );
// TODO: supply this function
inline std::size_t hash_combine( std::size_t lhs, std::size_r rhs ) {
// write this
}
// support for 0 to infinite args:
inline std::size_t hash_combine( std::size_t x ) {
return x;
}
inline std::size_t hash_combine() {
return 0;
}
template<class...Ts>
std::size_t hash_combine( std::size_t lhs, std::size_t rhs, Ts... ts ) {
return hash_combine( lhs, hash_combine( rhs, ts... ) );
}
// Add std runtime_hashs here:
// std "range" type supports:
template<class...Ts>
std::size_t runtime_hash( std::vector<Ts...> const& v ) {
return hash_range(v);
}
template<class...Ts>
std::size_t runtime_hash( std::set<Ts...> const& s ) {
return hash_range(s);
}
template<class...Ts>
std::size_t runtime_hash( std::unordered_set<Ts...> const& s ) {
return hash_range(s);
}
template<class...Ts>
std::size_t runtime_hash( std::map<Ts...> const& m ) {
return hash_range(m);
}
template<class...Ts>
std::size_t runtime_hash( std::unordered_map<Ts...> const& m ) {
return hash_range(m);
}
// tuple-like support:
template<class...Ts>
std::size_t runtime_hash( std::tuple<Ts...> const& t ) {
return tuple_hasher( std::make_index_sequence<Ts...>{}, t );
}
template<class T0, class T1>
std::size_t runtime_hash( std::pair<T0, T1> const& t ) {
return tuple_hasher( std::make_index_sequence<2>{}, t );
}
template<class T, std::size_t N>
std::size_t runtime_hash( std::array<T, N> const& t ) {
return tuple_hasher( std::make_index_sequence<N>{}, t );
}
// optional. Note that hash of an engaged optional is distinct
// from a hash of a value by a hash_combine. An optional acts
// as a range of 0 or 1 element hash-wise.
template<class T>
std::size_t runtime_hash( std::optional<T> const& t ) {
std::size_t retval = 0x0;
if (t) retval = hash_combine(retval, runtime_hash(t) );
return retval;
}
// add more types here!
struct runtime_hasher {
template<class T>
std::size_t operator()(T const& t)const{
return runtime_hash(t);
}
};
template<class R>
std::size_t hash_range( R const& r ) {
std::size_t seed = 0;
for (auto const& e : r) {
seed = hash_combine( seed, runtime_hash(r) );
}
}
template<std::size_t...Is, class T>
std::size_t tuple_hasher( std::index_sequence<Is...>, T const& t ) {
return hash_combine( runtime_hash(std::get<Is>(t))... );
}
}
теперь, когда вам нужен пользовательский хеш времени выполнения, переопределите runtime_hash
для вашего пользовательского типа в пространстве имен типа.
С этой работой,
namespace bob {
struct alice {
int val1, val2, val3, val4;
friend auto operator==(const alice&, const alice&) = default;
};
}
Я могу добавить поддержку хэша:
namespace bob {
inline std::size_t runtime_hash( alice const& a ) {
return runtime_hash( std::tie(a.val1, a.val2, a.val3, a.val4) );
}
}
и с этим
std::unordered_map<bob::alice, int, MyHash::runtime_hasher> map;
просто работает.
Функция runtime_hash
находится через ADL. Более того, у std::vector<bob::alice>
есть поддержка хэшей, как и у std::tuple<bob::alice>
и std::tuple<std::set<bob::alice>, bob::alice>
и т. д. И если вы напишете любой другой составной тип и поддержите его, как я сделал с контейнерами std
, контейнеры, содержащие bob::alice
, тоже будут работать.
Размер и сложность кода этой утилиты, приведенной выше, достаточно малы, чтобы возиться с буферами, указателями и неопределенными псевдонимами определенно не стоит.
Обратите внимание, что я называю это runtime_hash
— это делает его несколько уникальным именем (важно для ADL) и подчеркивает, что нет никаких гарантий, что этот хэш стабилен при различных запусках программы. Вы не можете полагаться на стабильность хэша std
таким образом, поскольку они не дают такой гарантии.
Приносим извинения за любые опечатки. Приведенный выше код был введен непосредственно в ответ и никогда не компилировался, поэтому, вероятно, он содержит по крайней мере один tpyo.
Как насчет того факта, что он имеет неопределенное поведение в результате нарушения строгого правила алиасинга? Это можно решить, написав
char
s в строку вместо того, чтобы пытаться принудительно вводитьint
s. Или используяstd::memcpy()
вместо присваивания через указатель.