Catalog
  1. 1. 基本概念
  2. 2. Hash的特点
  3. 3. 具体实现
Hash-学习

基本概念

Hash,一般翻译做“散列”,也有直接音译为“哈希”的。那么哈希函数的是什么样的?大概就是 value = hash(key),我们希望key和value之间是唯一的映射关系。   大家使用的最多的就是哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构,通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做哈希函数或散列函数。   实际中的Hash主要有两种应用:加密和压缩。在加密方面,Hash哈希是把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值,最广泛应用的Hash算法有MD4、MD5、SHA1。在压缩方面,Hash哈希是指把一个大范围映射到一个小范围,往往是为了节省空间,使得数据容易保存。   当然了,在我们做题的过程中,使用到的hash的方法都是十分简单的。

Hash的特点

  主要原理就是把大范围映射到小范围,因此输入范围必须和小范围相当或者比它更小,否则增加冲突。   Hash函数逼近单向函数,所以可以用来对数据进行加密。(单项函数:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来)   不同的应用对Hash函数有着不同的要求:用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

具体实现

Hash的方法非常多,有用加法的,有用乘法的,有用位运算的,还有混合的。这里,为了尽可能减小冲突的可能性,我们选择用混合运算去Hash。 Hash的具体思路就是把一串字符计算后形成一个数字。我们直接来看一段Hash的代码来理解吧:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff

using namespace std;

int hash(char s[])
{
int h = 0, l = strlen(s), k;
for(register int i = 0; i < l; i++)
{
k = s[i];
h = (h * 31 + k << 1) % 23456789;
}
return h;
}

char s[1000];

int main()
{
while(1)
{
cin >>s;
cout <<hash(s) << endl;
}
return 0;
}

Author: wflight
Link: http://yoursite.com/2019/08/02/Hash-学习/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment