Created
December 30, 2012 11:14
-
-
Save hoterran/4412241 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ●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&0×0f)); | |
| 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=0×100; | |
| while (*c) | |
| { | |
| v=n|(*c); | |
| n+=0×100; | |
| r= (int)((v>>2)^v)&0×0f; | |
| 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); | |
| } | |
| #endif | |
| Mysql中对字符串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 Functions | |
| A comprehensive collection of hash functions, a hash visualiser and some test results [see Mckenzie et al. Selecting a Hashing Algorithm, SP&E 20(2):209-224, Feb 1990] will be available someday. If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes. you are not likely to do better with one of the "well known" functions such as PJW, K&R[1], etc. Also see tpop pp. 126 for graphing hash functions. | |
| djb2 | |
| this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained. | |
| unsigned long | |
| hash(unsigned char *str) | |
| { | |
| unsigned long hash = 5381; | |
| int c; | |
| while (c = *str++) | |
| hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ | |
| return hash; | |
| } | |
| sdbm | |
| this algorithm was created for sdbm (a public-domain reimplementation of ndbm) database library. it was found to do well in scrambling bits, causing better distribution of the keys and fewer splits. it also happens to be a good general hashing function with good distribution. the actual function is hash(i) = hash(i - 1) * 65599 + str[i]; what is included below is the faster version used in gawk. [there is even a faster, duff-device version] the magic constant 65599 was picked out of thin air while experimenting with different constants, and turns out to be a prime. this is one of the algorithms used in berkeley db (see sleepycat) and elsewhere. | |
| static unsigned long | |
| sdbm(str) | |
| unsigned char *str; | |
| { | |
| unsigned long hash = 0; | |
| int c; | |
| while (c = *str++) | |
| hash = c + (hash << 6) + (hash << 16) - hash; | |
| return hash; | |
| } | |
| lose lose | |
| This hash function appeared in K&R (1st ed) but at least the reader was warned: "This is not the best possible algorithm, but it has the merit of extreme simplicity." This is an understatement; It is a terrible hashing algorithm, and it could have been much better without sacrificing its "extreme simplicity." [see the second edition!] Many C programmers use this function without actually testing it, or checking something like Knuth's Sorting and Searching, so it stuck. It is now found mixed with otherwise respectable code, eg. cnews. sigh. [see also: tpop] | |
| unsigned long | |
| hash(unsigned char *str) | |
| { | |
| unsigned int hash = 0; | |
| int c; | |
| while (c = *str++) | |
| hash += c; | |
| return hash; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment