c++ - 禁止碰撞的 unordered_map

Question

我想实现一个性能优化的 unordered_map 变体，它分几个阶段工作:

1. 初始化:将大约 100 个元素插入 std::map
2. 准备:施展魔法，将 std::map 转换为 std::unordered_map 的变体
3. 工作:执行大量(无限)查找；禁止插入/删除

为了使“工作”阶段尽可能快，我想选择一个对给定的键集(在初始化阶段收集)没有冲突的哈希函数。

我想衡量我可以从这个技巧中获得多少性能提升。所以这将是一个实验，可能会进入生产代码。

标准库是否有此实现的工具(例如，查找给定的 unordered_map 有多少次冲突；或更改哈希函数)？还是我应该改为自己实现？

Answer 1

这是“碰撞管理”API:

size_type bucket_count() const;
size_type max_bucket_count() const;

size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const;

local_iterator       begin(size_type n);
local_iterator       end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
const_local_iterator cbegin(size_type n) const;
const_local_iterator cend(size_type n) const;

简而言之，bucket_size(n) 为您提供了第 n 个桶的碰撞次数。您可以使用键查找存储桶，也可以使用 local_iterator 遍历存储桶。

为了更改散列函数，我会分配/构造一个新容器，从旧散列函数到新散列函数。