哈希表（等概率情况下）查找成功与查找不成功的平均查找长度

哈希表在等概率情况下，查找成功和查找不成功的平均查找长度可以分别用以下公式计算：

1. 查找成功的平均查找长度（Average Successful Search Length，简称 ASL）：

ASL = (1/2)(1 + 1/(1-λ))

其中，λ是哈希表的填装因子，即已经被占用的桶数与总桶数的比值。

2. 查找不成功的平均查找长度（Average Unsuccessful Search Length，简称 AUSL）：

AUSL = (1/2)(1 + 1/[(1-λ)^2])

这两个公式都是基于哈希表中每个元素被等概率地散列到每个桶中的情况下计算的。在实际使用中，哈希函数的设计和哈希表的容量都会影响到这两个指标的表现。

相关问题

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

(1) 根据装填因子α=9/m，我们希望平均查找长度不超过5，则根据公式：

E(n) = (1 + 1/(1-α))/2 <= 5

解得 m >= 14.25，因此哈希表的长度至少应该为15。

(2) 一个简单的哈希函数可以是取模函数，即 h(k) = k mod m，其中k为关键字，m为哈希表长度。

(3) 将数据填入哈希表中，可以按照以下步骤进行：

- 初始化哈希表，将所有位置都赋初值为空。
- 对于表中的每个元素，计算其哈希值h(k)，并将其插入哈希表中。
- 如果哈希表中h(k)位置已经被占用，则使用线性探测再散列法，查找下一个空位插入元素。

根据取模函数，可以将表中的元素插入到哈希表中的位置：

h(16) = 1， h(29) = 14， h(32) = 2， h(5) = 5， h(89) = 14， h(41) = 11， h(14) = 14， h(65) = 5， h(34) = 4

由于哈希表长度为15，因此哈希值相同的元素需要使用线性探测再散列法插入到下一个空位。

(4) 计算查找成功时的平均查找长度，可以使用公式：

ASL = Σ(di+1)/n

其中di为查找成功时需要查找的次数。我们可以使用线性探测的方法来查找元素，因此di最大为哈希表长度m，平均查找长度ASL不超过5，则可得到以下不等式：

Σ(m+1)/9 <= 5

解得 m >= 52.5，因此哈希表的长度至少应该为53。

将表中的元素插入到哈希表中后，可以计算出查找成功时的平均查找长度：

ASL = (1+2+1+1+3+1+1+2+1)/9 = 1.44

因此，在等概率情况下，查找成功的平均查找长度不超过1.44。

已知有长度为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。