平均检索长度

检索过程中对于关键码的平均比较次数。

$$ \mathrm{AVL} = \sum_{i = 1}^n P_iC_i $$

$P_i$ 表示检索到第 $i$ 个元素的概率，$C_i$ 表示检索到第 $i$ 个元素所需要的时间。

散列表

散列的基本思想

一个确定的函数 $h$。

待检索的关键码 $K$。

函数值 $h(K)$。

根据 $h(K)$ 计算记录的存储位置。

基本概念

• 负载因子 $\alpha = \dfrac{n}{M}$。

  $n$ 为散列表中已经有的节点数。

  $M$ 为散列表空间大小。

• 冲突：将不同的关键码映射到相同的散列地址。

常用散列函数

除余法

$$ h(x) = x \bmod M $$

通常选择质数作为 $M$ 值。

平方取中法

先通过求关键码的平方来扩大差别，再取其中的几位或者其组合作为散列地址。