$\color{blue}{\texttt{C++}}$$\color{orange}{数据结构}\color{}{基础篇目录}$
$\ \ $
$$第四章 \ \ \ \ Hash$$
$\ \ \ $
$Hash$表,说白了就是把一些很复杂的信息映射到一个易于维护的值域内
我们可以先建一个邻接表结构(关于邻接表结构,详见$\large\color{blue}{C}$$\color{Blue}{++}\color{orange}{数据结构}\color{black}{————第三章}$ ),以$Hash$函数的值作为表头数组$head$,映射后$Hash$值相同的放在同一类里,构成一个链表接在对应的表头之后,链表的节点上可以保存原始信息和一些统计数据
$Hash$表主要有两个操作:
- 计算$Hash$函数的值
- 定位到对应链表中进行遍历、比较
如果说原始数据的总数和表头数组的长度都是$O(N)$级别,且$Hash$函数分散均匀,几乎不产生冲突,那么每次操作如查询、统计的时间复杂度期望是$O(1)$的
举个例子
给定一个长度为 $N$ 的数列 $A$ ,统计数列 $A$ 中每个数出现了多少次
这个问题很简单,接下来就给大家演示下如何用 $Hash$ 表做
首先我们设计 $Hash$ 函数为 $HASH(x) = (x\ mod\ P) + 1$ ,其中P为一个较大的素数,但不超过 $N$
很显然,Hash函数把 $A$ 数列分成了 $P$ 类
扫描这 $N$ 个数,定位到 $head[HASH(A[i])]$ 这个表头所指向的链表,如链表中不包含 $A[i]$ ,那么就插入一个新节点 $A[i]$ ,并在这个节点上记录 $A[i]$ 出现次数 +1
最后这个算法的时间复杂度可以近似 $O(N)$
字符串Hash
$\ \ $
字符串$Hash$函数可以把一个任意长度的字符串映射成一个非负整数,且冲突率极低
如何计算一个字符串的$Hash$值呢?
先取一个固定值$P$,把这个字符串看作是一个$P$进制数,并给每种字符分配一个大于0的数值,代表每一种字符
再取一定值$M$,求出该$P$进制数对取模$M$的值,这就是这个字符串的$Hash$值
这里建议$P$取$131$或$13331$,这时冲突的概率会很小
$M$可以取$2^{64}$,用$unsigned\ long\ long$ 存储$Hash$值,这样可以避免溢出,如果溢出了就会自动对$2^{64}$进行取模,避免了低效的$%$运算
对于字符串的各种操作,这里简单讲一下:
我们先设字符串$S$的$Hash$值为$HASH(S)$
- 在$S$后面加上一个字符$c$,那么新字符串的$Hash$值就为 $ HASH( S + c ) = ( HASH( s ) * P + value [ c ] ) % M $ ,其中乘$P$就相当于$P$进制中的左移运算,value[c]为我们自己为$c$取得一个数值
- 在$S$后面加上另一个字符串$T$,那么字符串$T$的$Hush$就等于 $ HASH( T ) = ( HASH( S + T ) - HASH( S ) * P^{length(T)} ) % M $ ,这相当于$P$进制下在$S$后补$0$的方式,把$S$左移知道与$T$对齐,然后再二者相减就得到了$H(T)$
还是举个栗例子
假设$S = ” AK ” , c = ‘ 2 ‘ , T = ” IOI “$啊这
然后我们定义$ ‘ A ‘ = 1 ; ‘ K ‘ = 2 ; ‘ 2 ‘ = 3 ; ‘ I ‘ = 4 ; ‘ O ‘ = 5 $
$S$表示为$P$进制数$ 1\ 2 $
$HASH(S) = $
$HASH(c + S) = 3 * P^2 + 1 * P + 2$
$S + T$表示为$P$进制数$ 1\ 2\ 4\ 5\ 4 $
$HASH(S + T) = 1 * P^4 + 2 * P^3 + 4 * P^2 + 5 * P + 4$
$S$在$P$进制下左移$length(T)$位:$1 2 0 0 0$
两者相减得到$T$表示为$P$进制数为$4 5 4$
$HASH(T) = HASH(S + T) - (1 * P + 2) = 4 * P^2 + 5 * P + 4$
$\ \ $
通过上述两种操作,我们可以在$O(N)$的时间里预处理出需要处理的字符串的所有前缀$Hash$值
在$O(1)$的时间内查询它的任意子串的$Hash$值
哇出新了
暑假比较空,没事了就可以更两篇