基本概念

查找表（Lookup table）是一种数据结构，用于在给定输入值的情况下，快速查找相应的输出值。它是一种将输入值映射到输出值的表格或数据结构。

查找表通常是一个键值对的集合，其中键是输入值，而值是对应的输出值。当需要查找某个输入值时，可以通过直接访问查找表中的对应键，以获取相应的输出值。这种查找过程是非常快速的，因为它不需要进行线性搜索或计算。

关键字(键) – 用来标识数据元素的数据项称为关键字，简称键；其值称为键值。

主关键字 – 可唯一标识各个数据元素的关键字。 查找 – 根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。 静态查找表 – 进行的是引用型运算 动态查找表 – 进行的是加工型运算。

1.顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：　

查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

顺序查找的优缺点：

• 优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。
• 缺点：平均查找长度较大，查找效率低，所以当n很大时，不宜用顺序查找。

图解：

2.折半查找

前提： 有序的顺序表。【需要具有随机访问的特性，链表没有】

基本思想：

搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜 素过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组 为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logN) 。

图解：

3.分块查找

分块查找又称索引顺序查找。

基本思想：

• 索引表中记录每个分块的最大关键字、分块的区间
• 先查索引表（顺序或折半)、再对分块内进行顺序查找

查找过程：

1. 先建立最大（或小）关键字表 – 索引表（有序） 即将每块中最大（或最小）关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表；
2. 查找索引表，以确定所查元素所在块号； 将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号；
3. 在相应块中按顺序查找关键字为k的记录。

图解：

4.二叉排序树

二叉排序树(也称二叉查找树（Binary Sreach Tree）,简称BST)或者是一棵空树，或者是具有下列特性的二叉树:

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树。

性质： 中序遍历一颗二叉排序树所得的结点访问序列是键值的递增序列。

根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

过程：

当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功；否则根据给定值与根结点关键字间的大小关系，分别在左子树或右子树上继续进行查找。

图解：

5.二叉平衡树AVL

概念

平衡二叉树（AVL树）本身也是一种二叉排序树，其内部的元素之间同样遵从左孩子 < 根节点 <右孩子或者左孩子 > 根节点 > 右孩子的特性的。但是，在创建平衡二叉树的时候，我们要求树结构中的任何一个节点，左右子树的层数深度之间的深度之差，绝对值不超过1。

举个例子：如果在某一个二叉树结构中，某一个节点的左子树的深度是5，则其右子树的深度取值范围在4­-6之间，如果超出或者小于这个范围，就不算是平衡二叉树了。

那么在向这个二叉树结构中插入新节点，或者删除原有节点的时候，很可能出现导致某节点左右子树不平衡的状况发生，那么此时就需要对指定的节点进行旋转，最终达到让这个节点，乃至整个二叉树结构平衡的目的。

如何判断：

可通过计算非叶子结点的平衡因子来判断该树是否为平衡二叉树（叶子节点的平衡因子均为0）。

平衡因子 = 左子树深度 - 右子树深度

失衡的四种情况及基本操作

对于整棵树而言调整平衡的方法可能不唯一，即使是同一种类型都可能存在多种调整平衡的方法。

一棵平衡二叉树是因为新插入结点而导致不平衡的，所以我们只需要对最小失衡子树进行平衡调整，整棵树也会跟着平衡（插入结点导致高度改变，平衡调整是使得高度复原），所以并不需要整棵树进行调整。因为如果一个树很大，调整方法很多，就很繁琐，也很容易乱。

最小失衡子树：在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树。

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。根据旋转的方向有两种处理方式，左旋 与 右旋 。

旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转。

算法图解：

AVL

LL型

LR型

RR型

RL型

6.B树

概念

B-树是一种平衡的多路查找树，注意： B树就是B-树，"-"是个连字符号，不是减号 。

B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。

定义

B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：

• 每个节点最多只有m个子节点。
• 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
• 如果根不是叶节点，则根至少有两个子节点。
• 具有k个子节点的非叶节点包含k -1个键。
• 所有叶子都出现在同一水平，没有任何信息（高度一致）。

7.B+树

B+树是应文件系统所需而产生的B树的变形树，那么可能一定会想到，既然有了B树，又出一个B+树，那B+树必然是有很多优点的

B+树的特征：

• 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；

8.散列表(哈希表)

概念

散列表，也叫哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。

静态查找表以及动态查找表中的一些查找方法，其查找的过程都无法避免同查找表中的数据进行比较，查找算法的效率很大程度取决于同表中数据的查找次数。

哈希表可以通过关键字直接找到数据的存储位置，不需要进行任何的比较，其查找的效率相较于前面所介绍的查找算法是更高的。

散列查找法的两项基本工作：    

■ 计算位置：构造散列函数确定关键词存储位置；    

■ 解决冲突：应用某种策略解决多个关键词位置相同的问题。

时间复杂度几乎是常量：O(1) ，即查找时间与问题规模无关!

哈希表的建立同函数类似，把函数中的 x 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。即：

