带有禁止碰撞的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迭代存储桶.

为了更改哈希函数,我将分配/构造一个新的容器,从旧的哈希函数到新的哈希函数.