哈希表实践根底
- 用来疾速判断某个原生是否在汇合内(疾速查找)
- 哈希函数将传入的key映射到符号表的索引上
- 哈希抵触解决多个key映射到符号表雷同索引上的问题，罕用的解决办法有拉链法和线性探测法
- c++ stl中有四种常见的哈希构造
- 数组
std::array - 汇合
std::setstd::multisetstd::unordered_set - 映射
std::mapstd::multimapstd::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) |