首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如果我在构造函数中指定最小桶的大小,我会保证不会在`unordered_set`中得到与不同哈希值的冲突吗?

问如果我在构造函数中指定最小桶的大小,我会保证不会在`unordered_set`中得到与不同哈希值的冲突吗?
EN

Stack Overflow用户
提问于 2014-09-09 09:51:01
回答 2查看 99关注 0票数 0

因此,我将传递512个的unordered_set构造为最小桶,即n参数。我的哈希函数总是在范围[0,511]中返回一个值。

我的问题是,我是否还可以得到两个不相同的哈希值之间的冲突?为了使它更清楚,我容忍任何关于使用相同散列的值的冲突,但我可能不会与不同的散列值发生冲突。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-09-09 10:07:21

任何合理的实现都将bucket(k)实现为hasher(k) % bucket_count(),在这种情况下,如果哈希范围不大于bucket_count(),则不会从具有不同散列的值中获得冲突。

但是,不能保证这一点;只有相同的散列值映射到同一个桶中。一个糟糕的实现(例如)可能忽略其中一个桶,仍然满足容器需求;在这种情况下,您将得到冲突。

如果程序的正确性依赖于不同的散列值,则必须检查所使用的特定实现(可能会为这种行为编写测试),或者实现自己的容器以满足您的需求。

票数 2
EN

Stack Overflow用户

发布于 2014-09-09 09:56:22

由于没有无限数量的桶和/或完美的散列函数,如果您继续插入键(甚至使用较少的键,请查看生日悖论),您最终肯定会得到冲突(即,哈希指向同一个位置)。

最小化它们的关键是调优您的负载因子和(正如我认为STL内部所做的) 处理碰撞。对于桶值,您应该选择它,以避免重散列。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/25741563

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档