查找表分析（总论）

 

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

          1.  查找表的概念

          2.  静态查找表

          3.  动态查找表

          4.  Hash表，以及Map

 

 

                            本文是查找表系列之一:查找表的概念

 

  定义：

     查找表：是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。

 

  对查找表的操作:

• 查询某个“特定的”数据元素是否在查找表中；
• 检索某个“特定的”数据元素的各种属性；
• 在查找表中插入一个数据元素；
• 从查找表中删去某个数据元素。

   分类：

 

     按照记录在表中的位置和它的关键字之间的关系可以分为：静态查找表动态查找表和Hash表。

       其中静态查找表和动态查找表都是：记录在表中的位置和它的关键字之间不存在一个确定的关系。

       Hash表：记录在表中的位置和它的关键字之间存在一个确定的关系。

 

       静态查找表：

              仅作查询和检索操作的查找表。

      

       动态查找表

            在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。

 

       哈希表：

           根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“映象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。

 

   查找性能分析：

        无论是静态查找表还是动态查找表， 查找的过程均为给定值依次和关键字集合中各个关键字进行比较。查找的效率取决于和给定值进行比较的关键字个数。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。其平均查找长度始终都不可能为零。(平均查找长度ASL始终为长度n的函数)

 

    Hash表中，记录在表中位置和其关键字之间存在一种确定的关系，我们可以预先知道所查关键字在表中的位置，理想状态下ASL可以达到0，因为hash冲突等原因，哈希表的平均查找长度是 a 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 a ，使得平均查找长度限定在某个范围内。—— 这是哈希表所特有的特点。

 

 

 

   具体查找表特征分析： 

 

      静态查找表中

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

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

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

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

 

     动态查找表

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

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

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

 

        Hash表：

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

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

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

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

 

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

 

•  
  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法

         3. 处理冲突的方法 ：

              “处理冲突” 的实际含义是：为产生冲突的关键字寻找下一个哈希地址。

          1.开放定址法

            2.再哈希法

            3.链地址法

 

 

下一节先实现Hash表，然后模仿JDK中的HashMap自己山寨一份