查寻表分析（总论）

查找表分析（总论）

? 本来准备用一个文章来写关于查找表这一块的，结果发现内容实在太多了，所以现在决定分为以下三部分进行.? ?

? ?具体查找表特征分析：?

? ? ? 静态查找表中

? ? ? ? ?按存储结构： ? ?可以分为顺序结构和链式结构

?? ? ? ? 按元素的有序性：可以分为有序表和无序表

? ? ? ? ?无序表和链式表的查找方式，都需要遍历整个表进行比对,而顺序结构的有序表，可以通过折半查找算法来实现（具体算法/算法性能比较等参见静态表一节）

? ? ? ? ? 分有块序表:将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。索引顺序查找：又称分块查找

? ? ?动态查找表

? ? ? ? ? 特点：表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。

? ? ? ? ?动态生成二叉排序树（二叉查找树）--------平衡二叉树--------B-树B+树

? ? ? ? （本节主要是各种树的查找，增加，删除等操作的算法实现，放在最后实现）

? ? ? ? Hash表：

? ? ? ? ? ? 1)?? 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；

? ? ? ? ? ? 2)? 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key11 key2，而? f(key1) = f(key2)。

? ? ? ? ? ? 3).? 只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值

? ? ? ? ? ? ?因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。

? ? ? ? ? 2. 哈希函数构造的方法：