【C++杂货铺】一文带你走进哈希：哈希冲突 | 哈希函数 | 闭散列 | 开散列

文章目录

• 一、unordered 系列关联式容器
• 二、unordered_map
• • 1.1 unordered_map 介绍
  • 1.2 unordered_map 的接口说明
  • • 1.2.1 unordered_map 的构造
    • 1.2.2 unordered_map 的容量
    • 1.2.3 unordered_map 的迭代器
    • 1.2.4 unordered_map 的元素访问
    • 1.2.5 unordered_map 的查询
    • 1.2.6 unordered_map 的修改操作
    • 1.2.7 unordered_map 的桶操作
• 三、底层结构
• • 3.1 哈希概念
  • 3.2 哈希冲突
  • 3.3 哈希函数
  • • 3.3.1 直接定值法----(常用)
    • 3.3.2 除留余数法----(常用)
    • 3.3.3 平方取中法----(了解)
    • 3.3.4 折叠法----(了解）
    • 3.3.5 随机数法----(了解)
    • 3.3.6 数学分析法----(了解)
  • 3.4 哈希冲突解决
  • • 3.4.1 闭散列
    • • 3.4.1.1 线性探测
      • 3.4.1.2 闭散列（开放定址法）模拟实现
      • 3.4.1.3 二次探测
    • 3.4.2 开散列
    • • 3.4.2.1 开散列模拟实现
• 四、模拟实现 unordered_set 和 unordered_map
• • 4.1 哈希表的改造
  • • 4.1.1 模板参数列表的改造
    • 4.1.2 增加迭代器操作
    • 4.1.3 修改后的哈希表
  • 4.2 unordered_set 模拟实现
  • 4.3 unordered_map 模拟实现
• 五、结语

一、unordered 系列关联式容器

在 C++98 中，STL 提供了底层为红黑树结构的一些列关联式容器，在查询时效率可以达到 $O(l$