C++中的哈希表

Question

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

Answer 1

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

是.

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

当然.标准库还提供了一个std::unordered_map.

前者是有序的集合 (4认同)
`std :: map`使用树并且需要它的键是可比较的,而`std :: unordered_map`则要求它的键是可清除的.另外我不认为`std :: unordered_map`总是更快,尤其是.对于小数据(但不要接受我的话,并检查你是否认为这很重要). (4认同)

Answer 2

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

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

在实践中,让我们采取一个愚蠢的哈希表.对于任何输入键,它返回1.在这种情况下,当发生碰撞时(即在第二次和后续插入时),它将必须进一步链接以找到一些空闲空间.它可以转到下一个存储位置,也可以使用链接列表.

在任何情况下,在最好的情况下,是的,哈希表是O(1)(当然,直到你已经耗尽了所有的哈希值,因为具有无限量输出的哈希函数是不切实际的).在最坏的情况下(例如,使用我完全哑的哈希函数),哈希表是O(n),因为你必须遍历存储以便从给定的哈希中找到你的实际值,因为初始值不是正确的价值.