哈希基本理论
描述
对n个元素我们通过一个Hash函数将其映射(映射:和key-value类似)
到m个空间中(n<=m)。
每个空间仅存放一个元素
空间位置=Hash(n的关键字)
常见问题
1.hash函数的设计
hash函数的设计决定了整个hash程序,地位类似于状态转移方程于DP中的地位
好的hash要尽量避免冲突(冲突:你算出来的hash(n1)=hash(n2),也就是说有两个不同的元素通过你的函数计算得出同一个位置)
2.冲突如何解决
这个具体问题中都不一样,空说无用,见下文代码示例。
BKDRHash
我买的书上提到了好几种字符串的Hash,其中BKDRHash是首选,这是测评说的不是我说的。
各种Hash的测评数据在这里
Hdu2648
我们以此题为例拆分整个代码来看BKDRHash
首先总代码我的代码很大~ 你要忍一下
#include <bits/stdc++.h>
using namespace std;
struct node
{
char name[35];
int price;
};
vector <node> list1[10005];
unsigned int BKDRHash(char *str)
{
unsigned int seed=31,key=0;
while(*str)
{
key=key*seed+(*str++);
}
return key&0x7fffffff;//不要超过int,好吗
}
int main()
{
int n,m,key,add,memoryp,ranks,len;
int p[100005];
char s[35];
node temp;
cin>>n;
for(int i=0;i<10005;i++)
list1[i].clear();
for(int i=0;i<n;i++)
{
cin>>temp.name;
key=BKDRHash(temp.name);
list1[key].push_back(temp);
}
for(cin>>m;m;m--)
{
ranks=0;
len=0;
for(int i=0;i<n;i++)
{
cin>>add>>s;
key=BKDRHash(s)%10005;
for(int j=0;j<(int)list1[key].size();j++)
{
if(strcmp(list1[key][j].name,s)==0)
{
list1[key][j].price+=add;
}
if(strcmp(s,"memory")==0)
{
memoryp=list1[key][j].price;
}
else
{
p[len++]=list1[key][j].price;
}
}
}
for(int i=0;i<len;i++)
{
if(p[i]>memoryp)
{
ranks++;
}
}
cout<<ranks<<endl;
}
return 0;
}
拆分出来看就好多了
基础部分就不一 一细说了
BKDRHash部分
unsigned int BKDRHash(char *str)
{
unsigned int seed=31,key=0;
while(*str)
{
key=key*seed+(*str++);
}
return key&0x7fffffff;//不要超过int,好吗
}
while中是在计算key,或者说在转化出一个key值,最后维护一下边界不要超出int表示最大范围
cin>>temp.name;
key=BKDRHash(temp.name);
list1[key].push_back(temp);
这是在使用没啥好说的
进一步缩小空间
key=BKDRHash(s)%10005;
当然随之而来的就是冲突问题,接下来就是解决冲突,也是Hash中最重要的部分
for(int j=0;j<(int)list1[key].size();j++)
{
if(strcmp(list1[key][j].name,s)==0)
{
list1[key][j].price+=add;
}
if(strcmp(s,"memory")==0)
{
memoryp=list1[key][j].price;
}
else
{
p[len++]=list1[key][j].price;
}
}
当我们输入一个name转化为key值之后我们可以对这个key之下的所有元素进行遍历,遍历到了对应的元素也就是strcmp返回0时,我们自然也就完成了匹配
其实整个冲突处理还要加上前面的一句
list1[key].push_back(temp);
没有这个存储也是无法实现冲突处理的。
我们要找到的不是一个完全完美的hash因为就算是完美的,用的过程中缩小范围之后也会产生冲突。我们需要学习经典的hash,适当设计自己的,重点在如何处理各种冲突上。
总结一下
设计函数返回key
用vector存储key对应的元素文章来源:https://www.toymoban.com/news/detail-417353.html
用vector处理冲突文章来源地址https://www.toymoban.com/news/detail-417353.html
到了这里,关于哈希基本理论与BKDRHash的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!