C + + STL unorder_map 如何解决冲突？

C + + STL unorder _ map 如何解决冲突？

看看 http://www.cplusplus.com/reference/unordered_map/unordered_map/上面写着“独一无二的钥匙” 容器中的任何两个元素都不能有等效的钥匙。”

这应该意味着容器确实在解决冲突。然而，这一页并没有告诉我它是如何做到的。我知道一些解决冲突的方法，比如使用链表和/或探测。我想知道的是 c + + STL unorder _ map 是如何解析它的。

37862 次浏览
小开
最佳答案

该标准对此的定义比大多数人似乎意识到的要多一些。

具体来说，该标准要求(23.2.5/9) :

无序关联容器的元素被组织成桶。具有相同哈希代码的键出现在同一个桶中。

该接口包括一个在恒定时间内运行的 bucket_count。(表103)。它还包括一个 bucket_size，它必须在时间线性上运行桶的大小。

这基本上描述了一个使用冲突链接的实现。当您使用冲突链接时，满足所有需求是在简单和琐碎之间的某个地方。bucket_count()是数组中的元素数。bucket_size()是碰撞链中元素的个数。使它们分别处于常数和线性时间内是简单而直接的。

相比之下，如果使用线性探测或双哈希，这些需求几乎不可能满足。具体来说，散列到特定值的所有项都需要放在同一个 bucket 中，并且您需要能够在常量时间内计算这些 bucket 的数量。

但是，如果你使用线性探测或者双哈希，找到所有散列为相同值的项意味着你需要散列值，然后遍历表中非空项的“链”，找出其中有多少散列为相同值。但是散列到相同值的项数并不是线性的——它是散列到相同 或者碰撞值的项数的线性。

有了足够多的额外工作和相当多的延伸意义的一些需求几乎到了崩溃点，它可能几乎不可能创建一个散列表使用其他东西以外的碰撞链接，仍然至少在某种程度上满足要求-但我不确定这是可能的，它肯定会涉及相当多的额外工作。

概要: 所有 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.

我认为 Jerry 的答案是指内部系统，它使用这个系统将键缩小到适当的数组索引。

如果希望为类型处理冲突(使用桶) ，则需要 std::unordered_multimap，并且必须迭代

希望这段代码可以在没有上下文的情况下阅读。 它主要检查 bucket 中与散列相关联的元素是否是我要查找的元素。

//sp is std::shared_ptr
//memo is std::unordered_multimap< int, sp<AStarNode> >


//there's probably multiple issues with this code in terms of good design (like using int keys rather than unsigned)


bool AStar_Incremental::hasNodeBeenVisited(sp<AStarNode> node)
{
using UMIter = std::unordered_multimap<int, sp<AStarNode> >::iterator;


bool bAlreadyVisited = false;


//get all values for key in O(1*)
int hash = WorldGrid::hashGrid(node->location);
std::pair<UMIter, UMIter> start_end = memo.equal_range(hash); //bucket range
UMIter start = start_end.first;
UMIter end = start_end.second;


//hopefully this is implemented to be O(m) where m is the bucket size.
for(UMIter bucketIter = start; bucketIter != end; ++bucketIter)
{
sp<AStarNode> previousNode = bucketIter->second;
sf::Vector2i& previousVisit = previousNode->location;
if (previousVisit == node->location)
{
bAlreadyVisited = true;
break;
}
}


return bAlreadyVisited;
}

提交答案