编程学习笔记10--哈希表
时间：2019-07-09 14:17:01
手机看文章
扫描二维码
随时随地手机看文章
[导读]导引问题
Problem Description
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m (0
导引问题
Problem Description
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m (0
思考： 常规算法的缺陷？ 常规算法需要先对输入的值进行存储，然后进行排序，最后再进行输出前m个数，n的数值很大是，对整体排序的时间会很长。
是否可以将“数据值”和“存储位置”做某种对应？ 因为数据的范围有限制的，数据量的多少也是有限制的，所以必然可以想办法让大的数据对应大的存储位置，小的数据对应小的存储位置。--优点，存储完毕，排序完毕，省去了排序的时间，缺点，对应关系找的不好的话，对空间的要求估计会比原来大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。
函数构造 最常见的方法：除余法 H(k ) = k mod p (p一般选取适当大的素数)
冲突 由于不能够保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况：“对于不同的元素关键字，Hash函数计算出了相同的函数值”，这就是产生了所谓的“冲突”。换句话说，就是Hash函数把不同的元素分在了相同的下标单元。 冲突解决 常用方法：线性探测再散列技术 即：当 h(k)位置已经存储有元素的时候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中， S为数组长度。 特别地，如果将数组扫描一圈仍未发现空单元，则说明哈希表已满，这会带来麻烦，但是，该情况完全可以通过扩大数组范围来避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函数运算 插入元素（包含冲突解决） 定位（需考虑可能冲突的情况） 优缺点总结 Hash函数评价标准： 低冲突率 易于编码 Hash函数特点： 优点：数据存储和查找效率高 （几乎是常数时间） 缺点：消耗较多内存（内存很便宜哪～） Hash主要应用： 查找元素是否属于集合 搜索中的状态表示
Hash的应用 n给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。 n Input n输入可能包含多组数据，其中每组数据包括两行： n第一行两个数N和M， n第二行N个数，表示该序列。 n nOutput n对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。
思考： 常规算法的缺陷？ 常规算法需要先对输入的值进行存储，然后进行排序，最后再进行输出前m个数，n的数值很大是，对整体排序的时间会很长。
是否可以将“数据值”和“存储位置”做某种对应？ 因为数据的范围有限制的，数据量的多少也是有限制的，所以必然可以想办法让大的数据对应大的存储位置，小的数据对应小的存储位置。--优点，存储完毕，排序完毕，省去了排序的时间，缺点，对应关系找的不好的话，对空间的要求估计会比原来大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。
函数构造 最常见的方法：除余法 H(k ) = k mod p (p一般选取适当大的素数)
冲突 由于不能够保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况：“对于不同的元素关键字，Hash函数计算出了相同的函数值”，这就是产生了所谓的“冲突”。换句话说，就是Hash函数把不同的元素分在了相同的下标单元。 冲突解决 常用方法：线性探测再散列技术 即：当 h(k)位置已经存储有元素的时候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中， S为数组长度。 特别地，如果将数组扫描一圈仍未发现空单元，则说明哈希表已满，这会带来麻烦，但是，该情况完全可以通过扩大数组范围来避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函数运算 插入元素（包含冲突解决） 定位（需考虑可能冲突的情况） 优缺点总结 Hash函数评价标准： 低冲突率 易于编码 Hash函数特点： 优点：数据存储和查找效率高 （几乎是常数时间） 缺点：消耗较多内存（内存很便宜哪～） Hash主要应用： 查找元素是否属于集合 搜索中的状态表示
Hash的应用 n给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。 n Input n输入可能包含多组数据，其中每组数据包括两行： n第一行两个数N和M， n第二行N个数，表示该序列。 n nOutput n对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。
#include
#define MAX1 3000*2999/2+10//N最大取3000，最多有3000*2999/2个数,扩大了5倍
#define MAX2 3000
int mask[MAX1]={0};
/**因为处理不好哈希冲突，经常出现小的数被存储在大的数据后面，和原来的大的存在高地址，小数
存储在低地址相违背了。因为原来的规则是存在k%MAX1的位置，如果位置有的话，就继续向后找，但是很可能出现后面
已经存储了比较大的数，所以处理不好，即使把k和k+1的间隔扩大几倍也很可能出现。就是k存储在k*10%MAX位置，
也有可能出错，所以设置了掩码位，计算相同的数个数*/
int h1[MAX1]={0};
int h2[MAX2]={0};//存储用的
int main()
{
int M,N,count=0;
int i,j,k,t,s=0;
while(scanf("%d %d",&N,&M)!=EOF)
{
memset(h1,0,MAX1);
memset(h2,0,MAX2);
memset(mask,0,MAX1);
for(i=0;i=0;t--)
{
while(mask[t])
{
mask[t]--;
printf("%d ",h1[t]);
count++;
}
if(count==M)
{
printf("n");
break;
}
}
}
return 0;
} 
下载文档
