试用键值序列20,38,16,27,5,23,56,29建立散列

已知散列表的地址空间为0~10,散列函数为H(key)= key mod 11(mod表示求余运算),采用二次探测法解决冲突,

试用键值序列20,38,16,27,5,23,56,29建立散列表,

二次探测法的基本思想： 生成的后继散列地址不是连续的， 而是跳跃式的， 以便为后续数据元素留下空间从而减少堆积。 按照二次探测法， 键值 key 的散列地址序列为

其中， m 为散列表的表长， i=1²， -1²，2²， -2²， …， ±k²（k≤m/2） 。

本题中，长度为11的散列表，其散列函数为H(key) =key mod 11，求出键值序列（20,38,16,27,5,23,56,29)对应的散列函数H(key) ：

故依据H(key)依次填入散列表中对应的地址序号中，当插入元素16时，其对应的地址5已有元素38，故应用二次探测法，得到下一个地址d1=（5+1²）mod 11=6，故把元素16插入地址6；当插入元素27时，其对应的地址5已有元素38，应用二次探测法，得到下一个地址d1=（5+1²）mod 11=6仍有冲突，则再求下一个地址d1=（5-1²）mod 11=4，地址4上无元素，故把元素27插入地址4号中。同理求出后续key对应的地址。