哈希和哈希表

前言

应用：将一串字符串转变为数字

哈希 Hash

字符串哈希核心代码：

typedef unsigned long long ULL;
const int b=26;//进制 
ULL hash()
{
    ULL sum=0;
    for(int i=1;i<=m;++i)
        sum=sum*b+(ULL)(s[i]-'a'+1);//b进制 
    return sum;
}

把串 s[1..m] 当成一个 b 进制数，第 i 位是 s[i]-'a'+1 ，一个串就映射成了一个数；判两个串是否相等，比一下 hash 值就行， O(1) （算值本身要 O(m) ）。 b 取 26 正好对应 26 个字母。代码里 sum=sum*b+... 从高位往低位扫，和读十进制数一个道理。

每位上加 1 而不是用 0 ，是为了避免 "a" 和 "aa" 这种前面带 0 的串撞在一起—— a 算出来是 1 ， aa 是 1×26+1=27 ，分得开。

用 unsigned long long 存，乘加时按 2^64 自动溢出，相当于对 2^64 取模，不用写取模语句，也不会越界；无符号数的溢出是定义好的行为，不像 int 溢出那样未定义。

拿 abc 算一遍： 1×26^2+2×26+3=731 ，串就这样变成了数。

哈希表 Hash Table

例题：Code

题意：维护一个图书馆， add s 加入一本名为 s 的书， find s 查询这本书在不在馆里，书名区分大小写（一开始一本都没有），对每条 find 输出一行 yes 或 no 。

不同的串可能算出同一个 hash 值，这就是哈希冲突。例题用双哈希处理： p1 、 mod1 和 p2 、 mod2 各算一个值，两个值一起对上才认作同一本书——这也是代码注释里“减小误差”的意思，真撞上时 find 会把一本不存在的书误判成在馆。 sum1 决定挂在哪条链上， sum2 存在节点里用来比对。

另外 hash 值大到 2^64 ，没法直接拿来做下标，例题先对 mod1 取模把 x 压进 poi 数组， y 存进链表节点里；字符串哈希那种自然溢出省事，要自己开数组时就换成挑模数取模。

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
using std::cin;

const int mod1=1e6+3,mod2=1e6+9,p1=47,p2=79,N=30000;
int tot=0,nxt[N+5],poi[mod1+5],end[N+5];

void insert(int x,int y)						//将元素插入哈希表
{
	nxt[++tot]=poi[x];
	poi[x]=tot;
	end[tot]=y;
}

int query(int x,int y)
{
	for(int i=poi[x];i;i=nxt[i])				//找到则表示存在
	{
		if(end[i]==y)
		{
			return 1;
		}
	}
	return 0;									//不存在返回 0
}

int main()
{
	int n;
	char op[10],s[205];
	scanf("%d",&n);
	while(n--)
	{
		cin>>op;								//读入到空格
		cin.getline(s,205);						//读入剩余的一整行
		int len=strlen(s),sum1=0,sum2=0;
		for(int i=0;i<len;++i)					//双哈希思想,两个关键字决定一个字符串,减小误差
		{
			sum1=(sum1*p1+s[i])%mod1;
			sum2=(sum2*p2+s[i])%mod2;
		}
		if(op[0]=='a')
			insert(sum1,sum2);
		else
		{
			if(query(sum1,sum2)) 
				printf("yes\n");
			else
				printf("no\n");
		}
	}
	return 0;
}

核心代码

//x、y为一个元素的两个哈希值，使用双哈希思想处理哈希冲突
void insert(int x,int y)                        //将元素插入哈希表
{
    //所有 x 值相同的字符串会储存在一条链表上，用 y 值区分
    nxt[++tot]=poi[x];
    poi[x]=tot;
    end[tot]=y;
}

int query(int x,int y)
{
    for(int i=poi[x];i;i=nxt[i])                //找到则表示存在
    {
        if(end[i]==y)
        {
            return 1;
        }
    }
    return 0;                                   //不存在返回 0
}

上面完整程序里的 insert 、 query 抽出来就是这段。这套 poi 加 nxt 就是邻接表的写法： poi[x] 存 x 这条链的头， nxt 串起整条链， end 存 y 值， tot 给节点编号。

insert 头插， O(1) ； query 沿链表找，哈希值够散时期望链长就是 O(1) ，最坏会退化，所以模数要挑比 n 大不少的质数——例题 n 最多 30000 ， mod1 取了 1e6+3 。

参考资料：

例题代码：Hash 例题-哈希表.cpp

前言

哈希 Hash

哈希表 Hash Table

继续读