如何为位集找到/实现一个好的哈希函数
我正在尝试使用unordered_map，其中密钥(存储在位集中)是通过Morton编码生成的。我测试了几种情况，当密钥在2^0-2^6、2^3-2^9 (后3位为零)、2^6-2^12 (后6位为零)和2^9-2^15 (后9位为0)范围内时。
当我使用visual studio为位集提供的默认哈希函数时，一切似乎都很好。对于所有情况，在unordered_map中查找元素的时间是相同的，并且随着容器的大小单调增加。
当我试图减少查找元素的时间时，出现了一些错误。我使用散列函数
class my_bitset_hash
{
public:
size_t operator()(const bitset<64>& key) const
{
size_t hashVal = 0;
hashVal = key.to_ullong();
return hashVal;
}
};即使unorder_map的大小相同，当键在2^9-2^15范围内时，查找元素的时间至少比键在2^0-2^6范围内时大两个数量级。据我所知，如果没有碰撞，查找的时间消耗应该是最低的，时间复杂度应该是O(1)。此外，与使用默认函数的情况相比，所有情况都需要更多的时间进行查找。
有没有人对此有一些想法，以及如何为位集找到一个好的哈希函数？
谢谢
回答 1
Stack Overflow用户
发布于 2020-06-12 22:02:36
有没有人对此有一些想法，以及如何为位集找到一个好的哈希函数？
尝试不同的散列函数。
如果您的字典在使用运行时数据创建后保持不可变，请尝试使用暴力强制哈希函数种子。
下面是一个尝试最小化冲突的示例：
#include <unordered_set>
#include <iostream>
#include <cmath>
struct Stats {
static int constexpr BINS = 8;
size_t size = 0;
size_t buckets = 0;
double load_pct = 0;
double collision_pct = 0;
unsigned collisions[BINS] = {};
};
std::ostream& operator<<(std::ostream& o, Stats const s) {
o << "size: " << s.size << ", ";
o << "buckets: " << s.buckets << ", ";
o << "load: " << std::round(s.load_pct) << "%, ";
o << "collisions: " << std::round(s.collision_pct) << "% [";
for(auto const& bin : s.collisions)
o << bin << ',';
return o << "]\n";
}
template<class C>
Stats stats(C const& c) {
Stats s;
s.size = c.size();
s.buckets = c.bucket_count();
s.load_pct = 100. * c.size() / c.bucket_count();
size_t collisions = 0;
for(auto bucket_idx = c.bucket_count(); bucket_idx--;) {
auto elements_in_bucket = std::distance(c.begin(bucket_idx), c.end(bucket_idx));
if(elements_in_bucket > 1) {
++collisions;
++s.collisions[std::min<unsigned>(Stats::BINS - 1, elements_in_bucket - 2)];
}
}
s.collision_pct = 100. * collisions / c.size();
return s;
}
// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
struct Fnv1a32 {
static constexpr unsigned BASIS = 16777619;
static constexpr unsigned PRIME = 2166136261;
unsigned const state_;
static constexpr unsigned hash(void const* key, size_t len, unsigned state) noexcept {
unsigned char const* p = static_cast<unsigned char const*>(key);
unsigned char const* const e = p + len;
for(; p < e; ++p)
state = (state ^ *p) * PRIME;
return state;
}
public:
constexpr Fnv1a32(unsigned seed = 0)
: state_(seed ? hash(&seed, sizeof seed, BASIS) : BASIS)
{}
template<class T>
std::enable_if_t<std::is_integral<T>::value, unsigned> operator()(T key) const {
return hash(&key, sizeof key, state_);
}
};
int main() {
// Using std::hash.
std::unordered_set<unsigned> s;
for(unsigned n = 1000; n--;)
s.insert(static_cast<unsigned>(std::rand()) << 6);
std::cout << "std::hash: " << stats(s);
// Using Fnv1a32.
std::unordered_set<unsigned, Fnv1a32> s2(s.bucket_count());
s2.insert(s.begin(), s.end());
std::cout << "Fnv1a32: " << stats(s2);
// Brute-force Fnv1a32 seed.
double best_collision_pct = std::numeric_limits<double>::infinity();
unsigned best_seed = 0;
for(unsigned seed = 0; seed < 10000; ++seed) {
std::unordered_set<unsigned, Fnv1a32> s3(s2.bucket_count(), Fnv1a32{seed});
s3.insert(s2.begin(), s2.end());
auto const stats3 = stats(s3);
if(stats3.collision_pct < best_collision_pct) {
best_collision_pct = stats3.collision_pct;
best_seed = seed;
}
}
// Using Fnv1a32 with the best seed.
std::unordered_set<unsigned, Fnv1a32> s4(s2.bucket_count(), Fnv1a32{best_seed});
s4.insert(s2.begin(), s2.end());
std::cout << "Fnv1a32 best: " << stats(s4);
}输出：
std::hash: size: 1000, buckets: 1493, load: 67%, collisions: 21% [152,46,6,1,0,0,0,0,]
Fnv1a32: size: 1000, buckets: 1613, load: 62%, collisions: 21% [177,29,3,1,0,0,0,0,]
Fnv1a32 best: size: 1000, buckets: 1741, load: 57%, collisions: 17% [135,24,5,1,0,0,0,0,]您可能希望以类似方式最小化的另一个指标是查找时间。
对于std::unordered_set和std::unordered_map，查找时间可能是α*buckets + β*collisions + γ*hashtime的函数，即查找时间随以下时间增长：
- 桶的数量-更多的桶导致更多的CPU缓存未命中。
- 冲突的数量-当不同的元素最终在同一个桶中时。标准容器存储桶是链表，因此每次冲突都需要跟随列表到下一个元素，这可能是CPU缓存未命中；以及另一个关键的comparison.
- With散列函数CPU time。
您还可以尝试不同的哈希表，如skarupke::flat_hash_map和C++Now 2018: You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance，它们不使用链表来解决冲突，通常提供最佳性能。
请注意，哈希表的性能在很大程度上取决于键、哈希函数和大小，因此通用基准测试可能不会反映特定工作负载的性能。您需要根据您的实际工作负载/数据集对其进行基准测试。
https://stackoverflow.com/questions/62342265
复制相似问题
腾讯云开发者
