关于哈希
今天老师讲了哈希，草草地整理一下：哈希表，也称散列表，是一种高效的数据结构。它的最大优点就是把数据存储和查找所消耗的时间大大降低，几乎可以看成是 O（1）的，而代价是消耗比较多的内存。
他的基本实现原理就是将输入以某种方式转化为固定长度的输出，该输出就是散列值：
举个例子，比较两个字符串是否相同，可以将所有的字母转换为数字1到26，将字符串用数字累加求和再取余的方式求出散列值，通过比较两者散列值是否相等来判断两字符串是否相等
我们可以用前缀和的思想来计算每个字符串的哈希值：
通过这个例子我们就很好地解决了每个字符串的哈希值：
比如说输入一个字符串，输入a,b,c,d，尝试比较，两个子字符串是否相同
下面给出核心代码：
string s; // s 为字符串
int f, g; // f 为前缀和，g 为 D 的 i 次方
void prehash(int n) // 预处理哈希值
{// 预处理时，注意到数字可能很大，对一个数 MD 取模
f = s; // f 前缀和预处理
for(int i=1; i<=n; i++)
{
f = (1LL * f * D + s) % MD;
}
g = 1; // g：D 次方预处理
for(int i=1; i<=n; i++)
{
g = 1LL * g * D % MD;
}
}
int hash(int l, int r) // 计算区间 的哈希值
{
int a = f;
int b = 1LL * f * g % MD; // 记得乘上次方
return (a - b + MD) % MD; // 前缀和相减
// 有可能结果小于 0，加上一个 MD 将其变为正数
}
if(hash(a, b) == hash(c, d)) // 字符串 与字符串 匹配
这种方法固然很不错，但是也有一个小问题：两个不同的数据无法保证其散列值一定不同，也就会判断错误，这种情况叫做哈希冲突
那么如何解决这样的冲突呢？？？这里介绍两种方法：
1、拉链法（链地址法）：
就是将具有相同哈希值的数据存在一个链表中，查找某一元素是否在哈希表时，就求出待判断的那个元素的散列值，并在哈希表中找到相应位置的地址，搜索这条链上的元素并判断是否相等即可，链表结构如下图所示：
核心代码如下：
//链地址法
vector<int> hash_array;
// hash_array：每个位置用一个 vector 来维护
void push2(int x)
{
int y = x % N; // 计算初始位置
for(int i=0; i<hash_array.size(); i++)if(hash_array == x) // 如果之前已经出现过了
{
cout << x << "?has?occured?before!" << endl;
return; // 标记已经出现过
}
// 如果之前没有出现过，将 x 加入表中
hash_array.push_back(x);
cout << x << "?inserted." << endl;
}
2.顺序询址法：
就是当有两个元素的散列值出现重复的时候，将后输入的元素往后放（如果后面有空的话），当然，如果后面也被占领了，就一直往后找，直到有空隙能够放下为止，
当想要查找一个元素时，先求出他的散列值，找到哈希表对应的位置，如果不是就一直往后找，如果查询到了当前位置为空时还没有找到此元素，那么这个元素就不存在，输出no，反之则输出yes
核心代码如下：
//顺序寻址法
int hash_table; // hash_table 哈希表：0 位置代表没有数
void push1(int x)
{
int y = x % N; // 计算初始位置，N：表的大小
for(; hash_table!=0 && hash_table!=x; ) y = (y+1) % N;
// 寻找到一个 0 位置，或者找到自己为止
if(hash_table) cout << x << "?has?occured?before!" << endl;
// 如果是自己本身，则之前已经出现过了
else
{
hash_table = x; // 否则，将 x 加入表中
cout << x << "?inserted." << endl;
}
}
还有就是哈希表的常见构造方法，一种经典的叫做求模取余法（上文也有所体现）：
尝试构造一种哈希函数：H(key)=key%p
其中p是一个可以自己拟定的值，但尽量要求p<=哈希表的表长m且p是一个质数。
哈希有很多的应用，比如：
输入n个整数，输入m为访问次数，每次访问是输入一个数并判断原序列中是否有这个元素
代码如下：
#include<cstdio>
#include<iostream>
using namespace std;
const int N=50000; //定义总共输入哈希数字个数
const int b=999979,H=999979;//哈希取模%数字
int tot,adj,nxt,num;
int top,stk;
void init()
{ //初始化哈希表
tot=0;
while(top)//我们用一个栈存储下出现过的哈希值
adj]=0;
} //每次把出现过的哈希值的链表清0，来节省时间
void insert(int key)
{//将一个数字插入哈希表
int h=key%b; //除余法
for(int e=adj;e;e=nxt)
if(num==key) //诺链表中已存在当前数字则不再存
return;
if(!adj) stk[++top]=h; //把第1次出现的哈希值入栈
nxt[++tot]=adj,adj=tot; //建立链接
num=key; //建立链接表，存储值等于key的数字。
}
bool query(int key)
{
int h=key%b;
for(int e=adj;e;e=nxt) //查询链接
if(num==key) return true;
return false;
}
int main()
{
int a;
init();
int n,m;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a;
insert(a);
}
cin>>m;
int num;
for(int i=1;i<=m;++i)
{
cin>>num;
if(query(num))
printf("yes\n");
else
printf("no\n");
}
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int N=1e4+1;
char c;
ull a;
ull num=131;
int ans,n;
int prime=233317;
ull mod=212370440130137957ll;
ull hasha(char s[])
{
int len=strlen(c);
ull ans=0;
for(int i=1;i<=len;i++)
{
ans=(ans*num+(ull)c)%mod+prime;
}
return ans;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>c;
a=hasha(c);
}
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
if(a!=a)
{
ans++;
}
}
cout<<ans+1;
return 0;
}
页:
[1]