社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
哈希的英文是Hash,一般被译为散列,也被音译为哈希,把任意长度的输入通过散列算法输出,该输出值就是散列值。一般散列算法会根据输入值计算出输出应该存储的位置,这个位置如果和已经存储键值冲突则需进行重新映射。常见的散列函数有:
(1)直接取余法: f(x)=(x+MAX)mod size 其中MAX是一个比较大的数,size是存储空间
(2)平方取中法:先计算关键字的平方然后有目的的选取中间的若干位作为散列地址。若,假设散列地址范围是[000,999],k=4731则k^2=22382361取第三位至第五位作为其散列地址,则H(k)=382
(3)叠加法:把关键字分割成位数相同的几部分,如最后一部分位数不够,则左边可以空缺。
(4)基数转换法:设原关键字是十进制数,人为的当做q进制数,再转换成十进制数作为散列地址。
(5)除留余数法:设散列范围的长度为m,将关键字值k除以某数p(p<=m)以后所得的余数作为散列地址。对应的散列函数为H(k)=k mod p
处理冲突的方法:
(1)开放定址法:将散列表中“空”的地址向处理冲突开放,当散列表未满时,处理冲突需要的“下一个”空位在该散列表中解决。因此,当发生冲突时散列函数为:Di=(H(k)+di) mod m
di的取法为:
(a)1,2,3,...m-1,称线性探测再散列。
(b)1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)称二次探测再散列。
(c)伪随机数列。称伪随机探测再散列
(2)再散列法:当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
(3)链地址法:把据哟相同散列地址的元素用一个线性链表链接在一起,每个线性链表称之为一个“桶”,为了处理方便每个链表前设置一个头结点,所有头结点存放于散列地址在[0,m-1]的散列表中。如下图所示:
(4)建立一个公共溢出区
今天做题发现了一道题可以用哈希来进行解决,我用的是直接取余法。下面我将代码贴出来:
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXNUM 4000
#define MAX 1000000000
#define size 20345677
#define key 745
int a[4][MAXNUM];
int n,ans;
int hash[size],sum[size];
void insert(int a){
int tmp=(a+MAX)%size;
while(hash[tmp]!=MAX&&hash[tmp]!=a)
tmp=(tmp+key)%size;
hash[tmp]=a;
sum[tmp]++;
}
int find(int a){
int tmp=(a+MAX)%size;
while(hash[tmp]!=MAX&hash[tmp]!=a)
tmp=(tmp+key)%size;
if(hash[tmp]==MAX)
return 0;
else
return sum[tmp];
}
int main(){
int i,j;
ans=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d %d %d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);
for(i=0;i<size;i++)
hash[i]=MAX;
for(i=0;i<size;i++)
sum[i]=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
insert(a[0][i]+a[1][j]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ans+=find(-(a[2][i]+a[3][j]));
printf("%dn",ans);
}
主要的算法是在insert()函数和find()函数内。如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!