第三章 查找

1.符号表
a.有序符号表是值键都为可比较对象的符号表.它具有最大键,最小键,向下取整(floor)和向上取整(ceiling)等操作,还可以进行排名(rank),选择(select)和范围查找.

b.一种简单的符号表实现是使用无序链表.插入和查找都需要对链表进行遍历,时间复杂度都为O(N).

c.有序符号表可以用一对平行数组来实现,一个存储键,一个存储值.用二分查找来实现rank函数,大大减少了每次查找所需的比较次数.查找的时间复杂度为O(lgN).但是插入需要移动大量元素,所以插入的时间复杂度仍为O(N).它适用于只需要大量查找的符号表.

2.二叉树查找
使用二又查找树的算法的运行时间取决于树的形状，而树的形状又取决于键被插人的先后顺序。在最好的情况下，一棵含有N个结点的树是完全平衡的，每条空链接和根结点的距离都为~lgN。在最坏的情况下，搜索路径上可能有N个结点。

散列表
散列表是算法在时间和空间上作出权衡的经典例子。如果没有内存限制，我们可以直接将键作为（可能是一个超大的）数组的索引，那么所有查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为当键很多时需要的内存太大。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。事实上，我们不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间作出取舍。我们会使用概率论的经典结论来帮助我们选择适当的参数。

** 我们面对的第一个问题就是散列函数的计算，这个过程会将键转化为数组的索引。如果我们有一个能够保存M个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引（[0，M-1]范围内的整数）的散列函数。我们要找的散列函数应该易于计算并且能够均匀分布所有的键，即对于任意键，0到M-1之间的每个整数都有相等的可能性与之对应（与键无关）。这个要求似乎有些难以理解。那么要理解散列，就首先要仔细思考如何去实现这样一个函数。**

** 散列函数和键的类型有关。严格地说，对于每种类型的健都我们都需要一个与之对应的散列函数。如果键是一个数，比如社会保险号，我们就可以直接使用这个数；如果键是一个字符串，比如一个人的名字，我们就需要将这个字符串转化为一个数；如果键含有多个部分，比如邮件地址，我们需要用某种方法将这些部分结合起来。对于许多常见类型的键，我们可以利用Java提供的默认实现。我们会简略讨论多种数据类型的散列函数。你应该看看它们是如何实现的，因为你也需要为自定义的类型实现散列函数。**