已知有长度为9的表 (16，29，32，5，89，41，14，65，34) ，它 们存储在一个哈希表中，利用线性探测再散列法，要求它在等概率情 况下查找成功的平均查找长度不超过3。 (1) 该哈希表的长度m应设计成多大? (2) 设计相应的哈希函数 (3) 将数据填入到哈希表中 (4) 计算查找成功时的平均查找长度

(1) 根据线性探测再散列法的公式，平均查找长度ASL≈(1/2)*(1+1/(1-λ)^2)，其中λ为填装因子，表示已经填入哈希表中的元素个数与哈希表长度的比值。要求ASL不超过3，代入公式得到(1/2)*(1+1/(1-λ)^2)≤3，解得λ≤0.828。因此，哈希表的长度m应设计为m=11或m=12，这样可以满足要求。

(2) 设计哈希函数：h(key) = key % m，其中key为表中的元素值，m为哈希表长度。

(3) 将数据填入哈希表中：

哈希表长度m=11，填装因子λ≈0.818
索引位置：0 1 2 3 4 5 6 7 8 9 10
元素值：   41 14     89 16 32 5 65 29 34

(4) 计算查找成功时的平均查找长度：
对于任意一个元素，查找成功的概率为1/m，查找失败的概率为(1-1/m)。因此，平均查找长度ASL=(1/m)*(1+(1-1/m)*(1/(1-1/m)))。
对于元素16，它的哈希值为5，直接查找成功，ASL=1；
对于元素29，它的哈希值为7，需要1次线性探测，ASL=1+1=2；
对于元素32，它的哈希值为10，需要2次线性探测，ASL=1+2=3；
对于元素5，它的哈希值为5，需要1次线性探测，ASL=1+1=2；
对于元素89，它的哈希值为0，需要1次线性探测，ASL=1+1=2；
对于元素41，它的哈希值为9，直接查找成功，ASL=1；
对于元素14，它的哈希值为3，直接查找成功，ASL=1；
对于元素65，它的哈希值为9，需要1次线性探测，ASL=1+1=2；
对于元素34，它的哈希值为1，直接查找成功，ASL=1。
因此，查找成功时的平均查找长度ASL=(1/9)*(1+8*(1/10))≈1.089。