MSVC旧版哈希表采用的方法是较少采样。这意味着孤立的更改不会显示在您的哈希值中,但您要避免的是读取和处理整个80 MB的数据以便对向量进行哈希处理。不读取一些字符是相当不可避免的。
第二件事是不要为所有的vector专门定制std :: hash,这可能会使您的程序不合规(如缺陷解决方案所建议的),并且至少是一个糟糕的计划(因为std肯定会允许自己添加哈希组合和向量哈希)。
当我编写自定义哈希时,通常使用ADL(Koenig Lookup)使其易于扩展。
namespace my_utils {
namespace hash_impl {
namespace details {
namespace adl {
template<class T>
std::size_t hash(T const& t) {
return std::hash<T>{}(t);
}
}
template<class T>
std::size_t hasher(T const& t) {
using adl::hash;
return hash(t);
}
}
struct hash_tag {};
template<class T>
std::size_t hash(hash_tag, T const& t) {
return details::hasher(t);
}
template<class T>
std::size_t hash_combine(hash_tag, std::size_t seed, T const& t) {
seed ^= hash(t) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<class Container>
std::size_t fash_hash_random_container(hash_tag, Container const& c ) {
std::size_t size = c.size();
std::size_t stride = 1 + size/10;
std::size_t r = hash(hash_tag{}, size);
for(std::size_t i = 0; i < size; i += stride) {
r = hash_combine(hash_tag{}, r, c.data()[i])
}
return r;
}
template<class T, class A>
std::size_t hash(hash_tag, std::vector<T,A> const& v) {
return fash_hash_random_container(hash_tag{}, v);
}
template<class T, std::size_t N>
std::size_t hash(hash_tag, std::array<T,N> const& a) {
return fash_hash_random_container(hash_tag{}, a);
}
}
struct my_hasher {
template<class T>
std::size_t operator()(T const& t)const {
return hash_impl::hash(hash_impl::hash_tag{}, t);
}
};
}
现在,my_hasher
是一个通用哈希器。它使用在 my_utils::hash_impl
中声明(适用于 std
类型)的哈希函数,或者调用名为 hash
的自由函数来哈希给定类型的内容。如果这些都失败了,就会尝试使用 std::hash<T>
。如果还是失败,就会产生编译时错误。
根据我的经验,在要哈希的类型的命名空间中编写自由的 hash
函数要比打开 std
并专门为其特化 std::hash
要少烦。
该哈希器递归地理解向量和数组。对于元组和成对需要更多的工作。
它以约 10 倍的采样率对这些向量和数组进行采样。
(注意:hash_tag
既是个笑话,也是一种强制 ADL 的方法,以避免不得不在 hash_impl
命名空间中前向声明 hash
特化,因为这个要求很麻烦。)
采样的代价是可能会出现更多的冲突。
如果你有大量的数据,另一个方法是对它们进行一次哈希,并跟踪它们何时被修改。为此,使用在类型上下文中跟踪哈希是否最新的写时复制单子界面。现在一个向量只需要哈希一次;如果你修改它,哈希会被丢弃。
你可以更进一步,使用随机访问哈希(其中很容易预测在编辑给定值时哈希会发生什么),并调节访问向量的所有方式。这很棘手。
你也可以多线程进行哈希计算,但我猜想你的代码可能已经受到了内存带宽的限制,并且多线程不会有太大的帮助。还是值得一试的。
你可以使用比一个扁平向量更高级的结构(例如树形结构),其中值的更改以哈希类似的方式冒泡到根哈希值。这将增加所有元素访问的 lg(n) 开销。同样地,你必须将原始数据包装在控件中,以保持哈希计算的最新状态(或跟踪哪些范围是脏的,并需要更新)。
最后,因为你每次处理 1000 万个元素,请考虑转向强大的大规模存储解决方案,如数据库等。在 Map 中使用 80MB 的键对我来说似乎很奇怪。
std::hash<double>
是否过于智能了,也许一个不那么花哨的实现(例如*reinterpret_cast<const size_t *>(&v)
)会更适合你的用法。v.data()
并在紧密循环中直接迭代元素,使用自己的内联哈希代码即可获得另一个巨大的性能提升。对于你所拥有的1000万个项目,函数调用开销太大了。 - selbie