求解 试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的平均查找长度。

Question

试为下列关键字建立一个装载因子不小于 0.75 的哈希表，并计算你所构造的哈希表的平均查找长度。　　（ZHAO, QIAN, SUN, LI, ZHOU, WU, CHEN, WANG, CHANG, CHAO, YANG, JIN）
回答后可以再百度上面通知我

Answer 1

解：（1）先确定哈希表的长度：

根据公式：α= n/m, （n为记录数，m为表长）可知因为α不小于0.75，所以当记录数为12时，可以设表长为16，此时α的值为0.75

（2）根据关键字首字母的排序建立哈希表，若首字母相同则将第二个字母的排序加上，依次类推，易知

可以转换为数字ZHAO = 26；QIAN = 17；SUN = 19；LI = 12；ZHOU = 34；WU = 23；

ZHANG = 35；WANG = 24；CHANG = 3；CHAO = 11；YANG = 25；JIN = 10

（3）

增量di设为di = i((12k)MOD15+1

H(key) = (3k)MOD20

易求得哈希表为：

H(26) = 18;

H(17) = 11;

H(19) = 17;

H(12) = 16

H(34) = 2;

H(23) = 9;

H(35) = 5;

H(24) = 12;

H(3) = 9;H1(3) = 7;

H(11) = 13;

H(25) = 15;

H(10) = 10;

                          

平均查找长度：

ASLsucc = (1×11+2)/12=13/12;

Answer 2

呵呵，我也很想知道i！