2022-07-17 23:35 北京科技大学 Java

关注

19-数据结构和算法-03-查找

数据结构和算法（Data Structure And Algorithms）

查询

一是数据如何组织-查找表
二是在查找表上如何查找-查找方法

基本概念

查找表是由同类型的数据元素（或记录）构成的集合

查找表的基本操作

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

查找表分类

静态查找表：仅作查询和检索操作的查找表
动态查找表：
- 查询结果"不在查找表中"-->数据元素插入到查找表中；
- 查询结果为"在查找表中"的数据元素-->删除

关键字

在查找过程中，往往是依据数据元素的某个数据项进行查找，这个数据项通常是数据的关键字。

关键字：就是数据元素中某个数据项的值，用以标识一个数据元素。

如果关键字能标识唯一的一个数据元素，则称为主关键字
如果关键字能标识若干个数据元素，则称为次关键字

平均查找长度ASL（有点海贼王的意思的了）

alt

查找算法

顺序查找
二分查找
索引查找
哈希查找

顺序查找

基本思想

从表中指定位置（一般为最后一个，第0个位置设为岗哨）的记录开始，沿某个方向将记录的关键字与给定值比较，若某个记录的关键字和给定值相等，则查找成功；
反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。

查找算法

alt

性能分析

空间复杂度：O(1)
时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较
- 最好情况：O(1)
- 最坏情况：O(n)
- 平均情况：O(n/2)=O(n)

平均查找长度

平均查找长度（ASL）：给定值与关键字比较次数的期望值。对于具有n个记录的顺序表，查找成功时的平均长度为：

alt

等概率情况

alt

不等概率

每个元素的查找概率已知--->查找概率大的放前面，查找概率小的放后面，可以使得ASL最小
每个元素的查找概率未知--->将查找过得元素放到线性表的尾部。

折半查找

有序表：若果顺序表中的记录按关键字值有序，则称顺序表为有序表。

查找过程

将待查关键字与有序表表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则可能在有序表的后半部分，因此经过一次比较，就将查找范围缩小一半，这样一直进行下去直到找到所需记录或记录不再查找表中。

alt

代码实现

alt

性能分析

alt

特点

折半查找查找效率高
平均查找性能和最坏性能相当接近
折半查找要求查找表为***==顺序存储结构的有序表==***

索引查找

索引使用方法

先分析数据规律，建立索引
再根据索引进行快速定位
在定位的地方进行细致搜索

索引表的构建

alt

索引表的查找

索引表的查找（索引表有序）
查找表的查找

alt

索引表的顺序查找算法思想

alt

算法实现

alt

m表示索引块的数量，Link表示查找表中的位置

索引顺序查找的ASL

ASL = ASL（索引表）+ ASL（块内），以下只考虑两个都是顺序查找

alt

==其实也就是 1/2 * (b+s) +1==

三种查找算法的比较

	顺序查找	二分查找	索引查找
ASL	大	小	中
表结构要求	无	有序表	分块有序

哈希查找

场景：学生学号 xx000-xx999，查找学号17128

alt

取给定学号的后三位，不需要经过比较，便可直接从查找表中找到给定学生的记录。

alt

哈希函数

一般情况下，需要在关键字与记录在表中的存储位置之间建立一个函数关系，以h(key)作为关键字为key的记录在表中的位置，通常称这个函数h(key)为哈希函数。

alt

哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置灵活，只要这个地址集合的大小不超出允许范围即可；
由于哈希函数是一个压缩映象，因此，在一般情况下，很容易差生“冲突现象”，==即key1 != key2，而h(key1) = h(key2)==
很难找到一个不产生冲突的哈希函数，一般情况只能选择恰当的哈希函数，使冲突尽可能少的产生
所以说，哈希查找需要做两方面的事情：
- 选择一个较好的哈希函数
- 提供一种处理冲突的方法

一般来说，好的哈希函数具备两个条件：

计算简单
冲突少

哈希表

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

alt

