【C++---哈希表】哈希表的魅力，不仅在于其高效与便捷，更在于其背后所蕴含的深刻哲理。它告诉我们，即使面对再复杂、再混乱的世界，只要我们用心去寻找、去创造，总能找到一种方法，将其变得有序而美好。

哈希表

• 1 unordered_map和unordered_set的使⽤
• • 1.1 unordered_set和unordered_multiset参考⽂档
  • 1.2 unordered_set类的介绍
  • 1.3unordered_set和set的差异
  • 1.4 unordered_map和map的使⽤差异
  • 2 哈希表实现
  • • 2.1 哈希概念
    • 2.2 直接定址法
    • 2.3 哈希冲突
    • 2.4 负载因子
    • 2.5 将关键字转为整数
    • 2.6 哈希函数
    • • 2.6.1 哈希函数之除法散列法
      • 2.7 哈希的防御措施
      • 2.8 开放定址法
      • • 2.8.1 开放定址法代码实现
        • 2.9 链地址法

          

          1 unordered_map和unordered_set的使⽤

          在介绍哈希表之前，我们先了解下unordered_map和unordered_set

          1.1 unordered_set和unordered_multiset参考⽂档

          链接: 参考⽂档

          1.2 unordered_set类的介绍

          

          这里的unordered_set其实与set相似，只不过底层实现是不一样，还有其他特殊的不同.
          不过他们大部分功能是相同的。
          

          unordered_set的声明如下，Key就是unordered_set底层关键字的类型

          • unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key转成整形的仿函数传给第⼆个模板参数

          ---

          • unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数

          ---

          • unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第四个参数。

          ---

          • ⼀般情况下，我们都不需要传后三个模板参数

          ---

          • unordered_set底层是⽤哈希桶实现，增删查平均效率是 ，迭代器遍历不再有序，为了跟set区分，所以取名unordered_set。O(1)

          ---

          • 前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不同，有⼀些性能和使⽤的差异.

          template  class unordered_set;
          

          1.3unordered_set和set的差异

          • 查看⽂档我们会发现unordered_set的⽀持增删查且跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不再赘述和演⽰了。

          ---

          • unordered_set和set的第⼀个差异是对key的要求不同，set要求Key⽀持⼩于⽐较，⽽unordered_set要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_set的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

          ---

          •unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

          ---

          •unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删查改更快⼀些，因为红⿊树增删查改效率是

          ,⽽哈希表增删查平均效率是 ，具体可以参看下⾯代码的演⽰的对⽐差异。

          

          #include
          #include
          #include
          using namespace std;
          int test_set2()
          {
          	const size_t N = 1000000;
          	unordered_set us;
          	set s;
          	vector v;
          	v.reserve(N);
          	srand(time(0));
          	for (size_t i = 0; i