C++哈希基础：哈希思想前置铺垫

上一篇我们学习了 map 和 set，我们知道它们底层是红黑树。
虽然红黑树效率不错，但是有没有更快的容器？
这就引出了我们今天要讲的：哈希。
本篇只做铺垫，通俗易懂，为后面 unordered_map、unordered_set 哈希表做准备。

一、为什么需要哈希？

我们之前学的二叉搜索树、红黑树，增删查时间复杂度是 O(logN)。
虽然已经很快，但是能不能做到 O(1) 常数级查找？

想要实现极速查找，就需要用到：
哈希思想（散列）

通俗理解：
给一个数据，通过哈希函数，直接算出它的存放位置。
不需要遍历、不需要比较、不需要走树路径。

二、哈希是什么？

哈希：将任意类型的数据，通过哈希函数，转换成整数下标。

举个通俗易懂的例子：
数组下标是连续整数，我们希望数据能直接映射到下标。
不需要查找，直接一步定位。

简单哈希映射代码示例

#include <iostream>
using namespace std;

// 简单哈希函数
int HashFunc(int key)
{
    // 对数组长度取模，得到下标
    return key % 10;
}

int main()
{
    int arr[10] = {0};

    int num = 26;
    int index = HashFunc(num);

    arr[index] = num;

    cout << "数据" << num << "存放下标：" << index << endl;
    cout << "arr[" << index << "] = " << arr[index] << endl;

    return 0;
}

三、哈希冲突是什么？

理想情况：一个关键字对应一个下标。
现实情况：不同数据算出同一个下标，这就是 哈希冲突。

例如：
26 % 10 = 6
36 % 10 = 6
两个数据抢占同一个位置，产生冲突。

在极端哈希冲突的情况下哈希表的效率会由O（1）降为O（N）

四、树结构容器 和 哈希容器区别

1. map/set：底层红黑树，有序、O(logN)
2. unordered_map/unordered_set：底层哈希表，无序、O(1)

想要有序用树，想要极速用哈希。

总结

1. 哈希核心思想：数据映射下标，一步定位。
2. 哈希最大问题：哈希冲突。
3. 理想情况下哈希容器查询速度远快于红黑树容器。