c++std::hash<>有一些固定大小的基本类型的标准专门化，std::string家族是唯一一个具有可变内存大小的(std::vector<bool>也是，这里不关心)
一旦我们倾向于对多个变量或一个缓冲区进行哈希，我们就需要实现一个哈希算法，这个算法很难记住，而且很容易出错。
std::string可以用作缓冲区(std::vector<std::byte>更好，我知道)，如果我们在其中存储utf-8字符串(其中有ASCII以外的字节)，它很可能也是哈希。
这样做的缺点是什么?
std::string hash_wrapper(4 * 4, ' ');
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;
你的代码违反了严格混叠。
你的代码非常不清楚它在做什么。
散列映射的关键在于它们是映射。您的哈希映射是从一个模糊转换的字符串类型到您的数据，而不是从一个合理的键到您的数据。
我的建议是:
-
写一个哈希组合器，或者使用别人已经发布的一个(有适当的归属/权利)，比如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。