共计 456 个字符，预计需要花费 2 分钟才能阅读完成。
哈希表实践根底
- 用来疾速判断某个原生是否在汇合内 (疾速查找)
- 哈希函数将传入的 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) |
正文完