哈希表
将一个大范围空间压缩到一个较小的空间
前面用的方式是离散化（其实是一种特别的哈希 要求保序）
这里介绍一般的哈希
思路就是 将一个大区间内所有的数
通过一个哈希函数映射到一个小区间中
那就势必要考虑两个问题
哈希函数怎么设
既然是从大区间映射到小区间 就一定会出现冲突问题 怎么解决冲突
对于第一个问题：
最简单的 要把一堆数映射到某特定范围 的方法
就是取模
n%7 的取值为[0,6]
那么很简单的 要把原区间的数都映射到一个新区间
就把原区间的所有数 都与新区间的大小相近的一个数去取模
这样就能保证每个数都能在新区域有个投射
引入两个子问题：
这个数到底取多少
将取模结果怎么映射成下标
这个数取多少
模的这个数最好要是质数 且要离2的整数次幂尽可能远 （这样冲突概率最小）
那这里就直接选 大于新数组大小的第一个质数
可以使用
找到大于区间的第一个质数
for(int i=100000;;i++)
{
bool flag=true;
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
flag=false;
break;
}
}
if(flag)
{
cout<<i<<endl;
break;
}
}
找到大于区间的第一个质数（10000->100003）
将取模结果怎么映射成下标
若将-10^9~10^9的数映射到0~10^5
就要考虑一个问题
因为c++中 负数取模的结果为负数
而显然负数是不能作为下标的 所以得想办法把它变成正数
可以采用 先取模 再加上N 再取模N的方法
即
\(k=(x mod N+N)%N\)那么得到的要插入的地方就是h[k]
对于第二个问题：
秉承一个萝卜一个坑的原则 如果两个数经过处理后 要在一个坑 这就冲突了
该怎么解决？ 要么换一个坑（开放寻址法） 要么就排队（拉链法） 比较推荐拉链法 可以加深对数组模拟链表的理解 以及后面的图中邻接表也是类似存储 y总推荐开放寻址 看自己吧
开放寻址法
只用一个数组去存储映射后的关系
如果冲突了 就继续往后找 直到找到一个坑没被占
那这样的话 数组长度就应该比理想情况要大了 大多少 最好开两到三倍
对于这么一个结构来说 核心就是查找了
如果得到一个k 从h[k]开始去找
如果当前位置有数 并且就为x 那就找到了x
如果当前位置有数 但不是x 那就往后找
如果当前位置没数 那就x不存在
（执行删除还是返回没找到看操作要求 核心就是一个find）
怎么表示该某位置没元素？ 全初始化成无穷大
→ 两个相关小专题见 04-刷题小贴士：无穷大（为什么取 0x3f3f3f3f）、memset（按字节赋值的原理）
拉链法
就是把一个数处理后 得到一个下标位置
但如果这个下标位置已经有元素了
那就把它链在后面
但是这里我们还是用数组模拟的链表
嗯 一个e放数据本身 一个ne放下一个位置的下标
那就是这样咯？
在一维的每一个结点的后面都接两个数组
其实没必要
因为一维中存的不过是一个下标 作用就是单链表中的head
各个域中的head并不冲突 它只需要根据下标找到e数组中的第一个数
再链着ne找下一个数 直到所有
所以 完全可以把所有的数都存放在一个e、ne中
不同域去就相当于不同的head 去进行一个索引
嗯 把一个数组拆成多个链
把一维的每一个位置都当做head即可 不过是对一个数组有多个head访问罢了
那么既然是当head用
所以初始化就是要把所有的值都赋为-1表示空
memset(h,-1,sizeof h);
插入一个点 就是头插
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
遍历也很简单 从头开始 i=h[k]
直到结束i!=-1 每次往后寻 i=ne[i]
for(int i=h[k];i!=-1;i=ne[i])
💬 评论