概念#

• ASL 比较次数的期望，分为成功ASL与失败ASL
• 查找判定树 内部节点表示集合容器中存在的元素，外部节点是失败节点，查找判定树是正则的所以如果有n个元素那么就有n个内部节点与n+1个外部节点，即n个元素能分割出n+1个失败区间

线性容器查找#

顺序查找#

无序序列的查找#

有序序列的查找#

• 对于查找成功同无序序列有相同的ASL
• 对于有序序列不必比较所有元素所以ASL比无序序列小

索引查找#

索引顺序查找#

也叫分块查找设共n条记录，b条记录组成一个块，在索引表与块内都采用顺序查找那么$ASL = \frac{n/b+1}{2} + \frac{b+1}{2} >= \sqrt{n} + 1$

折半查找#

判定树#

对于判定树与所有子树而言 如果mid=floor((l+r)/2)左子树节点数要么等于右子树要么右子树比左子树数量多一个 如果mid=ceil((l+r)/2)左子树节点数要么等于右子树要么左子树比右子树数量多一个

树查找#

• BST
• BBT
• avl树
• 红黑树b树家族

哈希查找#

哈希函数#

• 直接定址
• 取模
• 数字分析
• 平方取中

冲突#

开放定址法#

哈希槽不仅对同义词还对非同义词表项开放 $H_i = (Hash(key) + d_i)\space mod\space table.len$,根据$\{d_i\}$序列选择的不同有四类子方法

• 线性探测
• 平方探测
• 再哈希
• 伪随机序列

封闭定址法#

拉链法

性能分析#

• ASL 对于开哈希方法的失败查找的结果则是顺着哈希表找到第一个无效的哈希表项，但是这个无效的哈希表项也要算入一次比较次数
• LoadFactor 装载因子
• 哈希表性能
  • 哈希函数
  • 处理冲突的方法
  • 装填因子