首页  /  数据结构教程  /  哈希算法  /  

哈希算法

点击打开在线编译器,边学边练

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;
}


下一课:动态规划思想
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记