数据结构哈希函数问题

来源：百度知道 编辑：UC知道 时间：2024/09/25 08:34:29
设哈希表的长度 M=13; 哈希函数为 H（k）＝k mod m,给定的关键码序列为 19, 14, 23, 01, 68, 20, 84, 27, 55, 11，并求出在等概率的情况下的ASL，请帮我作一下请详细些谢谢！

***************1。链地址法处理冲突构造所得哈希表************
H（19）=19MOD13=6；所以在链表第七个位置的第一个元素（所以对19查询能够一次查到。）
H(14)=14MOD13=1;所以在链表第二个位置的第一个元素（所以对14查询能够一次查到。）
H(23)=23MOD13=10;所以在链表第十一个位置的第一个元素（所以对23查询能够一次查到。）
H(01)=01MOD13=1;所以在链表第二个位置的第二个元素（所以对01查询能够二次查到。）
H(68)=68MOD13=3；所以在链表第四个位置的第一个元素（所以对68查询能够一次查到。）
H(20)=20MOD13=7;所以在链表第八个位置的第一个元素（所以对20查询能够一次查到。）
。。。。。。。。。。。
一直到链表建完
书上的例子
ASL(10)表示有10个元素
ASL(10)=1/10(1*5+2*4+3*1)=1.6
其中1*5表示一次就能够查到的元素个数有 5个，即长度为1；
2*4表示2次能够查到元素个数由4个 即长度为2；
3表示3次能购查到的元素有1个 即长度为3；

1.6表示每个元素平均找到的长度为1.6