关于leetcode:Leetcode刷题笔记哈希
- 用来疾速判断某个原生是否在汇合内 (疾速查找)
- 哈希函数将传入的 key 映射到符号表的索引上
- 哈希抵触解决多个 key 映射到符号表雷同索引上的问题，罕用的解决办法有拉链法和线性探测法
- c++ stl 中有四种常见的哈希构造
- 数组
std::array
- 汇合
std::set std::multiset std::unordered_set
- 映射
std::map std::multimap std::unordered_map
| 汇合 |
底层实现 |
是否有序 |
增删查的效率 |
std::set |
RB-Tree |
是 |
O(logn) |
std::multiset |
RB-Tree |
是 |
O(logn) |
std::unordered_set |
Hash |
否 |
O(1) |
std::unordered_multiset |
Hash |
否 |
O(1) |
| 映射 |
底层实现 |
是否有序 |
增删查的效率 |
std::map |
RB-Tree |
是 |
O(logn) |
std::multimap |
RB-Tree |
是 |
O(logn) |
std::unordered_map |
Hash |
否 |
O(1) |
std::unordered_multimap |
Hash |
否 |
O(1) |