Carson带你学数据结构：图文详解 - 动态查找、静态查找、散列查找

客官°小女子只卖身不卖艺 2022-12-09 05:10 169阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

*  查找是 数据结构中的重要操作
 *  今天，我将主要讲解介绍 查找的相关知识，如查找算法等，希望你们会喜欢。

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

# 目录 #

![示意图][b062f3be2ee6a15f842a779b48132264.png]

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

# 1. 简介 #

*  本节将介绍关于 查找 的相关基础概念
 *  具体请看下图：

![示意图][6d14fdb0f157d80c8ca031c1dd2ea091.png]

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

# 2. 查找 需求场景 #

*  对于不同的查找需求场景，会采用不同的查找类型，最终采用的查找方式（查找算法）也有所不同
 *  具体如下

![示意图][eb5c0bd1123cab9692742daf31a2b0e3.png]

*  下面，将根据不同的查找需求类型，讲解对应的查找算法

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

# 3. 静态查找 #

*  定义：仅作 查找操作
 *  面向的数据结构：静态查找表
 *  算法：顺序查找、有序查找、线性索引查找
 *  具体介绍如下

### 3.1 顺序查找 ###

*  具体介绍如下

![示意图][489922510db3a369bad726f4558f4d7a.png]

### 3.2 有序查找 ###

> 1.  主要算法有：二分查找、插值 & 斐波那契
> 2.  本文 主要介绍 = 二分查找（也称：折半查找）

*  定义

![示意图][f15fd0f5ad7913fc3afc97c58fc937fe.png]

*  具体实现

public class BinarySearch {
    
        /**
         * 二分查找方法
         *  @param srcArray：有序数组
         * @param des：需要查找的元素
         */
        public static int binarySearch(int[] srcArray, int des){
    
            int low = 0; // 比较区间第1位
            int high = srcArray.length-1; // 比较区间最后1位
            int middle ; // 区间的中间位置
            
            
            while(low <= high) {
    
                // 1. 通过折半，求出区间的中间位置
                middle = low +  (high - low)>>1;
                 // 此处需特别注意以下：
               // a. mid = （low + high) / 2：当low、high都是比较大的数时，可能造成上溢除
               // b. 采用右移的位运算代替除2，提高效率
    
                // 2. 比较给定值和中间值
                    // 2.1 若给定值 = 中间记录，则查找成功，返回该位置
                if(des == srcArray[middle]) {
                    return middle;
    
                    // 2.2 若给定值 ＜ 中间记录，则 在中间记录的左半区 继续查找
                    // 即 将比较区间的最后1位 设置为 原中间位置的前1位
                }else if(des <srcArray[middle]) {
                    high = middle - 1;
    
                    // 2.3 若给定值 ＞ 中间记录，则 在中间记录的右半区 继续查找
                    // 即 将比较区间的首位 设置为原中间位置的后1位
                }else {
                    low = middle + 1;
                }
            }
            // 若比较区间的第1位 ≥ 最后1位，则表示查找失败，返回-1
            return -1;
        }
    
    
        /**
         * 执行 二分查找方法
         */
        public static void main(String[] args) {
    
            // 定义1个有序表数组
            int[] src = new int[]{1, 4, 5, 7, 8, 13,20,28};
            // 输出结果
            System.out.println("需要查找数据的数组下标 = " + binarySearch(src,8));
    
        }
        
    }

*  测试结果

需要查找数据的数组下标 = 4

*  二分查找的变式

对于二分查找存在一定的优 & 缺点，所以衍生出2种二分查找的变式方法：**插值查找 & 斐波那契查找**。具体如下：

> 区别主要在于：比较元素（中间元素）的计算

![对比][648628cedc120e4d0fa1f291af7e4914.png]

### 3.3 线性索引查找 ###

*  面向的数据结构：索引表

> 关于 索引 的介绍如下

![示意图][e5cf60873a3bc346a4206d7f0dcdbbfb.png]

*  本文主要介绍的线性索引查找算法 = **稠密索引、分块索引、倒排索引**。具体介绍如下：

![示意图][b4c6806083b2deee4752ad20b7d786e7.png]

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

# 4. 动态查找 #

*  定义：作 查找、插入 & 删除操作
 *  面向的数据结构：动态查找表
 *  算法：二叉排序树、平衡二叉排序树（`AVL`树）&多路查找树
 *  具体介绍如下

### 4.1 二叉排序树 ###

> 也称：二叉查找树、二叉搜索树

*  特点  
    ![示意图][caafdc2e8752cd08e4886c0bc9227064.png]
 *  作用 & 应用场景

![示意图][d9f857824d29cfc263ed9d9230339581.png]

