C/C++ 关于哈希表算法的一个问题?
2024-05-09
1. C/C++ 关于哈希表算法的一个问题?
我只知道<<是向右移位的意思
2. 有关数据结构哈希表的问题？
Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
hashing定义了一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。
设所有可能出现的关键字集合记为u(简称全集)。实际发生(即实际存储)的关键字集合记为k（|k|比|u|小得多）。|k|是集合k中元素的个数。
散列方法是使用函数hash将u映射到表t[0..m-1]的下标上（m=o(|u|)）。这样以u中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在o(1)时间内就可完成查找。
其中：
① hash：u→{0，1，2，…，m-1} ，通常称h为散列函数(hash function)。散列函数h的作用是压缩待处理的下标范围，使待处理的|u|个值减少到m个值，从而降低空间开销。
② t为散列表(hash table)。
③ hash(ki)(ki∈u)是关键字为ki结点存储地址(亦称散列值或散列地址)。
④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(hashing).
比如：有一组数据包括用户名字、电话、住址等，为了快速的检索，我们可以利用名字作为关键码，hash规则就是把名字中每一个字的拼音的第一个字母拿出来，把该字母在26个字母中的顺序值取出来加在一块作为改记录的地址。比如张三，就是z+s＝26+19＝45。就是把张三存在地址为45处。
但是这样存在一个问题，比如假如有个用户名字叫做：周四，那么计算它的地址时也是z+s＝45，这样它与张三就有相同的地址，这就是冲突，也叫作碰撞！
冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(synonym)。
冲突基本上不可避免的，除非数据很少，我们只能采取措施尽量避免冲突，或者寻找解决冲突的办法。影响冲突的因素
冲突的频繁程度除了与h相关外，还与表的填满程度相关。
设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(load factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。
散列函数的构造方法：
1、散列函数的选择有两条标准：简单和均匀。
简单指散列函数的计算简单快速；
均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集k随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。
2、常用散列函数
（1）直接定址法：比如在一个0～100岁的年龄统计表，我们就可以把年龄作为地址。
（2）平方取中法
具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
（3）除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数（4）随机数法
选择一个随机函数，取关键字的随机函数值为它的散列地址，即
h(key)=random(key)
其中random为伪随机函数，但要保证函数值是在0到m-1之间。
处理冲突的方法：
1、开放定址法
hi=(h(key)+di) mod m i=1,2,...,k(k<=m-1)
其中m为表长，di为增量序列
如果di值可能为1,2,3,...m-1，称线性探测再散列。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。开放地址法堆装填因子的要求
开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。
②二次探查法(quadratic probing)
二次探查法的探查序列是：
hi=(h(key)+i*i)％m 0≤i≤m-1 //即di=i2
即探查序列为d=h(key)，d+12，d+22，…，等。
该方法的缺陷是不易探查到整个散列空间。
③双重散列法(double hashing)
该方法是开放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+i*h1(key))％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列为：
d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。
2、拉链法
拉链法解决冲突的方法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组t[0..m-1]。凡是散列地址为i的结点，均插入到以t为头指针的单链表中。t中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。
3、建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量hashtable[0..m-1]为基本表，另外设立存储空间向量overtable[0..v]用以存储发生冲突的记录。
性能分析
插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。
虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。
（1）查找成功的asl
散列表上的查找优于顺序查找和二分查找。
（2） 查找不成功的asl
对于不成功的查找，顺序查找和二分查找所需进行的关键字比较次数仅取决于表长，而散列查找所需进行的关键字比较次数和待查结点有关。因此，在等概率情况下，也可将散列表在查找不成功时的平均查找长度，定义为查找不成功时对关键字需要执行的平均比较次数。
注意：
①由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。
②散列表的平均查找长度不是结点个数n的函数，而是装填因子α的函数。因此在设计散列表时可选择α以控制散列表的平均查找长度。
③ α的取值
α越小，产生冲突的机会就小，但α过小，空间的浪费就过多。只要α选择合适，散列表上的平均查找长度就是一个常数，即散列表上查找的平均时间为o(1)。
④ 散列法与其他查找方法的区别
除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。其中顺序查找是对无序集合的查找，每次关键字的比较结果为"="或"!="两种可能，其平均时间为o(n)；其余的查找均是对有序集合的查找，每次关键字的比较有"="、""三种可能，且每次比较后均能缩小下次的查找范围，故查找速度更快，其平均时间为o(lgn)。而散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为o(1)。
例子：例子：选取哈希函数h(k)=(3k)%11,用线性探测再散列法处理冲突。
试在0～10的散列地址空间中，对关键序列22,41,53,46,30,13,01,67构造哈希表，并求等概率情况下查找不成功的平均查找长度asl。
3. C++哈希表问题求教
比如说，我有一个静态表(数组)a，现在有一个数据b需要索引: 不用哈希表的话就是遍历整个表，比较b和关键字是否相同，这样效率很低。 使用哈希表，可以先对b做哈希运算，得到c，那么a[c]就是我们要找的,就算有冲撞，和遍历整个表相比也是微乎其微的
4. hash table的问题
你的这个算法，可以说是一种针对字符串的hash table的实现方法。 但是，我觉得你大概没有理解面试官的意图。他让你写一个程序，从大量的string中找出某个特定的，那么你在设计hash函数的时候，应该让它能尽量地有区分度，只取首字进行区分，然后再使用链地址法无序地存放hash code重复的值，这样的效率依然很低。 想要提高效率，就要尽量地从这些字符串中提取更多的特征信息，hash code的范围也要扩大。 打个简单的比方，将hash code的范围扩大到65536，而特征值的选取，可以依次取字符串的第1，2，4，8个字符直接拼成一个无符号整型。 另外，使用链地址法时，键值相同的数据，最好按某一排序规则有序存放，这样在查找时效率就可以通过二分查找等方法大幅提升。
5. 数据结构哈希表，求大神，急急急
#include
#include
#include
#define MAXSIZE 20
#define MAX_SIZE 20 //人名的最大长度
#define HASHSIZE 60 //定义表长
#define SUCCESS 1
#define UNSUCCESS -1
typedef int Status; //为现有类型添加一个同义字
typedef char NA[MAX_SIZE]; // typedef 掩饰数组类型
typedef struct //记录
{
NA name;
NA xuehao; //关键字
NA tel;
}Stu; //查找表中记录类型
typedef struct //建立哈希表
{
Stu *elem[HASHSIZE]; //数据元素存储基址
int cou; //当前数据元素个数
int siz; //当前容量
}HashTable;
Status eq(NA x,NA y)
{
if(strcmp(x,y)==0)
return SUCCESS;
else return UNSUCCESS;
}
Status NUM_BER; //记录的个数 全局变量
Status NUM_BER1;
void Create(Stu* a) //创建新的通讯录
{
system("CLS"); //调用DOS命令CLS能够清屏
int i;
FILE *fp1,*fp2;
if((fp1=fopen("record.txt","r"))!=NULL) //打开文件
{
fclose(fp1); //关闭文件
}
else
{
fp2=fopen("record.txt","w"); //如果不存在,就创建一个record.txt
fclose(fp2);
}
printf("\n输入要添加的个数：\n");
scanf("%d",&NUM_BER);
for(i=0;i<NUM_BER;i++)
{
printf("请输入第%d个记录的姓名:\n",i+1);
scanf("%s",a[i].name);
printf("请输入%d个记录的学号:\n",i+1);
scanf("%s",a[i].xuehao);
printf("请输入第%d个记录的电话号码:\n",i+1);
scanf("%s",a[i].tel);
}
getchar();
printf("添加成功!!!\n");
}
void getin(Stu * a) //录入通讯录的内容，传入一个record的指针，然后针对这个指针指向的内存记录进行操作
{int i;
system("cls"); //调用DOS命令CLS能够清屏
printf("输入要添加的个数：\n");
scanf("%d",&NUM_BER);
for(i=0;i<NUM_BER;i++)
{
printf("请输入第%d个记录的姓名:\n",i+1);
scanf("%s",a[i].name);
printf("请输入%d个记录的学号:\n",i+1);
scanf("%s",a[i].xuehao);
printf("请输入第%d个记录的电话号码:\n",i+1);
scanf("%s",a[i].tel);
}
}
void output(Stu* a) //显示输入的用户信息
{int i;
system("cls");
printf(" \n姓名\t学号\t\t电话号码");
for( i=0;i<NUM_BER;i++)
printf("\n%s\t%s\t\t%s",a[i].name,a[i].xuehao,a[i].tel);
}
int Hash(NA name)
{
int i,m;
i = 1;
m=(int)name[0];//强制转化成数字
while(name[i]!='\0')
{
m+=(int)name[i];
i++;
}
m=m%HASHSIZE;
return m;
}
Status collision(int p,int c) //冲突处理函数，采用二次探测法解决冲突 //二次探测法处理冲突
{
int i,q;
i=c/2+1;
while(i<HASHSIZE)
{
if(c%2==0)
{
c++;
q=(p+i*i)%HASHSIZE;
if(q>=0) return q;
else i=c/2+1;
}
else
{
q=(p-i*i)%HASHSIZE;
c++;
if(q>=0) return q;
else i=c/2+1;
}
}
return UNSUCCESS;
}
void CreateHash(HashTable* H,Stu* a) //建表，以人的姓名为关键字，建立相应的哈希表
{ int i,p=-1,c,pp;
system("cls");//若哈希地址冲突，进行冲突处理
for(i=0;i<NUM_BER+NUM_BER1;i++)
{
c=0;
p=Hash(a[i].name);
pp=p;
while(H->elem[pp]!=NULL)
{
pp=collision(p,c); //若哈希地址冲突，进行冲突处理
if(pp<0)
{
printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出
continue; //无法解决冲突，跳入下一循环
}
}
H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入
H->cou++;
printf("第%d个记录冲突次数为%d。\n",i+1,c);
}
printf("\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->cou);
}
void SearchHash(HashTable* H,int c) //在通讯录里查找姓名关键字，c用来记录冲突次数，若查找成功，显示信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要查找记录的姓名：\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->name)==1)
{
printf("\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c);
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
}
else printf("\n此人不存在，查找不成功!\n");
}
void Modify(HashTable* H,int c) //在通讯录里修改某人信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要修改记录的姓名：\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->tel)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->tel)==1)
{
printf("\n以下是您需要修改的信息：");
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->tel[0]='\0';
printf("请输入修改后记录的姓名:\n");
scanf("%s",H->elem[pp]->name);
printf("请输入修改后记录的学号:\n");
scanf("%s",H->elem[pp]->xuehao);
printf("请输入修改后记录的电话号码:\n");
scanf("%s",H->elem[pp]->tel);
printf("修改成功!");
}
else
printf("\n此人不存在，修改不成功!\n");
}
void Delete(HashTable* H,int c) //在通讯录里查找姓名关键字，若查找成功，显示信息然后删除
{
int m,p,pp;NA str;
m=0;
system("cls");
printf("\n请输入要删除记录的姓名：\n");
m++;
scanf("%s",str);
p=Hash(str);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1)
{
printf("\n以下是您需要要删除的信息：\n\n",c);
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->name[0]='\0';
printf("删除成功!!!");
}
else
printf("\n此人不存在，删除不成功!\n");
}
void Save(HashTable * H) //将记录保存到指定文件
{
system("CLS");
int i;
FILE* fp;
if((fp=fopen("record.txt","w"))!=NULL)
{
fprintf(fp,"==================== 班级通讯录 ===================\n");
for(i=0;i<HASHSIZE;i++)
{
if((H->elem)[i]!='\0')
{
fprintf(fp,"学生姓名:%s\n",H->elem[i]->name);
fprintf(fp,"学生学号:%s\n",H->elem[i]->xuehao);
fprintf(fp,"学生电话号码:%s\n",H->elem[i]->tel);
fprintf(fp,"***********************************************\n");
}
}
fclose(fp);
printf("==================== 班级通讯录 ===================\n");
printf("\n\n恭喜你!!成功储存，你能在record.txt找到相应纪录\n");
system("pause");
}
else
{
printf("抱歉，保存记录失败！！");
system("pause");
}
}
int main()
{
Stu a[MAXSIZE];
int c,flag=1,i=0;
HashTable *H;
H=(HashTable*)malloc(sizeof(HashTable));
for(i=0;i<HASHSIZE;i++)
{
H->elem[i]=NULL;
H->siz=HASHSIZE;
H->cou=0;
}
while (1)
{ int num;
printf("\n");
printf("\n***************************班级通讯录****************************");
printf("\n* 【1】. 创建用户信息 *");
printf("\n* 【2】. 添加用户信息 *");
printf("\n* 【3】. 显示所有用户信息 *");
printf("\n* 【4】. 以姓名建立哈希表（二次探测法解决冲突）*");
printf("\n* 【5】. 查找用户信息 *");
printf("\n* 【6】. 删除用户信息 *");
printf("\n* 【7】. 修改用户信息 *");
printf("\n* 【8】. 保存 *");
printf("\n* 【9】. 退出程序 *");
printf("\n*****************************************************************");
printf("\n");
printf("\n* 温馨提示： *");
printf("\n* 进行4、5、6操作前 请先输出3 *");
printf("\n*****************************************************************");
printf("\n请输入一个任务选项>>>");
printf("\n");
scanf("%d",&num);
switch(num)
{
case 1:Create(a) ;break;
case 2:getin(a); break;
case 3:output(a); break;
case 4:CreateHash(H,a); break;
case 5:c=0;SearchHash(H,c); break;
case 6:c=0;Delete(H,c); break;
case 7:c=0;Modify(H,c); break;
case 8:Save(H); break;
case 9:return 0; break;
default:
printf("输入错误，请重新输入!");
printf("\n");
}
}
system("pause");
return 0;
}
6. c++问题哈希表完成文本搜索
你好 很高兴为你解答 答案是：这个问题还没有等到答案吗？ 满意请采纳，谢谢
7. c#删除哈希表中所有值为1的键值对 代码
基本思路是先获取哈希表中所有值为1的键名，然后用这些键名引用相应元素，并移除这些元素。
//生成Hash表。 Hashtable hashtable = new Hashtable(); hashtable.Add("name", "Tome"); hashtable.Add("age", 18); hashtable.Add("sex", "男"); hashtable.Add("补考次数", 1); hashtable.Add("重修次数", 1); //找到所有值为1的键名。 string[] keys = hashtable.Keys.Cast().Where(x => hashtable[x].Equals(1)).ToArray(); //移除相应键名对应的元素。 foreach (string key in keys) hashtable.Remove(key); //显示Hash表当前所有元素。 foreach (DictionaryEntry entry in hashtable) Console.WriteLine(entry.Key + "\t" + entry.Value); Console.ReadKey();运行结果：
小知识：
HashTable类（哈希表）：每个元素都是一个存储在 DictionaryEntry 对象中的键/值对。键不能为 nullNothingnullptrnull 引用（在 Visual Basic 中为 Nothing），但值可以。
在哈希表中，根据指定键名获取或设置相应值的运算复杂度为 O(1)，判断指定键名是否存在的运算复杂度也是 O(1)。
8. 关于哈希表容量最好是质数的问题
不会证明...不过可以大概解释一下... 设有一个哈希函数 H( c ) = c % N; 当N取一个合数时，最简单的例子是取2^n，比如说取2^3=8,这时候 H( 11100(二进制） ) = H( 28 ) = 4 H( 10100(二进制) ) = H( 20 ）= 4 这时候c的二进制第4位（从右向左数）就”失效”了，也就是说，无论第c的4位取什么值，都会导致H( c )的值一样．这时候c的第四位就根本不参与H( c )的运算，这样H( c )就无法完整地反映c的特性，增大了导致冲突的几率． 取其他合数时，都会不同程度的导致c的某些位”失效”，从而在一些常见应用中导致冲突． 但是取质数，基本可以保证c的每一位都参与H( c )的运算，从而在常见应用中减小冲突几率．． （个人意见：有时候不取质数效率也不会太差..但是无疑取质数之比较保险的..) 以上就是我的理解 补充一点，这里是说在常见应用中，往往有些数据会比较相近，这时候用质数比较好，比如要存放的数据是压缩的状态，比如存储一个描述当前搜索状态的表，的这时候哈希不用质数冲突机率就比较大。 如果是随机分布的整数，那么哈希模数只要取到足够大，在概率上来说都是一样的，但是这显然脱离实际应用。 你说的情况 是比较特殊的，因为选取了比较小的一个质数，当选去大质数N时，就可以仅在N进制的某一位失效，结合计算机系统的特性，N进制位表示法往往是不关键的，而常用的2^N进制比较关键，所以可以避免冲突。 其实，偶用一些大数做过测试，用来存放一个压缩为二进制的邻接矩阵，当模数足够大时，即便是合数也能有很接近质数的效果，但在某些（几十个）合数上会造成效率严重下降，所以质数是比较保险的。 你不妨自己做实验，不要去选随机整数，而要考虑一些常见应用，用质数和合数进行测试，主要考察平均装载因子，你得到的结论可能和我一样：合数绝大多数时候效果也不错，但在一部分合数上效果差得出奇，而质数几乎全部都有很好的效果。
最新文章
热门文章
推荐阅读