哈希表实现认知:Separate Chaining、Open Addressing 与标准边界 | STL
本章覆盖:bucket interface 暗示标准 unordered container 的抽象模型;主流标准库常使用 bucket / chaining 风格实现;open addressing 是常见哈希表技术,但标准 unordered_map 实现自由度受接口语义约束;collision resolution;bucket array;node allocation;flat hash map / robin hood hashing 属于非标准库实现生态;Abseil flat_hash_map 等工程替代只建立认知;标准容器选择与高性能第三方容器选择是不同层次问题。
本章知识点
- bucket interface 暗示标准 unordered container 的抽象模型
- 主流标准库常使用 bucket / chaining 风格实现
- open addressing 是常见哈希表技术,但标准 unordered_map 实现自由度受接口语义约束
- collision resolution
- bucket array
- node allocation
- flat hash map / robin hood hashing 属于非标准库实现生态
- Abseil flat_hash_map 等工程替代只建立认知
- 标准容器选择与高性能第三方容器选择是不同层次问题