哈希表理论基础:
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/哈希表理论基础.md
哈希表题目总结:
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/哈希表总结.md
当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。
这里数组就没啥可说的了,我们来看一下set。
在C++中,set 和 map 分别提供以下三种数据结构:
集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(log n) | O(log n) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |