字符串hash算法比较

字符串hash 算法比较 1 概述 链表查找的时间效率为O(N)，二分法为log2N，B+ Tree 为log2N，但Hash 链表查找的时间效率为O(1)。 设计高效算法往往需要使用Hash 链表，常数级的查找速度是任何别的算法无法比拟的，Hash链表的构造和冲突的不同实现方法对效率当然有一定的影响，然 而Hash 函数是Hash 链表最核心的部分，本文尝试分析一些经典软件中使用到的字符串Hash 函数在执行效率、离散性、空间利用率等方面的性能问题。 2 经典字符串Hash 函数介绍 作者阅读过大量经典软件原代码，下面分别介绍几个经典软件中出现的字符串Hash 函数。 2.1 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; } 2.2 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); } 在下面的测量过程中我们分别将上面的两个函数标记为OpenSSL_Hash1 和OpenSSL_Hash2，至于上面的实现中使用MD5 算法的实现函数我们不作测试。 2.3 MySql 中出现的字符串 Hash 函数 #ifndef NEW_HASH_FUNCTION /* Calc hash...