常见的几种hash算法的原理
2011-07-13 17:51
几种经典的hash算法
注:最近因为在做和hash有关的题目,感到很纠结。虽然上学期数据结构学过,但是当时觉得hash没什么用,所以没有认真学~后悔啊~~~现在恶补一下~
计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人 类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函 数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。
Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
应用于加密的Hash函数已经探讨过太多了,在作者的博客里面有更详细的介绍。所以,本文只探讨用于查找的Hash函数。Hash函数应用的主要对象是数组(比如,字符串),而其目标一般是一个int类型。以下我们都按照这种方式来说明。一般的说,Hash函数可以简单的划分为如下几类:
1. 加法Hash;
2. 位运算Hash;
3. 乘法Hash;
4. 除法Hash;
5. 查表Hash;
6. 混合Hash;
下面详细的介绍以上各种方式在实际中的运用。
一 加法Hash
所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:
static int additiveHash(String key, int prime)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
这里的prime是任意的质数,看得出,结果的值域为[0,prime-1]。
二 位运算Hash
这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比如,标准的旋转Hash的构造如下: static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i<key.length(); ++i)
hash = (hash<<4)^(hash>>28)^key.charAt(i);
return (hash % prime);
}
先移位,然后再进行各种位运算是这种类型Hash函数的主要特点。比如,以上的那段计算hash的代码还可以有如下几种变形:
1. hash = (hash<<5)^(hash>>27)^key.charAt(i);
2. hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
3. if((i&1) == 0)
{
hash ^= (hash<<7) ^ key.charAt(i) ^ (hash>>3);
}
else
{
Hash 函数的常用算法和应用领域 1.Hash 介绍 Hash 这个在实现某些功能的经常会...所以,在考虑使用 Hash 函数之前,需要明白它的几个限制: 1. Hash 的主要原理...
simhash算法的原理_计算机软件及应用_IT/计算机_专业资料。传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。传统hash...
常用的几个著名哈希算法源代码.cs_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 常用的几个著名哈希算法源代码.cs_IT/计算机_专业资料。class General...
常用的几个著名哈希算法源... 2页 免费 Hash算法 1页 2财富值 Hash算法 6...本文档中介绍了常见的各种hash算法,作者用通俗的语言,言简意赅!本文档中介绍了常...
本文介绍了 Hash 算法原理,并从一个校园网流量计费系统的实例入手,诠释快速检索...常用的定 位方法有以下几种: 1. 直接寻址法:取关键字或关键字的某个线性...
几种经典的Hash算法的实现(源代码)_IT/计算机_专业资料。几种经典的Hash算法的实现(源代码)链表查找的时间效率为 O(N),二分法为 log2N,B+ Tree 为 log2N,但...
被逼的,发个技术文章吧(几种经典的 hash 算法) ...Hash 的主要原理就是把大范围映射到小范围;所以,你...函数通过利用各种位运算(常见的是移位和异或)来充分...
几种,分别为:md2、md4、md5 和安全哈希算法(sha...哈希表的工作原理就是把一个数据帧按照某一种设定好...的算法就是哈希 算法,其中以 md5 算法最为常见。...
sheagle@yeah.net Hash join 算法原理自从 oracke 7...oracle 引进了几种技术,位图向量过滤、角色互换、...常见hash算法 9页 免费 字符串hash算法比较 6页 免费...
几种经典的Hash算法的实现(源代码)_IT/计算机_专业资料。几种经典的Hash算法的实现(源代码)链表查找的时间效率为 O(N),二分法为 log2N,B+ Tree 为 log2N,但...
热门文档