《hash算法大全.doc》由会员分享，可在线阅读，更多相关《hash算法大全.doc（18页珍藏版）》请在三一文库上搜索。
1、今天女朋友老是问我 hash函数的一些具体实现，在网上找了一些算法，顺便在这里晒一晒。/* Hash算法大全*推荐使用FNV1算法* algorithm None* author Goodzzp 2006-11-20* lastEdit Goodzzp 2006-11-20* editDetail Create*/public class HashAlgorithms/*加法hash* param key 字符串* param prime 一个质数* retur n hash 结果*/public static int additiveHash (String key , int prime
2、)int hash, i ;for (hash = key . length (), i = 0 ; i key . length (); i +)hash += key . charAt (i);return (hash %prime );/*旋转hash* param key输入字符串* param prime 质数* retur n hash 值*/public static int rotatingHash (String key , int prime ) int hash, i ;for (hash=key.length (), i =0; i key. length (); +i
3、)hash = (hash28)A key. charAt (i);return (hash %prime );/ return (hash a (hash10) a (hash20);/替代：/ 使用：hash = (hash a (hash10) a (hash20) & mask;/ 替代：hash %= prime;/* MASK值，随便找一个值，最好是质数*/static int M_MASK= 0x8765fed1 ;/* 一次一个 hash* param key输入字符串* return 输出 hash 值*/ public static int on eBy On eHash
4、Stri ng key) int hash, i ;for (hash=0, i =0; i key. length ();+i)hash+= key . charAt (i);hash+= (hash 6);hash+= (hash 11);hash+= (hash 15);/ return (hash & M_MASK);return hash;/Illi Pearsons Hash/ char pears on( charkey, ub4 len, char tab256)II II char hash;II ub4 i;II for (hash=le n, i=0; ile n; +i
5、)II hash=tabhashAkeyi;II return (hash);II IIII CRC Hashing ，计算crc,具体代码见其他II ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab256)II / ub4 hash, i;/ for (hash=le n, i=0; i 8) A tab(hash & 0xff) A keyi;/ return (hash & mask);/ /*Uni versal Hashi ng */public staticint universal (char key, int mask, int tab
6、 )int hash = key . length , i , len = key . lengthfor (i =0; i ( len 3;=tab i +0;=tab i +1;=tab i +2;=tab i +3;=tab i +4;=tab i +5;=tab i +6;=tab i +7;if ( k&0x01)if ( k&0x02)if ( k&0x04)if ( k&0x08)if ( k&0x10)if ( k&0x20)if ( k&0x40)if ( k&0x80)=0 ) hash a=0 ) hash a=0 ) hash a=0 ) hash a=0 ) hash
7、 a=0 ) hash a=0 ) hash a=0 ) hash aretur n (hash & mask);/* * Zobrist Hash ingtab )*/public static int zobrist ( char key, int mask, int int hash, i ;for (hash=key. length , i =0; i M_SHIFT) & M_MASK/* 改进的32位FNV算法1* param data 数组* return int 值*/public static int FNVHashlbyte data )finalint p = 16777
8、619;inthash = (int ) 2166136261L;for (byte b : data)hash=(hash a b ) * p ;hash+= hash 7 ;hash+= hash 17 ;hash+= hash 5 ;return hash ;/*改进的32位FNV算法1param data 字符串return int 值*/publicstatic int FNVHashlString data )finalint p = 16777619;inthash = (int ) 2166136261L;for(int i =0; i data. length (); i +
9、)hash=(hash a data . charAt (i) * p ;hash+= hash 7 ;hash+= hash 17 ;hash+= hash 5 ;return hash ;* Thomas Wang 的算法，整数 hash*/publicstatic int intHash (int key)key+= (key 10);key+= (key 6);key+=(key 16);returnkey ;/* RS 算法 hash* param str 字符串*/public static int RSHash(String str )intb =378551inta =6368
10、9;inthashi = 0;for (int i = 0 ; i str . length (); i +)hash = hash * a + str . charAt (i);a = a * b ;return (hash & 0x7FFFFFFF)；/* End Of RS Hash Function */* * JS 算法*/public static int JSHash( String str )int hash = 1315423911;for (int i = 0 ; i str . length (); i +)hash A = ( hash 2);return (hash
11、& 0x7FFFFFFF)；/* End Of JS Hash Function */* PJW 算法*/public static int PJWHashString str )int BitsInUnsignedlnt= 32 ;int ThreeQuarters = (BitsInUnsignedlnt* 3) / 4 ;int On eEighth = BitsI nUn sig nedl nt/ 8 ;int HighBits = 0xFFFFFFFF (BitsI nUn sig ned Int- On eEighth );int hash = 0 ;int test = 0;fo
12、r (int i = 0 ; i str . length (); i +)hash = (hash ThreeQuarters ) & (HighBits );return (hash & 0x7FFFFFFF);/* End Of P. J. Wei nberger Hash Fun ction */* * ELF 算法*/publicstatic int ELFHash( String str )inthash = 0;int=0;for(inti = O ; i str . length (); i +)hashif (x=(hash 24);hash&= x;return(hash
13、& 0x7FFFFFFF；/* End Of ELF Hash Function */* * BKDR 算法*/public static int BKDRHashString str )int seed = 131 ; / 31 131 1313 13131 131313 etc.int hash = 0 ;for (int i = 0 ; i str . length (); i +)hash = (hash * seed) + str .charAt(i);return (hash & 0x7FFFFFFF)；/* End Of BKDR Hash Function */* SDBM 算
14、法*/public static int SDBMHas(lString str )int hash = 0 ;for (int i = 0 ; i str . length (); i +)-hash ;hash = str . charAt (i) + (hash 6) + (hash 16)return (hash & 0x7FFFFFFF);/* End Of SDBM Hash Function */* DJB 算法*/public static int DJBHash(String str )int hash = 5381 ;for (int i = 0 ; i str . len
15、gth (); i +)hash = ( hash 5) + hash ) + str .charAt(i); return (hash & 0x7FFFFFFF)；/* End Of DJB Hash Fu nction */* DEK 算法*/public static int DEKHashString str )int hash = str . length ();for (int i = 0 ; i str . length (); i +)hash = ( hash 27 ) A str . charAt (i);return (hash & 0x7FFFFFFF)；/ JAVA
16、自己带的算法*/public static int java (String str )int h = 0 ;原文地址 End Of DEK Hash Fun ction */* AP 算法*/public static int APHash( String str )int hash = 0 ;for (int i = 0 ; i 3):a (hash 5);hash A = ( i & 1 ) = 0) ? ( (hash 7) A str . charAt (i) A( hash 11) a str . charAt (i)/ return (hash & 0x7FFFFFFF);ret
17、urn hash;/* End Of AP Hash Function */intoff=0;intlen=str.length ();for(inti =:0 ; i len ;i +)h=31 * h+ str . charAt(off +);return h;/* 混合hash算法，输出64位的值*/public static long mixHash(String str ) long hash = str . hashCodeQ;hash= 32;hash|= FNVHashTstr );return hash;*Bern ste ins hash* param key输入字节数组* param level 初始 hash 常量* return 结果 hash*/public static int bernstein (String key)int hash = 0 ;int i ;for (i =0; i key. length ();+i) hash = 33 *hash + key . charAt (i);return hash;