一、符号表
1、API
2、有序符号表
3、用例举例
4、无序链表中的顺序查找
5、有序数组中的二分查找
6、对二分查找的分析
7、预览
本章我们学习了6种符号表的实现下面是其简单预览：
| 使用的数据结构 | 实现 | 优点 | 缺点 |
|---|---|---|---|
| 链表（顺序查找） | SequentialSearchST | 适用于小型问题 | 对于大型符号表很慢 |
| 有序数组（二分查找） | BinarySearchST | 最优的查找效率和空间需求，能够进行有序性的相关操作 | 插入操作很慢 |
| 二分查找树 | BST | 实现简单，能够进行有序性的相关操作 | 没有性能上界的保证 链接需要额外的空间 |
| 平衡二叉查找树 | RedBlackBST | 最优的查找和插入效率，能够进行有序性的相关操作 | 链接需要额外的空间 |
| 散列表 | SeparateChainHashST LinearProbingHashST |
能够快速的查找和插入常见类型的数据 | 需要计算每种类型的数据散列 无法进行有序性的相关操作 链接和空结点需要额外的空间 |
二、二叉查找数
三、平衡查找树
四、散列表
使用散列查找算法分为两步：1、使用散列函数将键转化为数组的一个索引；2、处理哈希碰撞冲突的过程
两种解决哈希碰撞的方法：拉链法和线性探测法
1、散列函数
如果我们有一个能保存M个键值对的数组，那么我们就需要一个能将任意键转化为该数组范围内（0～M-1）索引的散列函数
下面我们来看看对不同键的散列函数
正整数
除留余数法
浮点数
乘上实数
字符串
2、基于拉链法的散列表
散列函数的第二步是处理哈希碰撞，也就是处理两个或多个键相同的情况，一种直接的办法就是：将大小为M的数组中的每个元素指向一条链表，链表中的每个节点都存储了散列值为该元素的索引的键值对，此乃 拉链法。
3、基于线性探测法的散列表
实现散列表的另一种方式是用大小为M的数组保存N个键值对（M>N）。我们需要依靠数组中的空位解决冲突。基于这种策略的所有方法都被称为开放地址散列表。
开放地址散列法中最简单的就是线性探测法：当碰撞发生时，我们直接检查散列表的下一个位置（索引+1），这样线性探测就会发生下面三种情况：
- 命中
- 未命中
- 继续查找
五、应用
计算机发展早期，符号表帮助程序员从使用机器语言的数字进化到汇编语言中使用符号名称
小小的总结：
- 顺序查找（无序链表）
- 二分查找（有序数组）
- 二叉树查找（二叉查找树）
- 2-3树查找（红黑树）
- 拉链法（链表数组）
- 线性探测法（并行数组）