首页 > 试题广场 >

有一组关键字为{77,28,38,41,45,1,9,31,

[问答题]

有一组关键字为{77,28,38,41,45,1,9,31,99,51,23,47,68,61}.1,请构造一个hash函数，形式为H（key）=key mod p，装填因子a=0.8，用链地址法解决冲突；2计算等概率情况下查找成功的平均查找长度；3计算等概率情况下查找失败的平均查找长度（空指针的比较不计入）。

努力变强的王小姐

hhhh

发表于 2017-08-10 19:09:43 回复(0)

冷静。

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int main()
{
int key[14] = {77,28,38,41,45,1,9,31,99,51,23,47,68,61};
int remain[14];
int remain_conts = 0;
int temp;
int p = 0;
while(++p)
{
remain_conts = 0;
for (int i = 0; i < 14; i++)
{
temp = key[i]%p;
int j = 0;
for (; j < remain_conts; j++)
{
if (remain[j] == temp) break;
}
if (j == remain_conts)
{
remain[remain_conts++] = temp;
}
}
if (abs((float)remain_conts/p-0.8) < 0.1)
{
break;
}
}
cout<<p<<endl;
cout<<"对应的余数:"<<endl;
for (int i = 0; i< 14; i++)
{
cout<<key[i]%p<<endl;
}
return 0;

}

通过计算，p等于6，对应的余数为：5 4 2 5 3 1 3 1 3 3 5 5 2 1，共占5个表项，5/6约等于0.83

发表于 2018-08-05 18:11:20 回复(2)

没毛病

装填因子为0.8 元素个数为14个，那么表长为14/0.8＝17.5，那么表长取18 :)我总感觉不太对:) 那p取18 hash函数为mod 18，对应的槽编号为{5 10 2 5 9 1 9 13 9 15 5 11 14 7}，查找成功的比较次数为{1 1 1 2 1 1 2 1 3 1 3 1 1 1}查找14个数需要比较20次查找成功平均查找长度为 20/14。链地址法，查找失败，每个元素都会比较一次，18次查找失败的总比较次数为元素总数14，失败平均查找长度为14/18

编辑于 2017-08-18 23:42:44 回复(6)

_Fan`Tasy

请参考Java HashMap源码

发表于 2018-04-11 01:35:10 回复(0)

细致的打工人追赶太阳

转天因子百度了一下是说实际占用空间/hash空间

通过如下代码发现i=11的时候跟题目要求的装填因子差不多。所以考虑用p=11，然后做后面的计算

#include<stdio.h>

#include<iostream>

#include<cstring>

using namespace std;

int arr[] ={77,28,38,41,45,1,9,31,99,51,23,47,68,61};

int main(){

int p[20];

for(int i = 11;i <= 20; i++){

memset(p,0,sizeof(p));

for(int j = 0;j < 14;j++)

p[arr[j]%i] = 1;

int l = 0;

for(int j = 0;j < i;j++)

l+=p[j];

cout<<i<<" "<<l<<" "<<1.0*l/i<<endl;

}

11 9 0.818182

12 9 0.75

13 9 0.692308

14 9 0.642857

15 8 0.533333

16 9 0.5625

17 10 0.588235

18 10 0.555556

19 9 0.473684

20 10 0.5

发表于 2017-09-01 22:06:32 回复(0)

提交观点

问题信息

来自：腾讯2017校招开发工...

上传者：阿奻_

难度：

5条回答 194收藏 8684浏览

有一组关键字为{77,28,38,41,45,1,9,31,

问题信息

热门推荐

相关试题