std::unordered_map 如何确定特定键在散列 table 中的位置？

Question

文档提到 std::unordered_map 使用散列 table。它如何实现对散列 table 中特定键的 O(1) 查找？我能想到的唯一方法是将每个键存储在一个地址，该地址是根据它所持有的数据的哈希值计算得出的。如果是这种情况，它如何将所有密钥在内存中保持在一起，以免很快用完？此外，如果使用多个 std::unordered_map 怎么办？该实现如何保证没有两个映射会计算归结为同一地址的哈希值？

Answer 1

通常情况下，哈希映射会在内部保存一个桶数组。另一方面，桶是条目列表。所以像这样：

template<class TKey, class TValue>
class HashMap {
    vector<vector<pair<TKey, TValue>>> Buckets;
};

然后当你进行查找时，它只是获取密钥，计算它的散列，比如 hash，转到 Buckets[hash % Buckets.size]，类型为 vector<pair<TKey,TValue>> 并执行线性搜索它。这使得 amortized（平均）查找复杂度不变，而在最坏的情况下（例如糟糕的散列函数）它是线性的。事实上，这是您使用 unordered_map.

获得的保证

请注意，当您添加元素时（甚至可能在您删除元素时），顶级向量最终会增长，以允许更多条目并避免冲突。在这种情况下可能会发生重新散列。因此 adding/removing 元素并不微不足道，有时可能会很昂贵。

另请注意，由于 vector 在引擎盖下在堆上分配内存，因此使用多个映射没有问题。他们什么都不分享（好吧，他们可能会分享一些东西，但这不会影响行为）。但即使实现不使用 vector（这不是强制性的，它只是一个示例），也必须使用某种形式的动态 malloc 来保证这一点。

Answer 2

O(1) 并不意味着算法的复杂性是“一次性”，或者，在这种情况下，必须根据其键通过某种形式的单次查找来检索映射中的值.

O(1)真正的意思是O(amortized constant)，即：完成需要一定的时间，平均.

无序映射的一种可能实现方式是散列 table 包含具有相同散列键的所有值的链表，无序映射动态调整散列的大小 table，如所须。偶尔的地图查找完全有可能必须搜索一个小链表才能找到正确的哈希键。此外，偶尔，插入或删除操作会花费额外的时间来重新散列整个无序映射。

如果您在参考资料中查找无序映射方法的详细信息material，您会发现它明确提到如果修改触发重新散列，无序映射的所有现有方法都会失效。

但是，平均，无序地图查找预计需要花费固定的时间。

std::unordered_map 如何确定特定键在散列 table 中的位置？

How does std::unordered_map determine the location of a specific key in a hash table?

c++

hash

unordered-map

hashtable