Hash

Hash及应用

任务

给定n个整数，请从小到大输出其中前m大的数
输入：每组测试数据有两行，第一行有两个整数n,m（0 < n, m < 1000000)，第二行有n个各相同，且都处于区间[0, 1000000]的整数
输出：对每组测试数据按从小到大顺序输出前m大的数
思想：桶排序
将数据值与它的位置建立某种关系，使得存储完毕，则排序完毕

加强版

第二行包含n个各不相同，且都处于区间[-500000, 500000]

再加强版

如果整数允许相同怎么办

Hash表（散列表）基本原理

使用一个下标范围比较大（数据大小的五到十倍）的数组来存储元素，一般通过设计一个函数($Hash$函数，即散列函数)，使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。
好处：$O(1)$

Hash函数构造：除余法

$H(k)= k\%p$ （$p$一般选取适当大的素数）

冲突

由于不能保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况：
“对于不同的元素关键字，$Hash$函数计算出了相同的函数值”， 这就是产生了所谓的“冲突”
换句话说，冲突就是$Hash$函数把不同的元素分在了相同的下标单元

冲突解决

常用方法：线性探测再散列技术
即：当 $h(k)$ 位置已经储存有元素的时候，依次探查 $(h(k) + i)\%S, i = 1, 2, 3...$，直到找到空的储存单元为止，其中 $S$ 为数组长度
特别地，如果将数组扫描一圈仍未发现空单元，则说明 $Hash$ 表已满，这会带来麻烦，但是该情况完全可以通过扩大数组范围来避免，选择地址可以在 $H()$ 函数内一起求了

bool vis[N]; // 占位
int val[N]; // 某个地址存放的数值
inline int Hash ( int x ) {
    int id = (x % p + p) % p; // 选择非零地址
    while ( num[id] && val[id] != x ) id = (id + 1) % p;
    return id;
}

基本操作

$Hash$表初始化（ $0$ 或 $-1$ 或其它）
哈希函数运算
插入元素（包含冲突解决）
定位（需考虑可能冲突的情况）

应用——字符串Hash

作用

可以将一个字符串变成一个前缀数值
而其子串也能快速利用前缀数值求出其区间数值

构造方法：进制表示法

我们和十进制数字求前缀一样
我们对字符串设置一个进制
进制大小根据字符串中不同的字符个数来定，常见的有 $31$、$131$ 等

const int base = 31;
const int p = 1e9 + 7;
string s;
ll hash[N];

hash[0] = s[0] - 'a';
for ( int i = 1; i < s.size(); i ++ ) {
    hash[i] = hash[i - 1] * (s[i] - 'a') % p;
}

获取方法：区间积

前缀和求区间用减法，这里当然用除法
不过一般都是模意义下的，所以我们要逆元获取

inline int inv ( int x ) {...} // 逆元
inline int getHash ( int l, int r ) {
    if ( l ) return hash[r] * inv(hash[l - 1]) % mod;
    else return hash[r];
}

例题

个人题单传送门