查找算法的效率评价
查找成功的ASL
查找失败的ASL
顺序查找
- 算法思路：从头到尾或者从尾到头，逐个元素与哨兵比较
- 算法实现：引入0位置为哨兵可以减少一次越界判断；加入哨兵在第0的位置并存放要查找的元素，顺序查找的时候从后往前查找，所以就不用进行越界判断
- ==无论如何优化都是O（n）==
折半查找
- 算法实现：
- 缺点：要有序顺序表（链表不合适呀）
- ==时间复杂度：log2n==
查找判定树
- 构造
- 特性：
折半查找的判定树是平衡的二叉排序树
只要表中的关键字个数相同，就一定会生成形状相同的判定树
只有最下面一层不满
若有n个关键字，就要n+1个查找失败结点
分块查找
- 算法思想:
索引表中保存每块的最大关键字和分块存储空间
块内无序，块间有序
**先在索引表中索引分块（可顺序，可折半）
然后在块内顺序查找** - 性能分析：
ASL=查找索引表的ASL+查找分块的ASL
散列表
- 概念：
关键字通过hash函数与存储地址直接相关
不同关键字映射到同一个地址，这些关键字就是同义词
同义词的冲突叫冲突。
聚集（堆积）：非同义词的冲突
装填因子（负载因子）：表中记录数/散列表的长度；降低装填因子来减少冲突；直接影响散列表的查找效率(ASL)。
散列表中，ASL平均查找长度与装填因子直接相关，查找效率不依赖已有表项数目或表长。 - 处理冲突的方法
拉链法：
所有的同义词存储在同一个链表中
ASL:
对空节点的查找次数是0
冲突越多，查找效率越低，理想情况下时间复杂度可以是o(1)
链地址法不会产生堆积现象
开放地址法
线性探测法：
- 查找：
同义词和非同义词都要被检查；
空位置的判断也算作一次比较；
越早遇到空位就越早确定查找失败。 - 过程：
hash一下后，一个一个往后查，查到空则停，但空位置也算一次比较 - 删除
不能简单地直接将被删除空间设置为空，否则会截断在它之后填入的同义词结点的查找路径，可以做一个“删除标记”进行删除标记 - 缺点
同义词与非同义词之间的冲突很容易造成聚集现象，影响查找效率 - ASL
平方探测法
- 过程
先hash一下，然后左右跳跃的查找，查到空则停。
- 优点
相比于线性探测更加不会产生聚集现象
再散列法
- 除了原始散列函数之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新的地址，知道不冲突为止
伪随机序列法
- di是一个伪随机数
拉链法和开放地址法的ASL计算：
ASL成功=（每个成功元素比较次数和）/元素个数
ASL失败=（每次hash失败比较次数和）/m
注意 ：
- 拉链法的空不算比较次数，但开放地址的空还算一次比较次数（而且开放地址到空才停止）
失败的比较次数注意范围，到%m就可以了，因为%m后面不是每次hash能hash到的，只是散列表的长度而已。
- 分母m是模的值
