在哈希表中，如何实现对键的迭代？

Question

基本上，我想知道当我 运行 像这样的事情时会发生或可能发生什么：

for key in some_hash_map.keys():
    print(key)

是否只是使用反向哈希函数？

Answer 1

典型的哈希 table 可以实现为一个桶数组，每个桶都有一个条目链表。

哈希查找通过 运行 哈希函数找到正确的桶，然后搜索桶。

迭代键是通过迭代桶实现的，依次搜索每个列表。

如果桶太多，会浪费内存并且迭代很慢。太少，链表变慢。但是我们可以动态调整每个键开销固定的桶数。

如果散列函数不能很好地工作，那么散列将执行得非常糟糕。