顺序查找 $ASL=\frac{N+1}{2}$
折半查找 $ASL=\lfloor \log_2 N \rfloor +1$
斐波那契查找 $ASL=O(\log_2 N)$。平均性能比折半查找好，最坏性能比折半查找差。
索引查找：划分子表。
二叉搜索树 BST：
- 插入：执行搜索操作，失败后插入。
- 删除：叶子节点直接删除；只有一个子节点，直接接上；左右子节点都存在时，可用中序前驱或中序后继替换。
- 旋转
中序遍历二叉搜索树得到有序序列。
AVL树：左子树和右子树都是 AVL 树，且高度之差的绝对值不超过 1。
- 插入：从插入位置向根回溯，检查各点的平衡性，进行旋转操作。
- 删除
高度为 $h$ 的 AVL 树，最少的节点数为斐波那契数列中 $f_{h+2}-1$。
另有 B-树、2-3-4树、红黑树。
散列：
- 散列函数：简单，近似随机。例：乘法，取模，折叠，平方取中。
- 冲突处理：链地址法，开放地址法（线性探测，双重散列）
- 冗余度和冲突是一对矛盾，不可直接删除元素
- 冲突处理：链地址，开放地址（线性探测、双重散列）
- 应用：字符串匹配，搜索引擎，信息安全，内容鉴别
- 缺陷：动态性能差、最坏性能差、忽略逻辑关系
安全的哈希函数：
- H能够应用到大小不一的数据上
- H能够生成大小固定的输出
- 对干任意给定的x，H(x)的计算相对简单
- 对于任意给定的h，要发现满足H(x)=h的x在计算上不可行
- 对于任意给定的块x，要发现满足H(y)＝H(x)且y!=x在计算上不可行
- 要发现满足H(x)=H(y) 的(x,y)对在计算上不可行
常用的有
- MD2/MD4/MD5算法
- SHA/SHA-1算法
- 生日攻击