c++ - Visual C++ 只用一个std::list 实现std::unordered_map？

Question

我想实现一个 unordered_map类似于std。所以我查看了 <unordered_map> 中的源代码和 <xhash>在 Visual C++ 2013 中。我发现实现调用 _Init unordered_map 中的函数构造函数。我发现函数的定义如下:

void _Init(size_type _Buckets = _Min_buckets)
{   // initialize hash table with _Buckets buckets, leave list alone
    _Vec.assign(2 * _Buckets, _Unchecked_end());
    _Mask = _Buckets - 1;
    _Maxidx = _Buckets;
}         

函数_Unchecked_end()只返回 _List.Unchecked_end() :

_Unchecked_iterator _Unchecked_end()
{   // return iterator for end of mutable sequence
    return (_List._Unchecked_end());
}

还有 begin()的 std::unordered_map只返回 _List.begin() ...

我认为 find() unordered_map 的功能只有一个列表不能满足一般情况下的恒定复杂度。

So... VC++到底是怎么实现的std::unordered_map ？

对不起，我没说清楚。在我看来，unordered_map 的实现应该是具有许多列表 的 vector (使用不同 std::list 的不同迭代器初始化)。但我只找到一个列表(使用一个 std::list 的迭代器初始化)。这就是重点。

Answer 1

哈希表的教科书实现希望单独链接就是您所说的:列表数组的一种，每个“桶”一个列表。

但是如果您考虑一下，就没有必要拥有一大堆单独的列表——您可以只拥有一个!这可能会提高顺序访问性能(注意，它是无序的，但您仍然可以“为哈希表中的每个”元素做一些事情)。

想象一下使用一个链表:把所有的值都放在那里，对于你的数组( vector )，直接在一个链表中使用指针/迭代器。如果你想知道一个桶从哪里开始，它和教科书的解决方案一样。要知道一个桶在哪里结束，您可以简单地查看下一个桶的开始(在恒定时间内)。

另一种看待它的方式是它是教科书的实现，但有一个修改:每个桶末尾的“下一个”指针指向下一个非空桶的开头。您会立即明白为什么这会改进顺序访问——它消除了遍历空桶的成本(其中可能有负载，因为实现不需要缩小哈希表，只需要增长它)。

有趣的故事:缺乏这种技巧是导致 GCC 和 Boost unordered_map 具有线性而不是恒定时间 erase(iterator) 性能的部分原因很多年。对于 GCC，请参阅 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975 .对于升压，请参阅 https://svn.boost.org/trac/boost/ticket/3693 .