编程学习笔记10--哈希表

[导读]导引问题 Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。 Input 每组测试数据有两行，第一行有两个数n,m (0

导引问题 Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。 Input 每组测试数据有两行，第一行有两个数n,m (0 题目特点： n数据量大 n数据在一定范围
思考：常规算法的缺陷？常规算法需要先对输入的值进行存储，然后进行排序，最后再进行输出前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;
}