C STLunordered_map如何解决冲突？

Question

C STLunordered_map如何解决冲突？

看着http://www.cplusplus.com/reference/unordered_map/unordered_map/，它说“唯一的键容器中的两个元素不能有相同的键。”

这意味着容器确实在解决碰撞。然而，那一页并没有告诉我它是如何做到的。我知道一些解决冲突的方法，比如使用链表和/或探测。我想知道的是c STL无序_映射是如何解决它的。

Answer 1

我找到这个答案是为了寻找如何检测我的类型何时发生冲突，所以如果这是问题的意图，我将发布这个答案

我相信人们对“唯一键”有一些误解，容器中没有两个元素可以有相同的键

看看下面的代码

//pseudocode
std::unordered_map<int, char> hashmap;
hashmap[5] = 'a';
hashmap[5] = 'b'; //replace 'a' with 'b', there is no collision being handled.

我认为Jerry的答案是指内部系统，它使用该系统将密钥收缩到适当的数组索引。

如果你想为你的类型（使用bucket）处理冲突，你需要std:：unordered_multimap，并且必须迭代

希望这段代码可以在没有我生成它的上下文的情况下被读取。它基本上检查了与哈希相关联的桶中的任何元素是否是我要找的元素。

//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;
}

Answer 2

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

具体而言，该标准要求（§23.2.5/9）：

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

该界面包括一个以恒定时间运行的桶计数。（表103）。它还包括一个bucket_size，必须根据bucket的大小在时间上线性运行。

这基本上描述了一个使用冲突链的实现。当您使用冲突链接时，满足所有要求是简单和琐碎的bucket_count（）是数组中的元素数bucket_size（）是碰撞链中的元素数。分别在常数时间和线性时间内得到它们是简单而直接的。

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

但是，如果你使用线性探测或双重散列，找到所有散列到相同值的项目意味着你需要散列值，然后遍历表中非空项目的“链”，找出其中有多少散列到相同值。然而，散列到相同值的项目数量并不是线性的——散列到相同或冲突值的项目数量是线性的。

有了足够多的额外工作和相当多的将一些需求的含义延伸到几乎极限的情况下，使用碰撞链以外的东西创建哈希表几乎是不可能的，并且至少在某种程度上满足需求——但我不确定这是否可能，而且这肯定会涉及大量的额外工作。

总结：std:：unordered_set（或unordered_map）的所有实际实现无疑都使用了冲突链接。虽然使用线性探测或双重散列可能（几乎）不可能满足需求，但这样的实现似乎损失很大，几乎没有任何回报。