哈希算法实例详解

1. 什么是哈希

Hash，一般翻译做散列、杂凑，或音译为哈希，是一个典型的利用空间换取时间的算法，把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

如有一个学生信息表：学生的学号为：年纪+学院号+班级号+顺序排序号【如：19(年纪)+002(2号学院)+01(一班)+17(17号)---à190020117】类似于一个这样的信息，当我们需要找到这个学号为【190020117】的学生，在不适用哈希的时候，我们通常是使用一个顺序遍历的方式在数据中进行查询大类，再查询子类得到，这样的作法很明显不够快 ，需要O(n)左右的时间花费，对于大型的数据规模而言这显然不行，而哈希的做法是，根据一定的规律(比如说年纪不存在过老和过小的情况，以此将【190020117】进行压缩成一个简短的数据如：【192117】)并且将这个数据直接作用于内存的地址，届时我们查询【190020117】只需要进行一次压缩并访问【192117】这个地址即可，而这个压缩的方法（函数），就可以称之为哈希函数。

一般的对于哈希函数需要考虑如下内容:

a) 计算散列地址所需要的时间（即hash函数本身不要太复杂）

b) 关键字的长度

c) 表长(不宜过长或过短，避免内存浪费和算力消耗)

d) 关键字分布是否均匀，是否有规律可循

e) 设计的hash函数在满足以上条件的情况下尽量减少冲突

2.哈希与哈希表

在理解了哈希的思维之后，我们要了解什么是哈希表，哈希表顾名思义就是经过哈希函数进行转换后的一张表，通过访问哈希表，我们可以快速查询哈希表，从而得出所需要得到的数据，构建哈希表的核心就是要考虑哈希函数的冲突处理（即经过数据压缩之后可能存在多数据同一个地址，需要利用算法将冲突的数据分别存储）。

冲突处理的方法有很多，最简单的有+1法，即地址数直接+1，当两个数据都需要存储进【2019】时，可以考虑将其中的一个存进【2020】

此外还有，开放定址法，链式地址发，公共溢出法，再散列法，质数法等等，各方法面对不同的数据特征有不同的效果。

3.哈希的思维

Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。

比如，利用哈希的思维在O(1)的复杂度情况下任意查询1000以内所有的质数（在创建是否是质数的时候并不是O(1)的复杂度），注意本样例只是演示思维，面对本需求可以有更好的空间利用方式（本写法比较浪费空间，仅供了解）。

#include<iostream>
using namespace std;
 
const int maxn=1002;
int arr[maxn]={0};
 
//判断是否是质数 
bool is_pri(int n){
    for(int i=n-1;i>=2;i--){
        if(n%i==0)  return false;
    }
    return true;
}
 
void create(){
    for(int i=3;i<=maxn;i++){
        if(is_pri(i)){
            arr[i]=1;
        }
    }
}
 
int main(){
    create();
    int input;
    while(cin>>input){
        if(arr[input]){
            cout<<input<<" 是质数"<<endl;
        }else{
            cout<<input<<" 不是质数"<<endl;
        }
    }
    return 0;
}