笔试+查找算法

3.分析分块查找？

1.分块查找的复杂度？

xx

xx

33

4.对分块查找的认识/理解？

七、哈希查找

1.解决什么问题？

2.怎么解决这个问题？

1.基本的思想？

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

2.规则？

3.流程？

1）用给定的哈希函数构造哈希表；

4.代码？

#include "stdio.h"
#include "stdlib.h"#define HASHSIZE 7 // 定义散列表长为数组的长度
#define NULLKEY -32768typedef int Status;
typedef struct{int *elem; // 数据元素存储地址，动态分配数组int count; //  当前数据元素个数
}HashTable;// 散列表表长，全局变量
int m = 0;void InitHashTable(HashTable *hashTable);
Status Hash(int key);
void Insert(HashTable *hashTable,int key);
Status Search(HashTable *hashTable,int key);
void DisplayHashTable(HashTable *hashTable);int main(int argc, const char * argv[]) {int result;HashTable hashTable;int arr[HASHSIZE] = {13,29,27,28,26,30,38};//初始化哈希表InitHashTable(&hashTable);/***  向哈希表中插入数据;也就是把元素使用哈希函数映射到哈希表中；*/for (int i = 0;i < HASHSIZE;i++){Insert(&hashTable,arr[i]);}//数据已存到哈希表中，打印观察哈希表，元素的位置和原数组是完全不一样的DisplayHashTable(&hashTable);//查找数据result = Search(&hashTable,30);if (result == -1){printf("没有找到！");}else{printf("在哈希表中的位置是:%d\n",result);}return 0;
}//初始化一个空的哈希表
void InitHashTable(HashTable *hashTable){m = HASHSIZE;hashTable->elem = (int *)malloc(m * sizeof(int)); //申请内存hashTable->count = m;for(int i = 0;i < m;i++){hashTable->elem[i] = NULLKEY;}
}//哈希函数(除留余数法)
Status Hash(int key){return key % m;
}//插入
void Insert(HashTable *hashTable,int key){/***  根据每一个关键字，计算哈希地址hashAddress；*/int hashAddress = Hash(key); //求哈希地址/***  发生冲突，表示该位置已经存有数据*/while(hashTable->elem[hashAddress] != NULLKEY){//利用开放定址的线性探测法解决冲突hashAddress = (hashAddress + 1) % m;}//插入值hashTable->elem[hashAddress] = key;
}//查找
Status Search(HashTable *hashTable,int key){//求哈希地址int hashAddress = Hash(key);//发生冲突while(hashTable->elem[hashAddress] != key){//利用开放定址的线性探测法解决冲突hashAddress = (hashAddress + 1) % m;if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(key)){return -1;}}//查找成功return hashAddress;
}//打印结果
void DisplayHashTable(HashTable *hashTable){for (int i = 0;i < hashTable->count;i++){printf("%d ",hashTable->elem[i]);}printf("\n");
}

3.分析哈希查找算法？

1.哈希查找算法的复杂度？

单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

2.哈希查找算法的特点？

3.哈希查找算法的优点？

4.哈希查找算法的缺点？

4.需要展开讲解的知识点？

1.哈希查找算法的哈希函数的选择？六种哈希函数的构造方法：

（1）直接定址法

函数公式：f(key) = a * key + b（a,b为常数）

这种方法的优点是：简单、均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。

（2）数字分析法

也就是取出关键字中的若干位组成哈希地址。比如我们的11位手机号是“187****1234”，其中前三位是接入号，一般对应不同的电信公司。中间四位表示归属地。最后四位才表示真正的用户号。

如果现在要存储某个部门的员工的手机号，使用手机号码作为关键字，那么很有可能前面7位都是相同的，所以我们选择后面的四位作为哈希地址就不错。

（3）平方取中法

取关键字平方后的中间几位作为哈希地址。由于一个数的平方的中间几位与这个数的每一位都有关，所以平方取中法产生冲突的机会相对较小。平方取中法所取的位数由表长决定。

如：K=456，K^2=207936,如果哈希表的长度为100，则可以取79（中间两位）作为哈希函数值。

（4）折叠法

折叠法是将关键字从左到右分割成位数相等的几个部分（最后一部分位数不够可以短），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。当关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以使用折叠法。

如：我们的关键字是9876543210，哈希表表长三位，我们可以分为四组：987 | 654 | 321 | 0，然后将他们叠加求和：987+654+321+0 = 1962,再取后三位就可以得到哈希地址为962.

（5）除留余数法

选择一个适当的正整数p（p<=表长），用关键字除以p，所得的余数可以作为哈希地址。即：H(key) = key % p(p<=表长)，除留余数法的关键是选取适当的p，一般选p为小于或等于哈希表的长度(m)的某个素数。

如：m = 8,p=7.

m = 16,p = 13.

m = 32,p = 31.

（6）随机数法

函数公式：f(key) = random(key). 这里的random是随机函数，当关键字的长度不等时，采用这种方式比较合适。

总之，哈希函数的规则就是：通过某种转换关系，使关键字适度的分散到指定大小的顺序结构中。越分散，查找的时间复杂度就越小， 空间复杂度就越高。哈希查找明显是一种以空间换时间的算法。

2.如何解决冲突问题？提到了如何构造一个哈希函数，那就不得不提如何避免冲突的算法。

（1）开放定址法

当冲突发生时，使用某种方法在哈希表中形成一探查序列。然后沿着该探查序列逐个单位的查找，直到找到一个开放的地址（即该地址单元为空）为止。对于哈希表中形成一探查序列时，可以有3种不同的方法：

1.线性探测法

将散列看成一个环形表，探测序列是（假设表长为m）：

H(k),H(k)+1,H(k)+2.....m-1,0,1......H(k)-1。用线性探测法解决冲突时，求下一个开放地址的公式为：Hi = (H(k)+i) MOD m.

2.二次探测法

二次探测法的探测序列依次是12，-12，22，-22等等。当发生冲突时，求下一个开放地址的公式为：

H2i-1=(H(k)+i2)MODm

H2i=(H(k)-i2)MODm(1=优点：减少了堆集发生的可能性；

缺点：不容易探测到哈希表空间。

3.伪随机探测法

采用随机探测法解决冲突时，下一个开放地址的公式为：Hi=(H(k)+Ri)MODm。

其中R1,R2,...,Rm-1是一个随机排列。

（2）再哈希法

当冲突发生时，使用另一个函数计算得到一个新的哈希地址，直到冲突不再发生时为止。Hi=RHi(key)i=1,2,…,k 。其中RHi均是不同的哈希函数。优点是不易产生聚集，缺点是增加了计算时间。

（3）链地址法

将所有关键字为同义词的结点链接在同一个单链表中。若选定的哈希函数所产生的哈希地址为0~m-1,则可以将哈希表定义成一个由m个链表头指针组成的指针数组。优点是：不产生聚集；由于结点空间是动态申请的，故更适合造表前无法确定表长的情况；从表中删除节点容易。

（4）公共溢出区法

假设哈希函数的值域为[0...m-1]，则设向量HashTable[0...m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都被填入溢出表中。

在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为k，根据建表时设定的哈希函数H，计算出哈希地址H(k),若表中该地址对应的空间未被占用。则查找失败。否则将该地址中的节点与给定值k比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。

5.对哈希查找算法的认识/理解？

1.使用Hash，我们付出了什么？

　　我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？

　　Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。

哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

八、其他补充的知识点

1.什么是查找？

#定义：查找是指给定某个值，在查找表中确定一个关键字等于给定值的数据元素（或记录）。

#其他描述（解释和理解）：

（1）查找是在大量的信息中寻找一个特定的信息元素。

（2）查找是常用的基本运算。

2.查找算法的分类？

=>第一种分类：静态查找和动态查找。（针对对查找表的操作而言的）

（1）静态查找：

（2）动态查找：

#总结：

#对静态查找和动态查找的认识（理解）：

(1）静态查找和动态查找都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

=>第二种分类:无序查找和有序查找（针对查找的对象的有序或无序）

（1）无序查找：被查找的数列可以是有序也可以是无序。

（2）有序查找：被查找的数列必须为有序数列。

3.什么是平均查找长度（Average Search Length,ASL）？

=>定义：需要和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

=>公式：。

公式整体的意义：ASL表示的是对于含有n个数据元素的查找表，查找成功的平均查找长度。

每个分量的意义：

Pi:查找表中第i个数据元素的概率。

Ci:找到第i个数据元素时已经比较过的次数。

=>理解：

（1）

九、各大查找算法的实际应用

哈希算法：http://touch-2011.iteye.com/blog/1090305

===============================================================

参考资料：

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.cnblogs.com/QG-whz/p/4536875.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！