数据结构实验：哈希表

Problem Description

在n个数中，找出出现次数最多那个数字，并且输出出现的次数。如果有多个结果，输出数字最小的那一个。

Input

单组数据，第一行数字n（1<=n<=100000)。
接下来有n个数字，每个数字不超过100000000

Output

出现次数最多的数字和次数。

Sample Input

3
1 1 2

Sample Output

1 2

Think

1.到这里我们首先想到的可能是桶排序，但是想想数据的最大值是：100000000
那这个方法自然就要放弃了
2.接下来我们要介绍的是哈希表，一种很有用的数据结构

哈希表

概念

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
---摘自百度百科

实际上就是一本字典，我们根据哈希函数，知道相应的key值，然后我们就去找到这个key对应的value

优点
哈希表关键在于在存储位置和key值之间建立了一种联系，我们根据key值来知道它的存储位置，这样很快就能拿到它的value

不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级.
对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

哈希函数

我们想想上次做的选课表的题，实际上有点像哈希表，我们根据课程的编号来找到相应课程的学生，只不过在那个哈希函数简单，就是H(key)=key,所以要知道的是，哈希函数只不过是key到存储地址的一个映射而已，至于你要怎么选择这个函数，可以根据不同的情况来选择，在这道题这里，我们采用的是除留余数法

课程编号	学生	数量
01	Kevis ,Julia	5
02	Tom...	2
03	Jack ...	3
...	...	...

冲突

当选用不同的哈希函数时，很可能会发生一些冲突，比如我前面说的除留余数法，假设数据的个数是10个，范围是0~5，我们定义的取余数就是 H(key)=key%num，(num是指数据的个数)
那么1和6就冲突了

冲突解决

我们要怎么去解决冲突呢？也有很多方法，但是这里我只介绍拉链法
拉链发，顾名思义，假如两个数在一个地址，我们就用链表的方式存储他们，比如前面的选课，我们根据学生的名字来做一个字典大小比较

拉链法
图片来源

好了，哈希表的介绍就到这里，我们来看看这题怎么做
题破：

#include<stdio.h> 
#include<stdlib.h>
struct hash{
    int num;
    int time;
    struct hash *next;
}* a[100101];

int main() {
    int n;
    int max=0,num=0;
    int data;
    struct hash *p1,*p2,*ins;
    scanf("%d",&n);
    //初始化
    for(int i=0;i<100000;i++){  //永远不要忘记指针的初始化
        a[i]=(struct hash *)malloc(sizeof(struct hash));        
        a[i]->next=NULL;
        
    }
    for(int i=0;i<n;i++){
        scanf("%d",&data);
        int y=data%100000; //哈希函数 H(key)=key/100000
        p1=a[y];
        p2=p1->next;
        while(p1->next!=NULL){
            if(p2->num==data){
                p2->time++;
                if(max<p2->time){
                    max=p2->time; 
                    num=p2->num;
                }//if
                else if(max==p2->time){
                    if(num>p2->num) 
                        num=p2->num;
                }                   
            break;
            }//if
            p1=p1->next;
            p2=p2->next;
        }
        //因为有一个break语句，跳出循环时就有两种情况了
        if(p1->next==NULL) {        
        ins=(struct hash *)malloc(sizeof(struct hash));
        ins->next=NULL;
        ins->num=data;
        ins->time=1;
        if(max<ins->time){
            max++;
            num=ins->num;           
        }
        else if(max==ins->time){
            if(num>ins->num)
                num=ins->num;
        }//上面两个语句来得到最大出现次数以及此条件下最小数
        p1->next=ins;
        ins->next=p2;
    }//if
    }
    printf("%d %d\n",num,max);
}


/***************************************************
User name: lin99
Result: Accepted
Take time: 48ms
Take Memory: 7184KB
Submit time: 2018-09-17 11:52:47
****************************************************/

ok,就这么简单，我们根据time在某个数组元素下构建有序列表，还有使用max和num来记录出现次数最大值和数值最小值，不得说这种思路是真的重要。像什么找最值等等，都能用到这种思想。

我们再来简单回顾一下这里哈希表的作用，实际上我私自认为这个地方发哈希表做到的就是压缩数据，这里并没有体现出哈希表查找的优点，我们仅仅只是根据哈希表的哈希函数来将数组的范围减小了很多，空间也减少了很多,但是不得不说哈希表真的是特别塞雷。