c++ - 遍历哈希表是如何实现的？

Question

我试图了解如何实现对哈希表的迭代。我只是无法想象。我对这种迭代的速度特别感兴趣。例如：

QHash<int, std::string> hashTable;
...
for (auto it = hashTable.begin(); it != hashTable.end(); ++it)
    std::cout << it.value() << std::endl;

这是O(hashTable.size())手术吗？

我试图挖掘源代码，但找不到正确的定义。

Answer 1

哈希表的一些实现还维护所有条目的链接列表以允许快速迭代（所谓的“链接哈希映射”）。

如果他们不这样做，唯一的方法是遍历哈希表的所有桶，同时也遍历每个桶中的元素。

此操作的速度取决于表格的填充状态。当它非常低时，需要迭代很多空桶，这很浪费时间。当表格填满，并且每个桶中有一个或多个元素时，这几乎就像迭代一个链表。在每个桶只包含一个元素的完美哈希映射上，这就像迭代一个数组。