[单选题]
懒人选择直接写代码
const int TABLE_LEN = 11;//表的长度
int main(){
vector<string> a({"D","BA","TN","M","CI","I","K","X","TA"});
vector<string> h(11,"");
int total = a.size();//total：总的查找次数，每个变量至少查找一次，所以至少为a.size()
for(auto it=a.begin();it!=a.end();it++)
{
char c = (*it)[0];
int index = (c - 'A')%TABLE_LEN;
while(!h[index].empty()) {
index = index+1>=TABLE_LEN?0:index+1;//注意，index有可能超出h的边界，这时回到h.begin()
total++;
}
h[index] = *it;
}
//输出hash表
for(int i=0;i<h.size();i++)
std::cout<<(h[i].empty()?"空":h[i])<<" ";
std::cout<<std::endl;
//输出平均查找次数
std::cout<<total<<"/"<<a.size();
}
发表于 2021-03-06 11:20:19
回复(1)
冲突：两个不同的键占用同一个存储空间，基本这个意思...
哈希函数：H(k) = 每个元素第一个字母在字母表中的顺序 % 11 。
线性探测：a.该值是所要插入元素的关键码，不进行插入。 H(k) 的值等于 关键码
b.产生冲突，依次查看其后的下一个桶，如果发现空位置插入新元素
b.产生冲突，依次查看其后的下一个桶，如果发现空位置插入新元素
因此：D在字母表中第4个,4%11 = 4，BA的第一个字母B在字母表中第2个，2%11 = 2，..................
加下来就插入到哈希表中，上面得到的H(k)的值就是在哈希表中要插入的地址，具体如下：
长度为11的哈希表。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| K(7) | TA(9) | BA(2) | M(4) | D(1) | CI(5) | X(8) | | | TN(3) | I(6) |
D-->4 ,4位置空的，因此D放到4位置,(1)表示放入的顺序号,只查找的1次就插入了，因为没有产生任何冲突，故次数为 1
BA--->2,2位置空的，插入...，和上一个一样一次成功，次数 1
TN--> 9，不冲突， 次数 1
M-->3 ,不冲突，次数 1
CI-->3,与M的值一样为3，产生了冲突，因此放到3的后一个位置4，此时4位置上是D，又冲突了继续往后走到5，不冲突，插入，次数3--4--4,故次数为3次
I-->9,与TN冲突，后移到10,9--10，共2次
K-->0,不冲突，1次
X-->2,冲突，2--3---4--5--6,6位置空插入，共5次
TA-->9,冲突，9--10--0--1,1位置空，共4次，
9个元素总共走了1+1+...+5+4 = 20，那么平均查找长度为 20/9次。
发表于 2019-05-14 09:21:51
回复(0)
有没有算的是17/9.
得出这个答案的原因我们在算TA时，它的索引值为9，然后索引为9的位置已经有了TN，可能有的人认为他们第一个字母相同，所以不冲突，查找成功。可是他们的实际键值是不一样，即还是发生冲突。所以我们要继续考察索引的下一个位置，直到找到TA或空位置，就put
发表于 2017-09-30 07:48:49
回复(1)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
