我想实现一个 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
的迭代器初始化)。这就是重点。
最佳答案
哈希表的教科书实现希望单独链接就是您所说的:列表数组的一种,每个“桶”一个列表。
但是如果您考虑一下,就没有必要拥有一大堆单独的列表——您可以只拥有一个!这可能会提高顺序访问性能(注意,它是无序的,但您仍然可以“为哈希表中的每个”元素做一些事情)。
想象一下使用一个链表:把所有的值都放在那里,对于你的数组( 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 .
关于c++ - Visual C++ 只用一个std::list 实现std::unordered_map?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26315361/