【算法杂谈】离散化与哈希

**离散化** 离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。 通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。 **用法** 有些数据本身很大， 自身无法作为数组的下标保存对应的属性，如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。 当我们只关心数据之间的大小关系而不关心他们的具体数值时，就可以将他们映射到$[1,size]$这个区间上(离散化)。 **用途** 缩小值域。 **例题** 给定一个白色数轴，$q$次操作，每次给定一个区间$[l,r]$，把区间染黑（多次染黑效果不变）。求最后黑色区间的总长度。 $1≤q≤20000,-2^{31}≤l≤r<2^{31}$ 如果数轴的范围与$n$同阶，问题可以被简单地转化为一个数列差分问题，容易解决。现在我们的问题是如何把数轴的范围映射到一个下标可以开的数组的范围内。 注意到，我们实际修改的点只有$2n$个。我们可以将这$2n$个点映射到$[1,2n]$这个区间内。对于一个数字$x$，如果它在这$2n$个数字中是第$i$大，则我们将之映射成$i$。也就是$f:S\to[1,2n]$，$f(x)=rank(x)$。显然这是个双射，所以我们可以通过逆映射将之映射回去：$f^{-1}(rank(x))=x$。 上述将出现的$2n$个数映射到$[1,2n]$区间上的方法称为离散化。为了介绍离散化，我们先介绍两个STL。 [**去重函数(003)/下界函数(004)**](https://www.luogu.com.cn/blog/fsx/post-stl) 有了上述两个函数，我们可以介绍将$n$个数离散化的算法： 1. 先将需要被离散化的数组拷贝到一个新数组```tmp```中，接下来的操作都在```tmp```中进行。 2. 用```sort```先将数组排序（因为后两步都要求数列有序，所以必须排序） 3. 使用```unique```函数将数组去重，算出不同的数的个数$k$。 4. 对于原数列中的每个数，在去重后的无重数列上做```lower_bound```，求出其rank。这里rank实际上无法开成下标为原值域的数组，所以我们定义rank[i]表示a[i]的rank，其中$a$是需要被离散化的数组。 显然，离散化的时间复杂度为$\text{O}(n\ log\ n)$。 离散化结束后，如何通过离散化后的值还原回原值？```tmp```数组里存储的是去重后的数列，也就是说```tmp[i]```就是排名为$i$的数。因此，```x```还原后就是```tmp[x]```。 回到题目上来。 我们先将坐标离散化。因为统计的是线段长度，所以我们将线段编号（而不是将坐标编号） 也即，```tmp[1]```和```tmp[2]```之间是$1$号线段，```tmp[2]```和```tmp[3]```之间是$2$号线段$...\ ...$考虑一个$[l,r]$(离散化后）的染色，其实是给编号为$[l,r-1]$的线段染色。所以差分时令$a[l]++,a[r]--$即可。时间复杂度为$\text{O}(n\ log\ n)$。瓶颈在离散化。 ```cpp #include<algorithm> #include<iostream> #include<cstdio> #define ll long long using namespace std; const int N=4e4+10; int n,k,l[N],r[N],alls[N],d[N]; ll ans; int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d%d",&l[i],&r[i]); alls[i]=l[i];alls[i+n]=r[i]; } sort(alls+1,alls+(n<<1)+1); k=unique(alls+1,alls+(n<<1)+1)-(alls+1); for(int i=1;i<=n;++i){ ++d[lower_bound(alls+1,alls+k+1,l[i])-alls]; --d[lower_bound(alls+1,alls+k+1,r[i])-alls]; } for(int i=1;i<=k;++i){ d[i]+=d[i-1]; if(d[i])ans+=alls[i+1]-alls[i]; } printf("%lld",ans); return 0; } ``` **哈希** Hash，一般译作散列、杂凑，或音译为哈希。 把任意长度的输入（又叫做预映射）通过散列算法变换成固定长度的输出，该输出就是散列值，这种转换就是一种压缩映射。 也就是说，散列值的空间通常远小于输入的空间。 但是，不同的输入可能会散列成相同的输出（哈希冲突），所以不可能从散列值来确定唯一的输入值。 简单地说就是一种将任意长度的消息压缩到某一固定长度的消息摘要函数。 **自然溢出** 由于哈希涉及大量取模，所以有可能有常数问题，实践中可以用自然溢出代替，即采用unsigned long long类型运算，相当于自动对$2^{64}$取模，同时还能提高正确率。 但可以被构造卡，需慎重。 **生日悖论** 生日悖论是指在不少于23个人中至少有两人生日相同的概率大于50%。 从引起逻辑矛盾的角度来说，生日悖论是一种 “佯谬”。 但这个数学事实十分反直觉，故称之为一个悖论。 生日悖论的数学理论被应用于设计密码学攻击方法——生日攻击。 生日悖论普遍应用于检测哈希函数：N位长度的哈希表可能发生碰撞测试次数不是2N次而是只有2N/2次。 这一结论被应用到破解密码哈希函数的“生日攻击”中。 **哈希表** 哈希表，也称散列表，是一种高效的数据结构。 它的最大优点就是把数据存储和查找所消耗的时间大大降低，几乎可以看成是O（1）的，而代价是消耗比较多的内存。 在当前竞赛可利用内存空间越来越多，程序运行时间控制得越来越紧的形势下，“以空间换时间”的做法还是值得的。 构建时间复杂度为O(n)  **构造方法** **求模取余法（除留余数法）** 取关键字key被某个不大于散列表表长m的数p除后所得的余数为散列地址,即H(key)=key mod p，p<=m。 不仅可以对关键字直接取模，也可在折叠、平方取中（平方取中法）等运算之后取模。 对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。 余数（哈希地址）总是循环出现，呈周期性变化。 **乘积取整法**  **哈希函数H(key)** 记录关键字与其存储地址之间的映射关系H(key)把某个较大的集合P映射到另一个较小的集合Q中。 哈希函数H(key)值，叫哈希地址：哈希表中该记录存储位置的下标。 **哈希冲突** 当两个不同的数据哈希值相同时，就会发生冲突（collision）。 **解决方式** **开放地址法** **链地址法/拉链法** 即将哈希值相同的数据存在一个链表当中。 当查找到这个链表时，采用线性查找的方法。  ```cpp //链地址法 vector<int>hash_array[N];//hash_array：每个位置用一个vector来维护 void pushe(int x){ int y=x%N;//计算初始位置 for(int i=0;i<hash_array[y].size();i++) if(hash_array[y][i]==x){ //如果之前已经出现过了 cout<<x<<" has occured before!"<<endl; return;//标记已经出现过 } //如果之前没有出现过，将x加入表中 hash_array[y].push_back(x); cout<<x<<" inserted."<<endl; } ``` **线性探测法/顺序寻址法** 发现位置被占了，就继续找后面的位置。 如果后面位置空闲则直接占用； 后面位置也被占用，则一直往后遍历查找，直到找到空闲位置为止。 查找时则同理，若当前位置没有找到，则向后查找，直到出现两种情况之一。 有空位：那就没出现过。 查询到一个相等的数：说明已经出现过了。 **双向平方试判（双平方探测法）** 为了解决二次聚集现象发明了双平方探测法 当冲突产生时 向该冲突点的双向以步长$i^2(1\ 4\ 9\ 16\ 25...)$ 探测若保证散列表的长度是素数且满足4K+3则可以遍历整个散列表从而不存在二次聚集现象。 **哈希查找** 哈希查找是一种按关键字编址的快速检索方法。 哈希查找通过对记录的关键字的值进行某种运算，直接求出记录的地址。 因为关键字到地址直接转换，无需反复比较，所以速度较快。 核心不在于如何“比较”，而在于如何“计算”。 单次查找复杂度为O(1)。   **过程** 由给定的关键字key，根据哈希函数计算出对应的哈希地址H(key)。 根据H(key)直接找到该记录的存储位置。 本质是先将待查数据映射成一个哈希值，然后查找具有这个哈希值的数据。 其核心是设计哈希函数，并构建哈希表。   **[基于哈希实现的映射——unordered_map（类似于哈希表）](https://www.luogu.com.cn/blog/fsx/post-stl)** **字符串哈希** 核心思想：通过比较哈希值是否相等来比较两个字符串是否相等。 有m个字符串，总长为S，q次询问两个字符串是否完全一样。（数据范围$10^5$） 一个相对普适的做法是这样的： 将这个字符串（假设只有小写字母）视为一个27（基底）进制数，将a看作1，b看作2，依此类推， 比如“abca”看作$1×27^3+2×27^2+3×27^1+1×27^0$。 但这样在字符串较大时数字会很大，存不下来。 一个欺骗性的方法是找一个较大的数P（模数，最好是大质数），只记录转换后数字对P取模的结果。   **注意** 不能将字符映射为0，否则’a’和’aa’的哈希值相同。 取的bas要和P互质，否则bas的指数足够大时模P就=0，那一位就没用了。（即gcd(bas,P)=1） 基底bas>字符种数 **哈希冲突** 由于bas的缘故，可以想象两个字符串有相同的哈希值很困难。 可以证明这么做出问题（即哈希值相等但是字符串不同）的概率是$O(\frac{1}{\sqrt{p}})$的，一般情况下够用了。 但是有些时候可能会有问题（错误概率不够小），可以通过找两组bas和P来解决（双哈希）。 **相关题目** **子串哈希值提取** （pre：前缀） 子串可视为前缀的后缀/后缀的前缀。 给定一个长位n字符串s，q次询问两个子串s1和s2是否相同。 拓展一下刚刚的哈希算法。 考虑对字符串的每个前缀计算其哈希值，那么对于子串[l, r],其哈希值可用以下式子计算（计算方式可能不同）。  $H=(s[r]-s[l-1]×bas^{r-l+1})$%$mod$   ```cpp string s;//s为字符串 int f[N],g[N];//f为前缀哈希值，g[i]为D的i次方 void prehash(int n){ //预处理哈希值 //预处理时，注意到数字可能很大，对一个数MD取模 f[0]=s[0];//f前缀和预处理 for(int i=1;i<=n;i++) f[i]=(1LL*f[i-1]*D+s[i-1])%MD; g[0]=1;//g：D次方预处理 for(int i=1;i<=n;i++) g[i]=1LL*g[i-1]*D%MD; } ``` ```cpp int hash(int l,int r){ //计算区间[l,r]的哈希值 int a=f[r]; int b=1LL*f[l-1]*g[r-l+1]%MD;//记得乘上次方 return (a-b+MD)%MD;//前缀和相减 //有可能结果小于0，加上一个MD将其变为正数 } if(hash(a,b)==hash(c,d))//字符串[a,b]与字符串[c,d]匹配 ``` **~~哈分加二希~~ 哈希加二分** 求LCP（最长公共前缀） 给一个字符串 S，多次询问两个后缀的最长公共前缀(LCP)。 **前置知识** maxsuf（最大后缀） maxpre（最大前缀） **方法** 二分加哈希 左边的哈希值一样，就在右边继续求哈希， 左边的哈希值不一样，就在左边继续求哈希， 直到求出LCP。 **推荐的二分写法**  **哈希与回文串** 给一个长为n的串s，q次询问一个子串是否是回文串。 回文串就是从左往右读和从右往左读，结果一样的串。 那么正着做一遍哈希，倒着读做一遍哈希，提取两遍子串哈希值即可。