由入门题回想起来的哈希表

洛谷P2550

P2550 [AHOI2001]彩票摇奖 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

可以看到这是个入门题，完全可以用暴力查找（for循环二重嵌套）来实现，但是这个查找形式让我想起了一个月之前学的哈希表（HashMap）

众所周知，利用哈希表可以将查找的时间复杂度优化到O(1)的水平，而且本题需要存储的对照数据只需要六个，所以哈希表的实现是非常简单的

但是，我TM已经忘干净了，于是紧急复习了一下

众所周知，哈希表是利用键值对来实现对元素的快速查找的，每一个值（元素）都对应着唯一的一个键（key），所以构建哈希表的关键就是对于给定的值，如何构建其唯一对应的键来存储以及查找它。

我们通常自己构造一个哈希函数来实现值对键的计算，一个较为简单的方法就是

1 int Get_Key(int n,int TableSize)
2 {
3          return n%TableSzie;//这里的表长一般取大于存储数据个数的一个质数
4 }

也就是值对哈希表的长度取模作为键值。但是显然，会出现多个元素对应一个键值的冲突，为了避免这种冲突，有一种叫做开放定址法的方法，也就是把冲突的元素重新在表中找一个位置填入

对于开放定址法，分为线性探测法和平方探测法，其中线性探测法实现简单但是会造成平均查找次数增多，元素会越来越集中的弊端，不过实现简单，这里我只举出线性探测法的例子

所谓线性探测，就是说当我们发现一个元素的键已经有数据存储的时候，我们便将这个元素加i在进行取模，得到相对的键值（说到这里，其实平方探测法就是将元素加上+-i的平方再进行取模罢了）,方便起见，一次冲突就加上i=1，两次冲突就加上i=2，以此类推直到找到没有被占用的键值

代码实现如下

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF -1;
 4 int Get_Key(int n,int TableSize)
 5 {
 6     return n%TableSize;
 7 }//哈希函数定义 
 8 int main()
 9 {
10     int N;
11     scanf("%d",&N);//要存入的数据 
12     int TableSize=7;//哈希表长 
13     int HashMap[TableSize];
14     memset(HashMap,-1,sizeof(HashMap));//定义-1为未定义也就是为占用标志 
15     int Key=Get_Key(N,TableSize);//获取初始键值 
16     for(int i=1;;i++)
17     {
18         if(HashMap[Key]=INF)//如果该键值未被占用，则填入元素，退出循环 
19         {
20         HashMap[Key]=N;
21         break;
22         } 
23         else//被占用了就继续加1向后一个坐标来探测 
24         Key=Get_Key(N+i,TableSize);
25     }
26     return 0;
27  } 

好了，至此我们就可以简单的解决入门题P2550辣