哈希表实现认知: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 等工程替代只建立认知
  • 标准容器选择与高性能第三方容器选择是不同层次问题