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在一般情况下不能满足常数的复杂性.

那么...... VC++如何实现std::unordered_map呢？

对不起,我没有说清楚.在我看来,实现unordered_map应该是一个带有许多列表的向量(具有不同 std::list s的不同迭代器的Init ).但我只找到一个列表(Init的迭代器为1 std::list).这才是重点.

Answer 1

哈希表的教科书实现希望单独链接就是你说的:排序列表,每个"桶"一个列表.

但是如果你考虑一下,就没有必要拥有一大堆单独的列表 - 你只能拥有一个!这可以改善顺序访问性能(nb它是无序的,但你仍然可以为哈希表中的每个"元素"做一些事情).

因此,想象一下使用一个链表:将所有值放在那里,对于你的数组(向量),将指针/迭代器直接用于一个链表.如果您想知道一个桶的起始位置,它与教科书解决方案相同.要知道存储桶的结束位置,您只需查看下一个存储桶的开始(以恒定时间).

另一种看待这种情况的方法是,它是具有一个修改的教科书实现:每个桶末尾的"下一个"指针指向下一个非空桶的开头.您将立即了解为什么这会改进顺序访问 - 它消除了遍历空桶的成本(其中可能存在负载,因为实现不需要缩小哈希表,只增长它).

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