重学数据结构（八、查找）

水深无声 2022-12-24 15:47 180阅读 0赞

### 文章目录 ###

*  一、查找的基本概念
 *  二、线性表的查找
 *   *  1、顺序查找
     *   *  1.1、基本思想
         *  1.2、算法实现
         *  1.3、算法分析
     *  2、二分查找
     *   *  2.1、基本思想
         *  2.2、算法实现
         *  2.3、算法分析
     *  3、分块查找
 *  三、树表的查找
 *   *  1、二叉排序树
     *   *  1.1、二叉排序树基本概念
         *  1.2、二叉排序树特点
         *  1.3、二叉查找树的操作
     *  2、平衡二叉树
     *  3、B树
     *  4、B+树
 *  四、散列表的查找
 *   *  1、散列表的概念
     *  2、散列函数的构造方法
     *   *  2.1、数字分析法
         *  2.2、平方取中法
         *  2.3、折叠法
         *  2.4、除留余数法
         *  2.5、随机数法
     *  3、处理冲突的方法
     *   *  3.1、开放地址法
         *   *  3.1.1、线性探测法
             *  3.1.2、二次探测法
             *  3.1.3、伪随机探测法
         *  3.2、链地址法
     *  4、散列表的算法
 *  五、总结

查找是各种软件系统中经常用到的操作。查找的效率非常重要，大型的系统尤其如此。

# 一、查找的基本概念 #

首先来看一些查找的基本概念和术语。

*  **查找表**  
    **查找表**是由同一类型的数据元素（或记录）构成的集合。由于 “集合” 中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵活的数据结构，可以利用其他的数据结构来实现，例如线性表、树表及散列表等。
 *  **关键字**  
    **关键字**是数据元素（或记录） 中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字 可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）。反之，称用以识别若千记录的关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。
 *  **查找**  
    **查找**是指根据给定的某个值，在查找表中确定一个其关键字等千给定值的记录或数据元素。若表中存在这样的一个记录， 则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个 “空” 记录或 “空” 指针。
 *  **动态查找表和静态查找表**  
    若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为**动态查找表**，否则称之为静态查找表。换句话说，动态查找表的表结构本身是在查找过程中动态生成的，即在创建表时，对千给定值， 若表中存在其关键字等于给定值的记录， 则查找成功返回；否则插入关键字等千给定值的记录。
 *  **平均查找长度**  
    为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法，在查找成功时的**平均查找长度(Average Search Length, ASL)**。

# 二、线性表的查找 #

在查找表的组织方式中，线性表是最简单的一种。

## 1、顺序查找 ##

### 1.1、基本思想 ###

在表的组织方式中，线性表是最简单的一种。而顺序查找是线性表查找中最简单的一种。

顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次扫描到的结点关键字和给定的K值相比较，若当前扫描到的结点关键字与 K相等，则查找成功；若扫描结束后，仍未找到关键字等于 K的结点，则查找失败。

图1:顺序查找示例图

![在这里插入图片描述][20201212161125883.png_pic_center]

順序査找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。

### 1.2、算法实现 ###

/** * 顺序查找 * @param data * @param key * @return */
        public int linearSearch(int[] data,int key){ 
            //遍历查找
            for (int i=0;i<data.length;i++){ 
                //查找到
                if (key==data[i]){ 
                    return i;
                }
            }
            //没有查找到
            return -1;
        }

### 1.3、算法分析 ###

成功时的顺序査找的平均査找长度为:

![在这里插入图片描述][20201212161327375.png_pic_center]  
在数据量为n的情况下，线性表的平均查找长度：

(n+……+2+1)/n=(n+1)/2

顺序查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，  
或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为 n，线性查找的时间复杂度便为 O(n)。

所以虽然顺序查找比较简单，且对表的结构无任何要求，但是查询效率较低，所以当n较大时不宜采用顺序査找。

## 2、二分查找 ##

二分查找也叫折半查找。

### 2.1、基本思想 ###

二分查找是一种效率相对较高的线性表查找方式，它要求被查找的线性表是有序的。

二分查找的基本思想是：先确定待查找记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。

具体步骤如下：

