哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　其中 Ci 为哈希函数取值为 i 时查找不成功的比较次数。 查找不成功的情况：（1）遇到空单元，（2）按解决冲突的方法完全探测一遍 后仍未找到。0 到 r－1 相当于 r 个不成功查找的入口，从每个入口进入后，直到 确定查找不成功为止，其关键字的比较次数就是与该入口对应的不成功查找长度。 据此计算公式，对下图所示的哈希表（采用线性探测再散列法处理冲突）， 可计算出在等概率情况下其查找不成功的平均查找长度为：

　　对于一个具体的哈希表，通常采用直接计算的方法求其平均查找长度。 例已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10， 79）给出按哈希函数 H(key)=key % 13 和线性探测处理冲突构造所得哈希表 ht[0..15]。 如下图所示。其中，每个关键字下面带圈的数字，是放置该关键字时所进行 的地址计算次数，或者说是放置该关键字时所进行的关键字比较次数（同时也是 查找该关键字时所进行的关键字比较次数）。