whi*_*kar 51 c++ stl unordered-map
C++ STL unordered_map如何解决冲突？
查看http://www.cplusplus.com/reference/unordered_map/unordered_map/,它显示"唯一键容器中没有两个元素可以具有等效键."
这应该意味着容器确实解决了碰撞.但是,该页面并没有告诉我它是如何做到的.我知道一些解决冲突的方法,比如使用链表和/或探测.我想知道的是c ++ STL unordered_map如何解析它.
Jer*_*fin 63
该标准比大多数人似乎意识到的更多地定义了这一点.
具体而言,该标准要求(§23.2.5/ 9):
无序关联容器的元素被组织成桶.具有相同哈希码的密钥出现在同一个存储桶中.
界面包括一个bucket_count在恒定时间内运行的界面.(表103).它还包括一个bucket_size必须按时间线性运行的桶的大小.
这基本上描述了使用冲突链的实现.当您使用碰撞链时,满足所有要求介于简单和简单之间.bucket_count()是数组中元素的数量.bucket_size()是碰撞链中的元素数量.分别使它们处于恒定和线性时间是简单而直接的.
相比之下,如果使用线性探测或双重散列等方法,那些要求几乎不可能满足.具体来说,所有散列到特定值的项目都需要在同一个桶中着陆,并且您需要能够在恒定时间内对这些桶进行计数.
但是,如果你使用线性探测或双重散列之类的东西,找到散列到相同值的所有项目意味着你需要散列值,然后遍历表格中非空项目的"链"以查找有多少那些哈希值相同.但是,对于散列到相同值的项目数,这并不是线性的 - 它与散列到相同或冲突值的项目数呈线性关系.
有了足够的额外工作和相当多的要求将某些要求的含义拉伸到断点,几乎不可能使用除碰撞链之外的其他东西来创建哈希表,并且至少仍然满足要求 - - 但我不确定它是否可能,而且肯定会涉及到相当多的额外工作.
总结:(std::unordered_set或unordered_map)的所有实际实现无疑都使用碰撞链.虽然可能(几乎不可能)使用线性探测或双重散列来满足要求,但这样的实现似乎失去了很多并且几乎没有任何回报.
我发现这个答案是为了寻找如何检测我的类型何时发生冲突，因此我将发布此内容，以防这是问题的意图：
我相信对于“唯一键容器中没有两个元素可以具有相同的键”存在一些误解。
看下面的代码
//pseudocode
std::unordered_map<int, char> hashmap;
hashmap[5] = 'a';
hashmap[5] = 'b'; //replace 'a' with 'b', there is no collision being handled.
我认为杰里的答案是指它用来将键收缩到适当的数组索引的内部系统。
如果您希望为您的类型（带有存储桶）处理冲突，您需要std::unordered_multimap并且必须迭代
希望这段代码可以在没有我生成它的上下文的情况下被阅读。它基本上检查与哈希关联的存储桶中是否有任何元素是我正在寻找的元素。
//pseudocode
std::unordered_map<int, char> hashmap;
hashmap[5] = 'a';
hashmap[5] = 'b'; //replace 'a' with 'b', there is no collision being handled.