*  (1) 首先确定该区间的中点位置：mid=(low +high)/ 2
 *  (2) 然后将待查的 A：值与 R\[mid\].key 比较。若相等，则査找成功并返回此位置，否则须确定新的査找区间，继续二分査找。具体如下：  
     ① 若R\[mid\].key>K：,则由表的有序性可知 R\[mid…n\].keys 均大于 K，因此若表中存在关键字等于尺的结点，则该结点必定是在位置 mid 左边的子表及\[1…mid- 1\]中，故新的査找区间是左子表R\[1,……,mid-1\]。  
      ② 类似地，若R\[mid\].key<K：，则要査找的 K必在 mid 的右子表R\[mid+1,……,n\]中，即新的査找区间是右子表R\[mid+1,……n\]。下一次查找是针对新的查找区间进行的。

图2:二分查找示例图

![在这里插入图片描述][20201212162948782.png_pic_center]

### 2.2、算法实现 ###

*  非递归实现：

/** * 二分查找-非递归 * @param data * @param key * @return */
        public int binarySearch(int[] data,int key){ 
            int mid;      //置查找区间初值
            int left=0;
            int right=data.length-1;
            while (left<right){ 
                mid=(left+right)/2;
                if (key==data[mid]){    //找到待查元素
                    return mid;
                }else if (key>data[mid]){  //在右子表查找
                    left=mid+1;
                    mid=(left+right)/2;
                }else{            //在左子表查找
                    right=mid-1;
                    mid=(left+right)/1;
                }
            }
            return -1;        //没有查找到待查元素
        }

*  递归实现

/** * 二分查找-递归 * * @param data * @param left * @param right * @param key * @return */
        public int binarySearchRescu(int[] data, int left, int right, int key) { 
            if (left > right) { 
                return -1;
            }
            int mid = (left + right) / 2;
            if (key == data[mid]) { 
                return mid;
            } else if (key > data[mid]) {  //在右子表查找
                return binarySearchRescu(data, mid + 1, right, key);
            } else { 
                return binarySearchRescu(data, left, mid - 1, key);
            }
        }

### 2.3、算法分析 ###

折半查找的时间复杂度为 O(log2n）, 折半查找的效率比顺序查找高，但折半查找只适用千有序表，且限于顺序存储结构。

折半查找的优点是：比较次数少，查找效率高。其缺点是：对表结构要求高，只能用于顺序存储的有序表。

如果对无序表进行二分查找，查找前需要排序，而排序本身是一种费时的运算。同时为了保持顺序表的有序性，对有序表进行插入和删除时，平均比较和移动表中一半元素，这也是一种费时的运算。因此，折半查找不适用于数据元素经常变动的线性表。

## 3、分块查找 ##

**分块查找**又称**索引顺序查找**。它是把顺序查找和二分査找相结合的一种查找方法，即把线性表分成若干块，块和块之间有序，但每一块内的结点可以无序。

分块查找的基本思想是：确定被査找的结点所在的块(采用二分查找法)后，对该块中的结点采用顺序查找。

分块査找介于顺序和二分查找之间，其优点是：在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。分块査找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算

# 三、树表的查找 #

在**[重学数据结构（六、树和二叉树）][Link 1]** 里，对大量的树进行了详细的描述和实现，所以针对树表的查找，下面只是是做一些简单的描述。

## 1、二叉排序树 ##

当用线性表作为表的组织形式时，可以用 3 种查找法。其中以二分査找效率最高。但由于二分査找要求表中结点按关键字有序，且不能用链表作存储结构，因此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多结点。这种由移动结点引起的额外时间开销，就会抵消二分査找的优点。也就是说，二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，最好使用二叉排序树。

### 1.1、二叉排序树基本概念 ###

二叉排序树又称为是二叉查找树或二叉搜索树。二叉排序树是具有下列性质的二叉树：

*  若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
 *  左、右子树也分别为二叉排序树；
 *  没有键值相等的节点。

图3:二分排序树示意图

![在这里插入图片描述][20201212175407280.png_pic_center]

### 1.2、二叉排序树特点 ###

由 BST性质可得：

*  (1) 二叉排序树中任一结点x，其左(右)子树中任一结点y若存在)的关键字必小(大)于 x 的关键字。
 *  (2) 二叉排序树中，各结点关键字是惟一的。  
    需要注意的是在实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中 BST 性质⑴ 里的“小于”改为“大于等于”，或将 BST性质(2)里的“大于”改为“小于等于”，甚至可同时修改这两个性质。
 *  (3) 按中序遍历该树所得到的中序序列是一个递增有序序列。

