c++ - C++中的哈希表

Question

是 C++ 的插入/删除/查找时间std::map O(log n)吗？是否可以实现O(1)哈希表？

Answer 1

C++ 映射的插入/删除/查找时间是否为 O(log n)？

是的。

是否可以实现 O(1) 哈希表？

确实。标准库还提供了一个std::unordered_map.

Answer 2

C++ 有一个unordered_map类型。STL 还包含一个hash_map类型，尽管它不在 C++ 标准库中。

现在，对于一些算法理论。在完美的条件下实现一个 O(1) 的哈希表是可能的，从技术上讲，哈希表是 O(1) 的插入和查找。在这种情况下，完美的条件是哈希函数必须是完美的（即无冲突），并且您有无限的存储空间。

在实践中，让我们使用一个哑哈希表。对于任何输入键，它返回 1。在这种情况下，当发生冲突时（即在第二次和随后的插入中），它必须进一步链接以找到一些空闲空间。它可以转到下一个存储位置，也可以为此使用链表。

无论如何，在最好的情况下，是的，哈希表是 O(1) （当然，直到你用尽了所有的哈希值，因为拥有无限量输出的哈希函数是不切实际的）。在最坏的情况下（例如，使用我完全愚蠢的哈希函数），哈希表是 O(n)，因为您必须遍历存储才能从给定的哈希中找到您的实际值，因为初始值不是正确的值。

Answer 3

的实现std::map是一棵树。这没有在标准中直接指定，但正如一些好书所说："It is difficult to imagine that it can be anything else". 这意味着 map 的插入/删除/查找时间是O(log n)。

经典哈希表的查找时间为 O(n/num_slots)。一旦表中的预期项目数与插槽数相当，您将拥有saturated O(1)。