Hash 哈希(上)

时间：2022-01-31 20:22:28

Hash 哈希(上)

简介

Hash，又称散列，它通过对数据进行计算，得出该数据的对应位置，使得数据和存放位置相对应，从而完成高效的查找。

Hash函数的构造

取余法

用关键字\(k\)除以\(M\)，取余数作为地址。

\[\operatorname h(k)=k \bmod M
\]

经验上\(P\)可以为\(k\)的取值可能数的1~2倍范围内的素数或\(k\)的取值可能数本身。

这类函数主要用于整数。

乘积取整法

用关键字\(k\)乘一个在\((0,1)\)中的实数\(A\)（最好是无理数），取其小数部分，乘\(M\)并取整，作为地址。

\[\operatorname h(k)=\left\lfloor{M(kA\bmod1)}\right\rfloor
\]

经验上\(A\)可以为\(\dfrac{\sqrt{5}-1}{2}\)。

这类函数主要用于小数。

其他方法

  • 自身函数：取\(k\)的某个线性函数值作为地址。
\[\operatorname h(k)=a\times k+b
\]
  • 平方取中法：将\(k\)平方后取中间几位作为地址。
  • 折叠法：将\(k\)分成位数相等的几段，但最后一段可以不同，最后相加作为地址。

冲突的处理

大部分的散列表无法避免冲突(废话) 。因此需要一些数据结构来解决这些冲突。

挂链法

顾名思义，当出现冲突时，用链表将这两个关键字连起来。看看代码有点像向量存图：

const int array_size=1e5+5;//数组大小

vector<int>lis[array_size];

void get_hash(int key)//加入一个值为key的元素

{

	int buc=f(key);

	lis[buc].push_back(key);

}

bool check(int key)//查找一个元素是否存在于Hash表中

{

	int buc=f(key);

	for(int i=0;i<lis[buc].size();i++)

		if(lis[buc][i]==key)

			return true;

	return false;

}

在键值均匀分布的前提下，挂链法操作的时间复杂度为\(O(n\texttt{length}(\texttt{Hash table}))\)。

开放定址法

这种方法将所有元素直接存于散列表中，因此散列表大小不能小于元素个数。开放定址法中有一个特殊的函数\(H(x,k)\)，指明如果前\(k\)次访问失败，下一次应访问哪一个位置。这个函数有三种构造方式：

线性探查法

\[\operatorname H(x,k)=(x+1)\bmod \text {array_size}
\]

二次探查法

\[\operatorname H(x,k)=(x+k^2)\bmod \text{array_size}
\]

双哈希法

这种方法需要引入一个新的\(Hash\)函数\(newh(x)\):

\[\operatorname H(x,k)=(x,k\times newh(x))\bmod\text{array_size}
\]

其中线性探查法有最优的缓存访问与计算消耗，二次探查法次之，双哈希法最劣。不过双哈希法的概率相等，能够避免“聚集”，即大量\(Hash\)值接近的情况。

三种方法代码类似：

const int array_size=1e5+5;//数组大小

int val[array_size];

int H(int buc,int opercnt){…}//上文提到的函数

void get_hash(int key)//加入元素操作

{

    int buc=f(key,array_size);

    while(val[buc]!=key&&val[buc])

        buc=(buc==array_size-1?0:buc+1);

    val[buc]=key;

}

bool check(int key)//查询元素操作

{

    int buc=f(key,array_size),opercnt=0;

    while(val[buc]!=key&&val[buc])

        buc=H(buc,opercnt++);

    return val[buc]==key;

}

在键值均匀分布的前提下，开放定址法时间复杂度为\(O(\texttt{length(Hash table)/(length(Hash table)}-n))\)

结语

以上是一些Hash的常用方法，限于篇幅这里仅提到了数值的哈希。

Hash还有更多的骚操作应用，如字符串哈希，排列哈希，树或图的哈希，Hash哈希（下）会提到的(光速逃

\[\xrightarrow{\qquad}To\;be\;continued\cdots
\]

相关文章