哈希算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入,在计算上是不可能的,所以数据的哈希值可以检验数据的完整性。
链表查找的时间效率为O(N),二分法为log2N,B+ Tree为log2N,但Hash链表查找的时间效率为O(1)。
设计高效算法往往需要使用Hash链表,常数级的查找速度是任何别的算法无法比拟的,Hash链表的构造和冲突的不同实现方法对效率当然有一定的影响,然 而Hash函数是Hash链表最核心的部分,下面是几款经典软件中使用到的字符串Hash函数实现,通过阅读这些代码,我们可以在Hash算法的执行效率、离散性、空间利用率等方面有比较深刻的了解。
下面分别介绍几个经典软件中出现的字符串Hash函数。
●PHP中出现的字符串Hash函数
static unsigned long hashpjw(char *arKey, unsigned int nKeyLength)
{
unsigned long h = 0, g;
char *arEnd=arKey+nKeyLength;
while (arKey < arEnd) {
h = (h << 4) + *arKey++;
if ((g = (h & 0xF0000000))) {
h = h ^ (g >> 24);
h = h ^ g;
}
}
return h;
}
●OpenSSL中出现的字符串Hash函数
unsigned long lh_strhash(char *str)
{
int i,l;
unsigned long ret=0;
unsigned short *s;
if (str == NULL) return(0);
l=(strlen(str)+1)/2;
s=(unsigned short *)str;
for (i=0; i
ret^=(s[i]<<(i&0x0f));
return(ret);
}
/* The following hash seems to work very well on normal text strings
* no collisions on /usr/dict/words and it distributes on %2^n quite
* well, not as good as MD5, but still good.
*/
unsigned long lh_strhash(const char *c)
{
unsigned long ret=0;
long n;
unsigned long v;
int r;
if ((c == NULL) || (*c == '\0'))
return(ret);
/*
unsigned char b[16];
MD5(c,strlen(c),b);
return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
*/
n=0x100;
while (*c)
{
v=n|(*c);
n+=0x100;
r= (int)((v>>2)^v)&0x0f;
ret=(ret(32-r));
ret&=0xFFFFFFFFL;
ret^=v*v;
c++;
}
return((ret>>16)^ret);
}
●MySql中出现的字符串Hash函数
#ifndef NEW_HASH_FUNCTION
/* Calc hashvalue for a key */
static uint calc_hashnr(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length--)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
/* Calc hashvalue for a key, case indepenently */
static uint calc_hashnr_caseup(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length--)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
#else
/*
* Fowler/Noll/Vo hash
*
* The basis of the hash algorithm was taken from an idea sent by email to the
* IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
* Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
* later improved on their algorithm.
*
* The magic is in the interesting relationship between the special prime
* 16777619 (2^24 + 403) and 2^32 and 2^8.
*
* This hash produces the fewest collisions of any function that we've seen so
* far, and works well on both numbers and strings.
*/
uint calc_hashnr(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) *(uchar*) key;
}
return (hash);
}
uint calc_hashnr_caseup(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) (uchar) toupper(*key);
}
return (hash);
}
#endifMysql中对字符串Hash函数还区分了大小写
●另一个经典字符串Hash函数
unsigned int hash(char *str)
{
register unsigned int h;
register unsigned char *p;
for(h=0, p = (unsigned char *)str; *p ; p++)
h = 31 * h + *p;
return h;
}
分享到:
相关推荐
几种经典的Hash算法的实现(源代码)
Java源代码实现部分,比较有意思,也具参考性。像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java...
该库以几种不同的方式提供了Austin Appleby的非加密“ MurmurHash”哈希算法功能。 主要特征: 阻塞和异步api接口 基于其他MurmurHash3 32位和128位渐进实现 流封装器,用于带有渐进式哈希器。类似于bi-api接口 渐...
尽管MD4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外,其中比较有名的还有SHA-1、RIPE-MD以及HAVAL等。 一年以后,即1991年...
Java源代码实现部分,比较有意思,也具参考性。像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java...
尽管MD4算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外,其中比较有名的还有sha-1、RIPEMD以及Haval等。 一年以后,即1991年,...
龙 翀 -《解决空间规模问题的几种常用的存储结构》 骆 骥 -《数学模型的建立和选择》 施 遥 -《人工智能在围棋程序中的应用》 肖 洲 -《数据结构的在程序设计中的应用》 谢 婧 -《规模化问题的解题策略》 徐 串...
10.求以下表达式的值,写出您想到的一种或几种实现方法: 1-2+3-4+……+m [Page] 答: int Num = this.TextBox1.Text.ToString() ; int Sum = 0 ; for (int i = 0 ; i ; i++) { if((i%2) == 1) { Sum += i ; ...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...
7、HAProxy负载均衡算法具体有如下几种: ①roundrobin,表示简单的轮询,这个不多说,这个是负载均衡基本都具备的; ②static-rr,表示根据权重; ③leastconn,表示最少连接者先...
对软件而言,逆向工程归结起来就是拿一个既没有源代码又没有准确文献资料的现成程序,尝试恢复出它的设计和实现细节。在某些情况下,可以找到程序的源代码,但是找不到最初的开发人员了。本书所讨论的就是通常所说的...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...
JOpenID是一个轻量级的OpenID 2.0 Java客户端,仅50KB+(含源代码),允许任何Web网站通过OpenID支持用户直接登录而无需注册,例如Google Account或Yahoo Account。 JActor的文件持久化组件 JFile JFile 是 JActor ...