### 1.3、二叉查找树的操作 ###

*  **查找**：因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似， 也 是一个逐步缩小查找范围的过程。
 *  **插入和生成**  
    已知一个关键字值为 key 的结点 s, 若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。插入可以用下面的方法进行：  
     - (1) 若二叉树序树是空树，则 key 成为二叉树序树的根；  
     - (2) 若二叉树序树非空，则将 key 与二叉树序树的根进行比较，如果 key 的值等于根结点的值，则停止插入，如果 key 的值小于根结点的值，则将 key 插入左子树，如果 key的值大于根结点的值，则将 key 插入右子树。

## 2、平衡二叉树 ##

二叉树虽然利于查找，但是存在一个最坏的情况——**二叉树退化为线性表**。

图4:二叉树退化

![在这里插入图片描述][20201212180241438.png]

所以就需要就需要引入一些特性来使二叉树保持平衡。

例如最早提出的平衡二叉树AVL树，是具有如下特性的二叉树：

*  (1 ) 左子树和右子树的深度之差的绝对值不超过1;
 *  (2) 左子树和右子树也是平衡二叉树。

图5:平衡二叉树示意图

![在这里插入图片描述][20201212180650990.png_pic_center]

## 3、B树 ##

B树也是一种平衡查找树，不过不是二叉树。

B树也称B-树，它是一种多路平衡查找树。

一棵m阶的B树定义如下：

*  每个节点最多有m-1个关键字（可以存有的键值对）。
 *  根节点最少可以只有1个关键字。
 *  非根节点至少有m/2个关键字。
 *  每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
 *  所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
 *  每个节点都存有索引和数据，也就是对应的key和value。

图6:B树示意图

![在这里插入图片描述][20201212180449827.png_pic_center]

## 4、B+树 ##

B+树是B树的变体，也是一种多路搜索树。

B+树·和B树有一些共同的特性：

*  根节点至少一个元素
 *  非根节点元素范围：m/2 <= k <= m-1

B+树和B树也有一些不一样的地方：

*  B+树有两种类型的节点：非叶子结点（也称索引结点）和叶子结点。非叶子节点不存储数据，只存储索引，数据都存储在叶子节点。
 *  非叶子结点中的key都按照从小到大的顺序排列，对于非叶子结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
 *  每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
 *  父节点存有右孩子的第一个元素的索引。

图7:B+树示意图

![在这里插入图片描述][20201212180932952.png_pic_center]

# 四、散列表的查找 #

## 1、散列表的概念 ##

在前面学习了关于线性表、树表的查找，这类查找方法都是以关键字的比较为基础的。

在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系， 其查找时间与表的长度有关，特别是当结点个数很多时，查找时要大量地与无效结点的关键字进行比较，致使查找速度很慢。

如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是**散列查找法 （HashSearch)**的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址， 即使用关键字到地址的直接转换方法，而不需要反复比较。因此，**散列查找法**又叫**杂凑法**或**散列法**。

图8:哈希示意图

![在这里插入图片描述][20201212234145220.png_pic_center]

下面来看一些散列查找法的术语：

