C++中的哈希表

Question

C++中std::map的插入、删除和查找时间复杂度是否为O(log n)？是否可能实现O(1)的哈希表？

- Paul S.

---

在C++11中，有std::unordered_map，如果您有boost，则可以使用boost::unordered_map。 - andre

你似乎误解了std::map是一个哈希表，但它们通常是二叉树。 - Brendan Long

@BrendanLong 当然，我知道它是使用二叉树实现的。但它不就像哈希表一样工作吗？ - Paul S.

哈希表和二叉树可以被改造成提供相同的接口（像 map / unordered_map），但它们内部的实现完全不同。 - Brendan Long

相关链接："哈希表真的可以是O(1)吗？"。 - David Cary

Answer 1

C++ map 的插入/删除/查找时间是O(log n)吗？

是的。

是否可能实现一个O(1)的哈希表？

肯定。标准库也提供了一个，名为std::unordered_map。

- Kos

---

我明白了。那么std:map相对于std:unordered_map有什么优势呢？ - Paul S.

前者是一个有序集合。 - Cheers and hth. - Alf

std::map使用树结构，需要对键进行比较，而std::unordered_map要求键可以被哈希。此外，我不能假设std::unordered_map总是更快，尤其是对于小数据（但如果您认为这很重要，请自行检查）。 - Kos

@Kos unordered_map 也需要其键可比较; 它只是与 map (less) 不同的默认比较器 (equal_to)。 - Praetorian

感谢澄清！（C#已经很好地解决了这个问题，区分了“可比较”（具有某种顺序）和“可等价”。） - Kos

Answer 2

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

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

在实践中，我们采用一个愚蠢的哈希表。对于任何输入键，它返回1。在这种情况下，当发生冲突（即第二次及以后的插入）时，它将不得不进一步链接以找到一些空闲空间。它可以转到下一个存储位置，或者使用链表。

无论如何，在最好的情况下，哈希表是O(1)的（当然，一旦你耗尽了所有的哈希值，这是不切实际的，因为没有无限输出的哈希函数）。在最坏的情况下（例如，使用我完全愚蠢的哈希函数），哈希表是O(n)的，因为您将不得不遍历存储以找到给定哈希的实际值，因为初始值不是正确的值。

- slugonamission

---

hash_map是大多数编译器提供的非标准扩展。标准哈希映射被称为unordered_map。 - Praetorian

Answer 3

std::map 的实现是一棵树。虽然标准没有直接规定，但一些好的书籍说过："很难想象它会是其他什么东西"。这意味着 map 的插入/删除/查找时间为 O(log n)。

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

- Kirill Kobelev

---

我有一个问题。O(0) == O(1)吗？O(0)是否有定义？ - im so confused

我认为O(0)不是一种有效的表示方法。O(1)代表“常数时间”。 - Kirill Kobelev

是的，这只是我在阅读你的回答时想到的一个闲想。谢谢！ - im so confused

O(0) 可能意味着算法在你询问之前就已经为你获取了结果 ;) - slugonamission

@slugonamission 哈哈哈，少数派报告的开端？ - im so confused