我遇到了一个很好的问题,它很相似,但完全不一样,因为它谈到了 Java,它具有不同的哈希表实现,凭借同步的访问器/mutators: What are the differences between a HashMap and a Hashtable in Java?
那么set
和unordered_set
的C++实现有什么区别呢?
这个问题当然可以扩展到 map
vs unordered_map
等等其他 C++ 容器。
这是我的初步评估:
set
:虽然标准没有明确要求将其实现为树,但时间复杂性约束要求其查找/插入操作,这意味着它将始终以树的形式实现.
通常作为 RB 树(如 GCC 4.8 中所见),它是高度平衡的。
由于它们是高度平衡的,因此它们对于 find()
优点:紧凑(与其他 DS 相比)
Con:访问时间复杂度为 O(lg n)
unordered_set
:虽然标准没有明确要求将其实现为树,但时间复杂性约束要求其查找/插入操作,这意味着它将始终作为哈希实现-表。
优点:
- 更快( promise 为搜索摊销 O(1))
- 与 tree-DS 相比,易于将基本原语转换为线程安全的
缺点:
- 查找不保证是 O(1)。理论上最坏的情况是 O(n)。
- 不像树那么紧凑(实际上,负载因子永远不会是 1)。
注意: 哈希表的 O(1) 来自没有冲突的假设。即使负载因子为 0.5,每第二个变量插入都会导致碰撞。 可以观察到,哈希表的负载因子与访问其中元素所需的操作数成反比。我们减少了更多#operations,更稀疏的哈希表。当存储的元素的大小与指针相当时,开销是相当大的。
我是否错过了应该知道的用于性能分析的 map /集之间的任何区别?
最佳答案
我想你通常已经回答了你自己的问题,但是,这个:
Not as compact as tree. (for practical purposes load factors is never 1)
不一定是真的。类型为 T
的树的每个节点(我们假设它是红黑树)使用的空间至少等于 2 * pointer_size + sizeof(T) + sizeof(bool)
.这可能是 3 * pointer size
取决于树是否包含 parent
每个树节点的指针。
将此与 HashMap 进行比较:每个 HashMap 都会浪费数组空间,因为 load factor < 1
正如你所说。然而,假设 HashMap 使用单链表进行链接(实际上,没有真正的理由不这样做),插入的每个元素只需要 sizeof(T) + pointer size
.
请注意,此分析忽略了可能来自对齐使用的额外空间的任何开销。
对于任何元素 T
它具有小尺寸(因此,任何基本类型),指针的大小和其他开销占主导地位。负载系数为 > 0.5
(例如)std::unordered_set
确实可能比等效的 std::set
消耗更少的内存.
另一个重要的缺失点是迭代 std::set
保证根据给定的比较函数生成从最小到最大的排序,同时遍历 std::unordered_set
将以“随机”顺序返回值。
关于c++ - C++ 中的 set 和 unordered_set 有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16075890/