|
|
多种哈希算法代码，用于文件校验、简单加密等场合。
哈希表也称作散列表，叫法不同，是一个意思。这种数据结构提供了键值对的映射关系，给出键就可以快速得到对应的值，比如上面提到的"50号"就是键，游戏机就是键得到的值。时间复杂度接近O(1)。哈希表是如何根据键来得到值的呢？我们来揭秘这个过程。
内容介绍
/***************************************
Copyright2008-2015,www.xxx.com
Filename:HashFunction.h
Author:
Version:V00R001
Date:
Description:Hash函数集合，包含主流的hash函数
StructList:
Functionlist:
History:
1.Date:2008-10-25
Create:
Modification:create
***************************************/#include"HashFunction.h"#definengx_hash(key,c)((u_int)key*31+c)
unsignedintngx_hash_key(conststd::string&data)
{
size_tlen=data.size();
unsignedinti,key;
key=0;for(i=0;i<len;i++){
key=ngx_hash(key,data);
}returnkey;
}//经典字符串Hash函数unsignedintpub_inthash(constchar*str)
{
registerunsignedinth;
registerunsignedchar*p;
for(h=0,p=(unsignedchar*)str;*p;p++)
h=31*h+*p;
returnh;
}
//PHP中出现的字符串Hash函数unsignedlongphp_longhashpjw(constchar*str)
{
unsignedlongh=0,g;
char*p;
for(h=0,p=(char*)str;*p;p++)
{
h=(h<<4)+*p++;
if((g=(h&0xF0000000)))
{
h=h^(g>>24);
h=h^g;
}
}
returnh;
}
//OpenSSL中出现的字符串Hash函数unsignedintOpenSSL_strhash1(constchar*str)
{
inti,l;
unsignedintret=0;
unsignedshort*s;
if(str==NULL)return(0);
l=(strlen(str)+1)/2;
s=(unsignedshort*)str;
for(i=0;i
ret^=(s<<(i&0x0f));
return(ret);
}
//MySql中出现的字符串Hash函数unsignedintmysql_hashnr1(constchar*key,unsignedintlength)
{
registerunsignedintnr=1,nr2=4;
while(length--)
{
nr^=(((nr&63)+nr2)*((unsignedint)(unsignedchar)*key++))+(nr<<8);
nr2+=3;
}
return((unsignedint)nr);
}
unsignedintmysql_hashnr_caseup1(constchar*key,unsignedintlength)
{
registerunsignedintnr=1,nr2=4;
while(length--)
{
nr^=(((nr&63)+nr2)*((unsignedint)(unsignedchar)toupper(*key++)))+(nr<<8);
nr2+=3;
}
return((unsignedint)nr);
}
unsignedintmysql_hashnr2(constchar*key,unsignedintlen)
{
constchar*end=key+len;
unsignedinthash;
for(hash=0;key<end;key++)
{
hash*=16777619;
hash^=(unsignedint)*(unsignedchar*)key;
}
return(hash);
}
unsignedintmysql_hashnr_caseup2(constchar*key,unsignedintlen)
{
constchar*end=key+len;
unsignedinthash;
for(hash=0;key<end;key++)
{
hash*=16777619;
hash^=(unsignedint)(unsignedchar)toupper(*key);
}
return(hash);
}
/**
*加法hash
*@paramkey字符串
*@paramprime一个质数
*@returnhash结果
*/intadditiveHash(conststd::string&key,intprime)
{
unsignedinthash,i;for(hash=key.size(),i=0;i<key.size();i++)
hash+=key;return(hash%prime);
}/**
*旋转hash
*@paramkey输入字符串
*@paramprime质数
*@returnhash值
*/
introtatingHash(conststd::string&key,intprime)
{
unsignedinthash,i;fo(hash=key.size(),i=0;i
hash=(hash<<4)^(hash>>28)^key;return(hash%prime);//return(hash^(hash>>10)^(hash>>20));}/**
*一次一个hash
*@paramkey输入字符串
*@return输出hash值
*/
intoneByOneHash(conststd::string&key)
{
unsignedinthash,i;for(hash=0,i=0;i
{
hash+=key;
hash+=(hash<<10);
hash^=(hash>>6);
}
hash+=(hash<<3);
hash^=(hash>>11);
hash+=(hash<<15);//return(hash&M_MASK);
returnhash;
}/**
*Bernstein'shash
*@paramkey输入字节数组
*@paramlevel初始hash常量
*@return结果hash
*/
intbernstein(conststd::string&key)
{
unsignedinthash=0;
unsignedinti;for(i=0;i
}/**
*RS算法hash
*@paramstr字符串
*/unsignedintRSHash(conststd::string&str)
{
unsignedintb=378551;
unsignedinta=63689;
unsignedinthash=0;for(unsignedinti=0;i<str.size();i++)
{
hash=hash*a+str;
a=a*b;
}return(hash&0x7FFFFFFF);
}/**
*JS算法
*/
intJSHash(conststd::string&str)
{inthash=1315423911;for(unsignedinti=0;i<str.size();i++)
{
hash^=((hash<<5)+str+(hash>>2));
}return(hash&0x7FFFFFFF);
}/**
*PJW算法
*/
intPJWHash(conststd::string&str)
{intBitsInUnsignedInt=32;intThreeQuarters=(BitsInUnsignedInt*3)/4;intOneEighth=BitsInUnsignedInt/8;intHighBits=0xFFFFFFFF<<(BitsInUnsignedInt-OneEighth);inthash=0;inttest=0;for(unsignedinti=0;i<str.size();i++)
{
hash=(hash<<OneEighth)+str;if((test=hash&HighBits)!=0)
{
hash=((hash^(test>>ThreeQuarters))&(~HighBits));
}
}return(hash&0x7FFFFFFF);
}/*EndOfP.J.WeinbergerHashFunction*//**
*ELF算法
*/
intELFHash(conststd::string&str)
{inthash=0;intx=0;for(unsignedinti=0;i<str.size();i++)
{
hash=(hash<<4)+str;if((x=(int)(hash&0xF0000000L))!=0)
{
hash^=(x>>24);
hash&=~x;
}
}return(hash&0x7FFFFFFF);
}/*EndOfELFHashFunction*//**
*BKDR算法
*/uint32_tBKDRHash32(conststd::string&str)
{uint32_tseed=131;//31131131313131131313etc..
uint32_thash=0;for(unsignedinti=0;i<str.size();++i)
{
hash=(hash*seed)+str;
}return(uint32_t)hash;
}uint64_tBKDRHash64(conststd::string&str)
{uint64_tseed=131;//31131131313131131313etc..
uint64_thash=0;for(unsignedinti=0;i<str.size();++i)
{
hash=(hash*seed)+str;
}return(uint64_t)hash;
}/*EndOfBKDRHashFunction*//**
*SDBM算法
*/
intSDBMHash(conststd::string&str)
{inthash=0;for(unsignedinti=0;i<str.size();i++)
{
hash=str+(hash<<6)+(hash<<16)-hash;
}return(hash&0x7FFFFFFF);
}/*EndOfSDBMHashFunction*//**
*DJB算法
*/unsignedintDJBHash(conststd::string&str)
{
unsignedinthash=5381;for(unsignedinti=0;i<str.size();i++)
{
hash=((hash<<5)+hash)+str;
}return(hash&0x7FFFFFFF);
}/*EndOfDJBHashFunction*//**
*DEK算法
*/
intDEKHash(conststd::string&str)
{inthash=str.size();for(unsignedinti=0;i<str.size();i++)
{
hash=((hash<<5)^(hash>>27))^str;
}return(hash&0x7FFFFFFF);
}/*EndOfDEKHashFunction*//**
*AP算法
*/
intAPHash(conststd::string&str)
{inthash=0;for(unsignedinti=0;i<str.size();i++)
{
hash^=((i&1)==0)?((hash<<7)^str^(hash>>3)):
(~((hash<<11)^str^(hash>>5)));
}//return(hash&0x7FFFFFFF);
returnhash;
}/*EndOfAPHashFunction*//**
*JAVA自己带的算法
*/
intjava(conststd::string&str)
{inth=0;intoff=0;
unsignedintlen=str.size();for(unsignedinti=0;i<len;i++)
{
h=31*h+str[off++];
}returnh;
}复制 |
|
窥视卡
雷达卡
发表于 2022-6-6 20:10
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