*  **散列函数和散列地址：**在记录的存储位置p和其关键字key 之间建立一个确定的对应关系H, 使 p=H(key), 称这个对应关系H为散列函数，p为散列地址。
 *  **散列表：**一个连续有限的地址空间，用来存储散列函数计算的到的散列地址。通常散列表的存储结构是一个一维数组，散列地址是数组的下标。
 *  **冲突和同义词**：对不同的关键字可能得到同一散列地址，即key不等于key2 ,而H(key1)=H(key2），这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词，key1与key2互称为同义词。

## 2、散列函数的构造方法 ##

构造散列函数的方法很多，一般来说，应根据具体问题选用不同的散列函数，通常要考虑以下因素：

*  (1)散列表的长度；
 *  (2) 关键字的长度；
 *  (3)关键字的分布情况；
 *  (4)计算散列函数所需的时间；
 *  (5) 记录的查找频率。

构造一个 “好” 的散列函数应遵循以下两条原则：

*  (1)函数计算要简单，每一关键字只能有一个散列地址与之对应；
 *  (2) 函数的值域需在表长的范围内， 计算出的散列地址的分布应均匀，尽可能减少冲突。

下面介绍构造散列函数的几种常用方法。

### 2.1、数字分析法 ###

如果事先知道关键字集合， 且每个关键字的位数比散列表的地址码位数多，每个关键字由n位数组成，如K1…Kn , 则可以从关键字中提取数字分布比较均匀的若干位作为散列地址。

例如，有80个记录，其关键字为8位十进制数。假设散列表的表长为100, 则可取两位十进制数组成散列地址，选取的原则是分析这80个关键字，使得到的散列地址尽最避免产生冲突。

假设这80个关键字中的一部分如下所列：

图9:数字分析法关键字示例

![在这里插入图片描述][20201213135327696.png_pic_center]

对关键字全体的分析中可以发现：第1、2位都是"8 、1", 第3位只可能取3或4, 第4位可能取2、 5或 7,因此这 4 位都不可取。由千中间的 4 位可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另外两位的叠加求和后舍去进位作为散列地址。

数字分析法的适用情况：事先必须明确知道所有的关键字每一位上各种数字的分布情况。

在实际应用中，例如，同一出版社出版的所有图书，其ISBN号的前几位都是相同的，因此，若数据表只包含同一出版社的图书，构造散列函数时可以利用这种数字分析排除ISBN号的前几位数字。

### 2.2、平方取中法 ###

通常在选定散列函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，如果取关键字平方后的中间几位或其组合作为散列地址，则使随机分布的关键字得到的散列地址也是随机的，具体所取的位数由表长决定。平方取中法是一种较常用的构造散列函数的方法。

图9:平方取中法示意图

![在这里插入图片描述][20201213141302476.png_pic_center]

平方取中法的适用情况：不能事先了解关键字的所有情况，或难千直接从关键字中找到取值较分散的几位。

### 2.3、折叠法 ###

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位） 作为散列地址，这种方法称为折叠法。根据数位叠加的方式，可以把折叠法分为移位叠加和边界叠加两种。移位叠加是将分割后每一部分的最低位对齐，然后相加；边界叠加是将两相邻的部分沿边界来回折叠，然后对齐相加。

例如，当散列表长为 1000 时，关键字key = 45387765213, 从左到右按 3 位数一段分割，可以得到 4 个部分：453 、 877 、 652 、 13。分别采用移位叠加和边界叠加，求得散列地址为 995 和914, 如下图 所示。

图10:由折叠法求得散列地址

![在这里插入图片描述][20201213142355875.png_pic_center]

折叠法的适用情况：适合于散列地址的位数较少，而关键字的位数较多，且难千直接从关键字中找到取值较分散的几位。

### 2.4、除留余数法 ###

假设散列表表长为m, 选择一个不大千m的数p, 用p去除关键字，除后所得余数为散列地址，即

H(key) = key%p

这个方法的关键是选取适当的p, 一般情况下，可以选p为小于表长的最大质数。例如，表长m= 100 , 可取p= 97 。

除留余数法计算简单，适用范围非常广，是最常用的构造散列函数的方法。它不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模，这样能够保证散列地址一定落在散列表的地址空间中。

### 2.5、随机数法 ###

选取一个随机函数，取关键字的随机函数的值为散列地址。

H(k)=random(key)

## 3、处理冲突的方法 ##

选择一个 “好” 的散列函数可以在一定程度上减少冲突，但在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列法的另一个关键问题。创建散列表和查找散列表都会遇到冲突，两种情况下处理冲突的方法应该一致。

处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通常分两大类：**开放地址法**和**链地址法**。

### 3.1、开放地址法 ###

**开放地址法**的基本思想是：把记录都存储在散列表数组中，当某一记录关键字 key的初始散列地址H0=H(key)发生冲突时，以H0为基础 ，采取合适方法计算得到另一个地址H1, 如果H1仍然发生冲突，以H1为基础再求下一个地址H2，若H2仍然冲突，再求得H3。依次类推，直至Hk不发生冲突为止，则Hk为该记录在表中的散列地址。

这种方法在寻找 “下一个 “ 空的散列地址时，原来的数组空间对所有的元素都是开放的，所以称为开放地址法。通常把寻找 “下一个 “ 空位的过程称为**探测**，上述方法可用如下公式表示：

Hi = (H(key) +di)%m   i = 1, 2, …，k(k<=m-1)

#### 3.1.1、线性探测法 ####

di= l, 2, 3, …, m-1

这种探测方法可以将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元顺序寻找空单元，如果到最后 一个位置也没找到空单元，则回到表头开始继续查找，直到找到一个空位，就把此元素放入此空位中。如果找不到空位，则说明散列表已满，需要进行溢出处理。

#### 3.1.2、二次探测法 ####

![在这里插入图片描述][20201213144615841.png_pic_center]

#### 3.1.3、伪随机探测法 ####

di = 伪随机数序列

例如，散列表的长度为 11, 散列函数 H(key) = key%11, 假设表中已填有关键字分别为 17 、60 、 29 的记录，如图 11 (a) 所示。现有第四个记录，其关键字为 38, 由散列函数得到散列地址为 5, 产生冲突。

*  若用**线性探测法处**理时，得到下一个地址 6, 仍冲突；再求下一个地址 7, 仍冲突；直到散列地址为 8 的位置为 “空” 时为止，处理冲突的过程结束，38 填入散列表中序号为 8 的位置，如图11 (b) 所示。
 *  若用**二次探测法**，散列地址 5 冲突后，得到下一个地址 6, 仍冲突；再求得下一个地址 4 , 无冲突， 38 填入序号为 4 的位置，如图 11 ©, 所示。
 *  若用**伪随机探测法**，假设产生的伪随机数为 9, 则计算下一个散列地址为(5+9)%11 = 3, 所以38 填入序号为 3 的位置，如图 11 (d) 所示。

图11:用开放地址法处理冲突时，关键字为 38 的记录插入前后的散列表

![在这里插入图片描述][20201213145223628.png_pic_center]

从上述线性探测法处理的过程中可以看到一个现象：当表中 i, i+1, i+2 位置上已填有记录时，下一个散列地址为i、i+ I 、i+2和i+3 的记录都将填入i+3 的位置，这种在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作 “**二次聚集**＂（或称作 “**堆积**＂），即在处理同义词的冲突过程中又添加了非同义词的冲突。

可以看出，上述三种处理方法各有优缺点。

*  线性探测法的优点是：只要散列表未填满，总能找到一个不发生冲突的地址。缺点是：会产生 ”二次聚集“ 现象。
 *  而二次探测法和伪随机探测法的优点是：可以避免 “二次聚集“ 现象。缺点也很显然：不能保证一定找到不发生冲突的地址。

### 3.2、链地址法 ###

链地址法的基本思想是：把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有 m 个散列地址就有 m 个单链表，同时用数组 HT\[0…m-1\]存放各个链表的头指针，凡是散列地址为 i 的记录都以结点方式插入到以 HT\[i\]为头结点的单链表中。

图13:链地址法

![在这里插入图片描述][20201213151759966.png_pic_center]

该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。对采用链地址法的哈希实现的查找分为两步，首先是根据散列值找到等一应的链表，然后沿着链表顺序找到相应的键。

## 4、散列表的算法 ##

散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表主要用于快速查找，且插入和删除均要用到査找操作。

接下来建立一个简单的散列表，其散列函数采用上述的除留余数法，处理冲突的方法采用开放定址法下的线性探测法。

public class HashTable { 
        int[] elem;
        int count;
        private static final int Nullkey = -32768;
    
        public HashTable(int count) { 
            this.count = count;
            elem = new int[count];
            for (int i = 0; i < count; i++) { 
                elem[i] = Nullkey; // 代表位置为空
            }
        }
    
        /* * 散列函数 */
        public int hash(int key) { 
            return key % count; // 除留余数法
        }
    
        /* * 插入操作 */
        public void insert(int key) { 
            int addr = hash(key); // 求散列地址
            while (elem[addr] != Nullkey) {  // 位置非空，有冲突
                addr = (addr + 1) % count; // 开放地址法的线性探测
            }
            elem[addr] = key;
        }
    
        /* * 查找操作 */
        public boolean search(int key) { 
            int addr = hash(key); // 求散列地址
            while (elem[addr] != key) { 
                addr = (addr + 1) % count; // 开放地址法的线性探测
                if (addr == hash(key) || elem[addr] == Nullkey) {  // 循环回到原点或者到了空地址
                    System.out.println("要查找的记录不存在！");
                    return false;
                }
            }
            System.out.println("存在记录:" + key + ",位置为：" + addr);
            return true;
        }
    
        public static void main(String[] args) { 
            int[] arr = { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34};
            HashTable aTable = new HashTable(arr.length);
            for (int a : arr) { 
                aTable.insert(a);
            }
            for (int a : arr) { 
                aTable.search(a);
            }
        }
    }

*  (1) 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由千 ＂冲突＂ 的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表查找效率的量度。
 *  (2) 查找过程中需和给定值进行比较的关键字的个数取决千三个因素：散列函数、处理冲突的方法和散列表的装填因子。  
    散列表的**装填因子α**定义为:

![在这里插入图片描述][20201213153419104.png_pic_center]α标志散列表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

*  (3) 散列函数的 “好坏“ 首先影响出现冲突的频繁程度。但一般情况下认为：凡是 ＂均匀的＂散列函数，对同一组随机的关键字，产生冲突的可能性相同，假如所设定的散列函数是 ＂均匀"的，则影响平均查找长度的因素只有两个—一处理冲突的方法和装填因子 α。

用几种不同方法处理冲突的散列表的平均查找长度

![在这里插入图片描述][20201213153709781.png_pic_center]

# 五、总结 #

查找是数据处理中经常使用的一种操作。 这里主要介绍了对查找表的查找 ， 查找表实际上仅仅是一个集合，为了提高查找效率，将查找表组织成不同的数据结构，主要包括3种不同结构的查找表：线性表、 树表和散列表。

*  **(1)线性表的查找**  
    主要包括顺序查找、折半查找和分块查找。

顺序查找、折半查找和分块查找的比较

![在这里插入图片描述][20201213154002277.png_pic_center]

*  **(2)树表的查找**  
    树表的结构主要包括二叉排序树、 平衡二叉树、 B-树和B+树

\* 二叉排序树的查找过程与折半查找过程类似

折半查找和二叉排序树查找虳比较

![在这里插入图片描述][20201213154218194.png_pic_center]  
  \* 二叉排序树在形态均匀时性能最好，而形态为单支树时其查找性能则退化为与顺序查找相同，因此，二叉排序树最好是一棵平衡二叉树。 平衡二叉树的平衡调整方法就是确保二叉排序树在任何情况下的深度均为 O(log2n），平衡调整方法分为4种： LL型、RR型、LR型和RL型。

\* B-树是一种平衡的多叉查找树，是一种在外存文件系统中常用的动态索引技术。 在 B-树上进行查找的过程和二叉排序树类似，是一个顺指针查找结点和在结点内的关键字中查找交叉进行的过程。 为了确保B-树的定义，在B-树中插入一个关键字，可能产生结点的 “分裂＂， 而删除一个关键字，可能产生结点的 “合并＂。

\* B+树是一种B-树的变型树，更适合做文件系统的索引。 在B+树上进行随机查找、 插入和删除的过程基本上与B-树类似，但具体实现细节又有所区别。

*  **(3)散列表的查找**  
    散列表也属线性结构，但它和线性表的查找有着本质的区别。 它不是以关键字比较为基础进行查找的，而是通过一种散列函数把记录的关键字和它在表中的位置建立起对应关系，并在存储记录发生冲突时采用专门的处理冲突的方法。这种方式构造的散列表，不仅平均查找长度和记录总数无关，而且可以通过调节装填因子，把平均查找长度控制在所需的范围内。

散列查找法主要研究两方面的问题：如何构造散列函数，以及如何处理冲突。

\* 构造散列函数的方法很多，除留余数法是最常用的构造散列函数的方法。它不仅可以对关键字直接取模， 也可在折叠、平方取中等运算之后取模。

\* 处理冲突的方法通常分为两大类：开放地址法和链地址法，二者之间的差别类似千顺序表和单链表的差别。

开放地址法和链地址法的比较

![在这里插入图片描述][20201213154757248.png_pic_center]

--------------------

上一篇：[重学数据结构（七、图）][Link 2]

本博客为学习笔记，参考资料如下！  
水平有限，难免错漏，欢迎指正！

**参考：**

【1】：邓俊辉 编著. 《数据结构与算法》  
【2】：王世民 等编著 . 《数据结构与算法分析》  
【3】： Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》  
【4】：严蔚敏、吴伟民 编著 . 《数据结构》  
【5】：程杰 编著 . 《大话数据结构》  
【6】：[图解：如何理解与实现散列表][Link 3]  
【7】：[算法图解之散列表][Link 4]  
【8】：[数据结构与算法-Day17-哈希(散列)表][-Day17-]  
【9】：[Java数据结构与算法解析(十二)——散列表][Java]  
【10】：[【Java】 大话数据结构(13) 查找算法(4) （散列表（哈希表））][Java_ _13_ _4_]

[20201212161125883.png_pic_center]: /images/20221120/2428536192d34fa495d9f72ebfd73059.png
[20201212161327375.png_pic_center]: /images/20221120/d85af03b27624151b4988fd5f3dfe6cf.png
[20201212162948782.png_pic_center]: https://img-blog.csdnimg.cn/20201212162948782.png?#pic_center
[Link 1]: https://blog.csdn.net/sinat_40770656/article/details/108805930
[20201212175407280.png_pic_center]: https://img-blog.csdnimg.cn/20201212175407280.png?#pic_center
[20201212180241438.png]: https://img-blog.csdnimg.cn/20201212180241438.png
[20201212180650990.png_pic_center]: https://img-blog.csdnimg.cn/20201212180650990.png?#pic_center
[20201212180449827.png_pic_center]: https://img-blog.csdnimg.cn/20201212180449827.png?#pic_center
[20201212180932952.png_pic_center]: https://img-blog.csdnimg.cn/20201212180932952.png?#pic_center
[20201212234145220.png_pic_center]: https://img-blog.csdnimg.cn/20201212234145220.png?#pic_center
[20201213135327696.png_pic_center]: https://img-blog.csdnimg.cn/20201213135327696.png?#pic_center
[20201213141302476.png_pic_center]: https://img-blog.csdnimg.cn/20201213141302476.png?#pic_center
[20201213142355875.png_pic_center]: https://img-blog.csdnimg.cn/20201213142355875.png?#pic_center
[20201213144615841.png_pic_center]: https://img-blog.csdnimg.cn/20201213144615841.png?#pic_center
[20201213145223628.png_pic_center]: https://img-blog.csdnimg.cn/20201213145223628.png?#pic_center
[20201213151759966.png_pic_center]: https://img-blog.csdnimg.cn/20201213151759966.png?#pic_center
[20201213153419104.png_pic_center]: https://img-blog.csdnimg.cn/20201213153419104.png?#pic_center
[20201213153709781.png_pic_center]: https://img-blog.csdnimg.cn/20201213153709781.png?#pic_center
[20201213154002277.png_pic_center]: https://img-blog.csdnimg.cn/20201213154002277.png?#pic_center
[20201213154218194.png_pic_center]: https://img-blog.csdnimg.cn/20201213154218194.png?#pic_center
[20201213154757248.png_pic_center]: https://img-blog.csdnimg.cn/20201213154757248.png?#pic_center
[Link 2]: https://blog.csdn.net/sinat_40770656/article/details/108964134
[Link 3]: https://xie.infoq.cn/article/c371774d14e320ccf916c6c55
[Link 4]: https://www.cnblogs.com/lshedward/p/10460958.html
[-Day17-]: https://juejin.cn/post/6844904161130053640
[Java]: https://blog.csdn.net/u012124438/article/details/78230478
[Java_ _13_ _4_]: https://www.cnblogs.com/yongh/p/9284896.html