查找
符号表：描述一张抽象的表格，信息存储其中，按照键值搜索获取。又称字典、索引。
有序数组中的二分查找
她使用的数据结构是一对平行数组，一个存储键一个存储值。键数组有序，可通过二分查找高效查找。但put操作需要将比它大的元素后移一位。同时要维护数组长度。
在N个键的有序数组中进行二分查找最多需要(lgN+1)次比较。
核心问题在于我们能否找到同时保证查找和插入操作都是对数级别的算法和数据结构。需要一种链式结构。
二叉查找树 BST
一颗二叉查找树是一颗二叉树，其中每个节点都含有一个键以及相关联的值，且每个节点的键都大于其左子树中的任意节点的键而小于右子树的任意节点。
使用二叉查找树的算法的运行时间取决于树的形状，而树的形状又取决于被插入的先后顺序。最好情况下N节点树平衡，每个空节点和根节点距离都为 lgN
二叉查找树得以广泛的应用的一个重要原因就是她能够保持键的有序性。
性能与树的高度成正比。
平衡二叉查找树（红黑树RedBlackBST）
树的高度始终 ~lgN 。
用标准的二叉查找树和一些额外的信息来表示2-3树。
链接分为两种类型：红链接将两个2-结点连接起来构成一个3-节点，黑链接则是2-3中的普通链接。
优点是无需修改就可以直接使用标准二叉查找树的get()方法。
能够将二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法。
红黑树定义，含有红黑链接并满足以下条件的二叉查找数：
- 红链接均为左链接
- 灭有任何一个节点同时和两条红链接相连
- 该树是完美黑色平衡的，及任意空连接到根节点的路径上的黑连接数量相同。
左旋转：
有一条红色的右链接需要被转化为左链接。
向单个2-结点插入新键：
一颗含有一个键的红黑树只含有一个2-结点。插入另一个键后，需要将他们旋转。如果新键小于老键，只需新增一个红色结点，新红黑树和单个3-结点完全等价。如果新键大于老键，那么新增的红色节点将会产生一条红色的右链接。需要用左旋转并修正根结点的链接。
向一颗双键树即一个3-结点中插入新键：（产生两条连续红链接的情况）
- 新键大于原树中两个键，因此她被连接到3-结点的右链接。
- 新键小于原树中两个键，被连接到最左边的空链接，长生了两条连续的红链接。只需将上层的红链接右旋转即可得到 1 的情况。
- 新键介于原树两键之间，会产生两条连续红链接，一条红色左链接一条红色右链接。先将红色右链接左旋转得到 2 的情况，再重复2的右旋转得到1的情况。
以上分别通过0次、1次、2次旋转得到一个 根节点在中间，左右链接都是红链接的情况。
颜色转换：
转换一个结点的两个红色子节点的颜色由红变黑，同时将父节点的颜色由黑变红。
根节点总是黑色：
每次插入后将根节点设为黑色。每次根节点由红变黑时树的黑链接高度加1
规则：
- 若右子节点是红色的而左子节点是黑色的，进行左旋转。
- 若左子结点是红色的且它的左子节点也为红色，右旋转。
- 若左右子节点均为红色，进行颜色转换。
红黑树的性质：
所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别。
无论插入顺序如何，红黑树都几乎完美平衡。
一颗大小为N的红黑树高度不会超过2lgN。
散列表
获取索引：
用算术操作将键转化为数组的索引来访问数组中的键值对。
查找算法分为两步：
- 用散列函数将查找的键转化为数组的一个索引。
- 处理碰撞冲突。两种解决方法：拉链法和线性探测法。
散列函数:
为一个数据类型实现一个优秀的散列方法需要满足三个条件，一致性，高效性，均匀性。
拉链法：
将数组中每个元素指向一条链表，链表中的每个节点都存储了散列值为该元素的索引的键值对。
线性探测法：
用大小为M的数组保存N个键值对，依靠数组中的空位解决碰撞冲突。开放地址散列表中最简单方法叫做线性探测法。
当碰撞发生时，直接检查散列表中的下一个位置，达到结尾时折回开头，知道找到该键或遇到一个空元素。
删除操作：需要将簇中被删除键的右侧所有键重新插入散列表。
散列表能够支持数组大小无关的常数级别的查找和插入操作是可能的。但：
- 每种类型的键都需要一个优秀的散列函数；
- 性能保证来自于散列函数的质量
- 散列函数的计算可能复杂且昂贵
- 难以支持有序性相关的符号表操作。