常见的哈希函数

常见的哈希函数构造方法

直接哈希函数
数字分析法
平方取中法
折叠法
除留余数法
随机数法

直接哈希函数

取关键字本身或者关键字的某个线性函数值作为哈希地址
比如h(key)=key 或者 H(key) = a*key+b (a、b为常数)

alt

数字分析法

设n个d位数的关键字，有r个不同的符号组成，此r个符号在关键字各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近n/r，而在另一些位上分布不均匀。则选择其中分布均匀的s位作为哈希地址，即H(key)="key中数字均匀分布的s位"。

alt

平方取中法

取关键字平方后的中间几位作为哈希地址，即哈希函数为

H(key) = “key平方的中间几位”，其中所取的位数由哈希表的大小确定。

alt

思想：

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是***==扩大差别==和==贡献平均==***。

即关键字的各位都在平方值的中间几位有所贡献，哈希值中应该有各位影子。

折叠法

关键字位数较长时，可将关键字分割成位数相等的几部分（最后一部分可以不相同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。叠加时有两种方法：
- 移位叠加法，即将每部分的最后一位对齐，然后相加
- 边界叠加法，即把关键字看作一纸条，从一端向另一端沿边界逐次折叠，然后对齐相加。

alt

除留余数法

取关键字被某个不大于哈希表长度m的数p除后的余数作为哈希地址，即

H(key) = key % p （p<m）

alt

随机数法

选择一个随机函数，取关键字的随机函数值作为哈希地址

H(key) = random(key)，其中key相同时，哈希值是相同的，即可复现

实际工作中需根据不同的情况采用不同的哈希函数。通常需要考虑的因素有：

计算哈希函数所需要的时间
关键字的长度
哈希表的大小
关键字的分布情况
记录的查找频率

字符串的哈希查找

alt

27的话计算量比较大，可以改成32，用位运算做

alt

冲突：是指由关键字得到的hash地址上已有其他记录。

好的哈希函数可以减少冲突，但是很难避免冲突。

冲突处理：为出现哈希地址冲突的关键字寻找下一个哈希地址。

冲突处理

开放地址法
再哈希法
链地址法
公共溢出区法

开放地址法

为产生冲突的地址H(key)求得一个地址序列：

alt

根据增量序列d，又可以细分

alt

alt alt

注意：==存储数据超过表长一半时，冲突次数大量增加！只要有空间，线性探测总能找到空间存放数据，但是二次探测不一定能够找到空间存放数据。==

要保证二次探测再散列始终能够找到空间存放：

二次探测再散列采用：1^2, -1^2, 2^2, -2^2 ,.......
可用空间至少有表长一半

alt

再哈希法

将n个不同哈希函数排成一个序列，当发生冲突时，有RHi确定第i次冲突的地址Hi，即

alt

这种方法不会产生聚类，但会增加计算时间。

链地址法

将所有哈希地址相同的记录都链接在同一链表中。

alt

公共溢出区法

alt

哈希表查找

在哈希表上查找的过程和哈希查找表的构造过程基本一致

给定k值，根据构造表时所用的哈希函数求哈希地址j；
若此位置无记录，则查找不成功；
- 否则，比较关键字，若和给定的关键字相等则成功；
  - 否则，根据构造表时设定的冲突处理的方法计算“下一地址”，重复2

/*哈希表查找算法*/
Status SearchHash(HashTable H, KeyType key, int &p, int &c){
/* 在开放地址哈希表H中查找关键字为key的数据 */
/* 用c记录发生冲突的次数，初始值为0 */
p=Hash(key);/*求哈希地址*/
while(H.data[p].key != NULL && H.data[p].key != key)
    /*该位置填有数据且与所查关键字不同*/
    collision(p,c++);/*求下一探查地址*/
if(H.data[p].key == key)
    return SUCCESS/*查找成功，p返回待查数据元素位置*/
else return UNSUCCESS;  /*查找不成功，p返回插入位置*/
}

alt