### 4.2 平衡二叉排序树（AVL树） ###

> 属于 二叉搜索树的一种特殊类型

*  特点

![示意图][46935bc8fed6643e6edfacfdd6d7f33a.png]

*  具体介绍

![示意图][e59fe60f1fe5f18d1e86e3edefec370f.png]

### 4.3 多路查找树 ###

*  具体介绍如下  
    ![示意图][06d99edeaedb387c7b347db6a1514a1f.png]
 *  多路查找树的类型介绍 & 对比  
    http://blog.csdn.net/wtyvhreal/article/details/46442091

![示意图][c5e9e78684893fc81662b24b46fa0db4.png]

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

# 5. 散列查找 #

*  定义：通过关键字获取记录
 *  面向的数据结构：散列表
 *  算法：散列技术
 *  具体介绍如下

### 5.1 散列技术 ###

*  简介

![示意图][363c86b4f1bb98de0bbedceb7cb57f19.png]

### 5.2 散列函数的设计（构造方法） ###

*  简介  
    即，该如何构造出 散列函数  
    ![示意图][8fd708af8cd406c6751c4ab244301a56.png]
 *  具体构造方法介绍 & 对比

![示意图][62b50d093f33b0db9d731a6704b08b17.png]

### 5.3 散列冲突 ###

*  简介 & 解决方案

![示意图][2af3381da4b715a8b419fd86dac9d5fe.png]

*  解决方案介绍

![示意图][af4ee6af33708aa2dcea69b3707a02e2.png]

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

# 6. 总结 #

*  本文主要讲解了数据结构中的查找相关知识
 *  下面我将继续对 **数据结构**，有兴趣可以继续关注[Carson\_Ho的安卓开发笔记][Carson_Ho]

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

# 请帮顶 / 评论点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20221123/d176c27b4a8142aeb25fdf1337d92cb6.png
[b062f3be2ee6a15f842a779b48132264.png]: /images/20221123/6af89f99051d43c4b0e06239066cecd4.png
[6d14fdb0f157d80c8ca031c1dd2ea091.png]: /images/20221123/0a769ee09e61476eba198c8090bb1333.png
[eb5c0bd1123cab9692742daf31a2b0e3.png]: /images/20221123/c34e16c14e24467f8aa59cc8297e3196.png
[489922510db3a369bad726f4558f4d7a.png]: /images/20221123/c6a4e7c05d8b488ea650dbe22d546bd2.png
[f15fd0f5ad7913fc3afc97c58fc937fe.png]: /images/20221123/984169f2281b43e4a5b5651130ea57d7.png
[648628cedc120e4d0fa1f291af7e4914.png]: /images/20221123/d3ce94aa7cd14baa86bed27c2e9daa5a.png
[e5cf60873a3bc346a4206d7f0dcdbbfb.png]: /images/20221123/d0e9283049914b7cbb7c924596bd5c41.png
[b4c6806083b2deee4752ad20b7d786e7.png]: /images/20221123/63fe5db7748440b9b9578f08c1181305.png
[caafdc2e8752cd08e4886c0bc9227064.png]: /images/20221123/f1f624632a3244658ffc0c129e2656bd.png
[d9f857824d29cfc263ed9d9230339581.png]: /images/20221123/3daee3a875bf4549ad75a097bddec3ee.png
[46935bc8fed6643e6edfacfdd6d7f33a.png]: /images/20221123/ffafab19e68242eba12336d95b6527c8.png
[e59fe60f1fe5f18d1e86e3edefec370f.png]: /images/20221123/b337e622a3464367aed5ff55f3de539b.png
[06d99edeaedb387c7b347db6a1514a1f.png]: /images/20221123/3f950d4a964a4d81a3f1c8f621f416a1.png
[c5e9e78684893fc81662b24b46fa0db4.png]: /images/20221123/32a74645b80b4e5e800ca452cb80871f.png
[363c86b4f1bb98de0bbedceb7cb57f19.png]: /images/20221123/06664a2c6d694a6e9146476904ffc1c1.png
[8fd708af8cd406c6751c4ab244301a56.png]: /images/20221123/ed06ef0e066a41cb9106ff3f35f8f711.png
[62b50d093f33b0db9d731a6704b08b17.png]: /images/20221123/578339a0413f4dd88f08cc227d7d006a.png
[2af3381da4b715a8b419fd86dac9d5fe.png]: /images/20221123/b3129b2b943d49f3b6911d2970073f01.png
[af4ee6af33708aa2dcea69b3707a02e2.png]: /images/20221123/1cb4eeb3235c4d20be1e74ca31becefb.png
[Carson_Ho]: https://blog.csdn.net/carson_ho