数据的哈希地址=f（关键字的值）

哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。

f(key)是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。

例：

有n= 11个数据对象的集合{18，23，11，20，2，7，27，30,42，15，34}。符号表的大小用TableSize = 17，选取散列函数h如下：h(key) = key mod TableSize(求余)

存放： h(18)=1，h(23)=6，h(11)=11，h(20)=3，h(2)=2,…如果新插入35，h(35)=1，该位置已有对象！冲突！！

查找： key = 22，h(22)=5，该地址空，不在表中。       key = 30，h(30)=13，该地址存放是30，找到！

装填因子（Loading Factor)：设散列表空间大小为m，填入表中元素个数是n，则称α=n/m为散列表的装填因子。   此例中，α=11/17=0.65。

构建哈希表

在构建哈希表时，最重要的是哈希函数的设计。

常用的哈希函数的构造方法有 6 种：

• 直接定址法

• 数字分析法
  如果关键字是位数较多的数字（比如手机号），且这些数字部分存在相同规律
  则可以采用抽取剩余不同规律部分作为散列地址
• 平方取中法
  即取关键字平方的中间位数作为散列地址
• 折叠法
  折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些）
  然后将这几部分叠加求和
  并按散列表表长，取后几位作为散列地址
  比如假设关键字是 9876543210，散列表表长为三位
  则我们可以将它分为四组 987|654|321|0
  然后将它们叠加求和 987+654+321+0=1962
  再取后 3 位得到散列地址即为 962
• 除留余数法
  此方法为最常用的构造散列函数方法
  对于散列表长为的散列函数公式为：

很显然，本方法的关键就在于选择合适的P。

• 随机数法选择一个随机数取关键字的随机函数值为它的散列地址：

当关键字的长度不等时采用这个方法构造散列函数是比较合适的

• 基数转换法
  基数转换法：例如将十进制的键值，先把他看作13进制的数，并转换为10进制；然后从计算结果中根据散列表的长度选取其中几位作为散列地址。

冲突处理：

冲突即：不同的关键字映射到同一存储单元。

解决冲突主要有两种方式，一种是链地址法，另一种为开放地址法。

用『链地址法』处理冲突

思想 ： 将散列地址相同记录存储在同一单链表中（称同义词表），同时按散列地址设立一个表头指针向量。

例如，若选定的散列函数为H(key) = key mod 13,已存入键值为26、41、25、05、07、15、12、49、51、31、62的散列表。

用『开放地址法』处理冲突

如果该位置已经有元素了，则换一个地方，当然为了查找时还能找得到他，肯定是不可以随便放的，需要按照指定的增长序列{k_1,k_2,k_3,k_4...k_n}，依次探查离自己距离自己{k_1,k_2,k_3,k_4...k_n}的地方是否有空。

增量序列的不同，提供了不同的解决冲突方法；常用的方法有四种，分别为：

• 线性探测
• 平方探测（二次探测）
• 双散列（多重散列）
• 公共区溢出

使用线性探测时，如果出现冲突那就向后错一位，看是否有空，直到找到空的；

使用二次探测时，每次向前向后di的平方2位。使用这2种方法容易会造成聚集。聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。

二次探测法的基本思想：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少堆积。按照二次探测法，键值key的散列地址序列为d0=H(key);

di = (d0 + i) mod m；

其中，m 为散列表的表长， i = 1^2, -1^2, 2^3,…,± k^2(k <= m / 2)。

分析:当发生冲突时，应用二次探测法，得到下一个地址d1 = (3 + 1^2) mod 13 = 4仍冲突，则再求下一个地址d2 = (3 - 1^2) mod 13 = 2仍冲突，直到散列地址为d3 = (3 + 2^2) mod 13 = 7时其位置上没有元素，即元素填入散列表中序号为7的位置。

对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。总体来说使用平方探测要比使用线性探测出现聚集的概率小。

使用双散列时，如果出现冲突，就用当前的键值作为参数用另一个散列函数计算键值，直到找到空位。

此法要求设立多个散列函数Hi， i = 1， …, k。当给定值 key 与散列表中的某个键值是相对于某个散列函数式的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数H_(i+1)下的散列地址，直到不再产生冲突为止。这种方法的优点是不易产生 『堆积』 ，缺点是计算量较大。

用『公共溢出区法』处理冲突

按这种方法，散列表由俩个一维数组组成。一个称为基本表，它实际上就是上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表。这样，基本表不可能发生『堆积』。

散列表的优缺点：

• 优点：它回避了关键字之间反复比较的繁琐，直接一步到位查找结果。
• 缺点：记录之间没有任何关联。

9.KMP算法

• KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。
• Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。
• KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。

本人能力有限，文中内容难免有纰漏，真诚欢迎大家斧正~

喜欢本文的朋友请三连哦！！！

另外本文也参考了网络上其他优秀博主的观点和实例，这里虽不能一一列举但内心属实感谢无私分享知识的每一位原创作者。