对包含n个元素的散列表进行检索,平均检索长度( )。A)为0(log2n)B)为0(n)C)为0(n﹡log2n)

Question

对包含n个元素的散列表进行检索，平均检索长度（ ）。

A)为0(log2n)

B)为0(n)

C)为0(n﹡log2n)

D)不直接依赖于n

Answer 1

正确答案：D
由于散列表的一个重要特征是平均检索长度不直接依赖于元素个数n。平均检索长度不随表中元素增加而增加，而是随负载因子的增大而增加。如果安排得好，平均检索长度可以小于1．5。正是由于这个特征，散列表成为一种很受欢迎的组织线性表的方法。