哈希图通常是用键数组实现的吗？ [已关闭]

Question

许多语言在标准库中或作为内置函数包含哈希图，允许程序员迭代哈希图。例如，在Python中：

d = {"US": "English", "Spain": "Spanish", "France": "French", "Canada": "English"}
for key in d:
    print(key)

或 C++：

#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
        unordered_map <string, string> m;

        m["US"] = "English";
        m["Spain"] = "Spanish";
        m["France"] = "French";
        m["Canada"] = "English";

        for (auto &it: m){
                cout << it.first << endl;
        }
        return 0;
}

Rust 也有类似的东西，而且迭代看起来更像 python。

所以我的问题是：hashmap 实现是否包含可以迭代的键向量，并且要么只给你键，要么在 O(1) 中动态查找值？或者他们是否遍历实际的哈希表（包括空桶）？

我问这个问题是因为在后一种情况下，我自己保存键列表并以这种方式迭代可能比实际使用地图的功能更有效。

Answer 1

所以我的问题是：hashmap 实现是否包含可以迭代的键向量，并且要么只给你键，要么在 O(1) 中动态查找值？或者他们是否遍历实际的哈希表（包括空桶）？

我问这个问题是因为在后一种情况下，我自己保存键列表并以这种方式迭代可能比实际使用地图的功能更有效。

对于这个特定的迭代来说，它会更有效，但存储效率会低很多，并且在迭代值或条目时也可能效率较低：现在你必须散列并查找条目（必须再次存储密钥）在每个项目上。

所以不，迭代哈希图时将迭代条目数组，并跳过空条目。

也可以有密集的条目数组，Python（自 3.6 起）或 Rust 中的

indexmap

就是这种情况，前者专门切换到该布局以提高迭代性能。