将关键字序列 ⟨7,8,30,11,18,9,14⟩ 散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H(key)=(key×3)mod7 ，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7 。

(1) 请画出所构造的散列表。

(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

散列表 平均查找长度

[tag_link]

1）由装载因子为 0.7, 数据总数为 7, 得一维数组大小为 7/0.7= 10, 数组下标为 0~9。所构造的散列函数值见下表。

采用线性探测再散列法处理冲突，所构造的散列表见下表。

2）查找成功时，是根据每个元素查找次数来计算平均长度的，在等概率的情况下，各关键字的查找次数见下表。

ASL成功 = 查找次数/元素个数 = (1 + 2 + 1 + 1 + 1 + 3 + 3)/7 = 12/7。

这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 mod7，初始只可能在 06 的位置。等概率情况下，查找 06 位置查找失败的查找次数见下表。

ASL不成功 = 查找次数/散列后地址个数 = (3 + 2 + 1 + 2 + 1 + 5 + 4)/7 = 18/7。