c++ 中 set数据结构和hashset数据结构的查询效率

Question

如题所述

Answer 1

在STL中，set是以红黑树（RB-tree）作为底层数据结构的，hash_set是以Hash table（哈希表）作为底层数据结构的。set可以在时间复杂度为O(logN)情况下插入、删除和查找数据。hash_set操作的时间复杂度则比较复杂，这取决于哈希函数和哈希表的负载情况。
一般来说，查询的数据量越大，hash_set的性能优势越明显。

Answer 2

hashset 不是标准c++里面的，set查询是o(log(n)),要是hash的话理想上是o(1),不过要看冲突，这个效率是不稳定的。