无论是折半查找、二叉排序树查找还是B树，性能都依赖于查找中的比较次数。
一种理想情况是不经过任何比较，一次直接定位索要查找的记录，即：若数据结构中存在关键字和K相等，则其必定在f(K)的存储位置上，我们称这个对应关系f为哈希函数。
冲突(Collision)：对不同的关键字，可能得到同一哈希地址，即存在key1!=key2，但f(key1)=f(key2)。此时称为冲突或碰撞。
由于在实际应用中，哈希函数都是压缩函数，所以冲突只能尽可能的减少，很难完全避免。
哈希表：根据[......]
一、后缀的定义
后缀数组，做为后缀树的替代品，可以解决很多棘手的字符串处理问题。
长度为n的String[0, 1...n-1]
定义后缀Suffix(i)=sub_string[i...n-1]。
例如字符串aabaaaab，Suffix[1] = abaaaab，Suffix[7]=b。
考虑到空间问题，以及C系列语言中，Suffix[i]非常好求得（&str[i]即可）。一般不会保存Suffix[i]这个数组。
二、后缀数组sa和逆运算数组ran[......]
问题描述
要求从N个元素中随机的抽取k个元素，其中N无法确定(N是个流，可能无穷大)。
这种应用的场景一般是数据流的情况下，由于数据只能被读取一次，而且数据量很大，并不能全部保存，因此数据量N是无法在抽样开始时确定的；但又要保持随机性，于是有了这个问题。所以搜索网站有时候会问这样的问题。
这里的核心问题就是“随机”，怎么才能是随机的抽取元素呢？我们设想，买彩票的时候，由于所有彩票的中奖概率都是一样的，所以我们才是“随机的”买彩票。那么要使抽取数据也随机，必须使每一个数据被抽样出[......]
键树，又称数字查找树(Digital Search Trees)是一棵度>=2的树，每个结点只含有组成关键字的符号。
键树有两种存储结构：
1、树的孩子-兄弟链表来表示键树。
每个Node有三个域：first指向第一棵子树的根指针；next指向右兄弟；info（可选的）记录附加数据。如下图：
查找过程是，从根结点出发，顺着first查找，如果相等，继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配，查找不成功。[......]