常用字符串hash函数总结

经典字符串常用的Hash函数有：BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等。BKDRHash和APHash是比较优秀的算法。具体要根据应用，是中文、英文还是混合的字符串，选择合适的Hash算法。

代码实现如下：

/** * FileName: allHash.cpp * Author: ACb0y * Create Time: 2011年3月20日21:55:53 * Last Modify Time: 2001年3月21日0:00:22 */ #include <iostream>using namespace std;typedef unsigned int uint;typedef struct node {char * str;struct node * pNext;}node;node * d[1000000];/** * 函数名：uint hashValue(char * str, uint hashFunction(char *str)); * 功能：用指定的hash函数求字符串的hash值 * 参数： * 输入： *str (char *): 字符串 *hashFunction (uint (char * str)): hash函数指针 *输出：无 * 返回值：得到的hash值 */uint getHashValue(char * str, uint hashFunction(char * str)) {return hashFunction(str) % 1000000;}/** * 函数名： uint SDBM_Hash(char * str); * 功能：获取字符串的SDBM哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的SDBM哈希值 */uint SDBM_Hash(char * str){uint hash = 0;while (*str) {hash = (*str++) + (hash <<6) + (hash <<16) - hash;}return (hash & 0x7FFFFFFF);}/** * 函数名： uint RS_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的RS哈希值 */uint RS_Hash(char * str){uint a = 63689;uint b = 378551;uint hash = 0;while (*str) {hash = hash * a + (*str++);a *= b;}return (hash & 0x7FFFFFFF);}/** * 函数名： uint JS_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的JS哈希值 */uint JS_Hash(char * str) {uint hash = 1315423911;while (*str) {hash ^= ((hash <<5) + (*str++) + (hash >> 2));}return (hash & 0x7FFFFFFF);}/** * 函数名： uint PJW_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的PJW哈希值 */uint PJW_Hash(char * str) {uint BitsInUnignedInt = (uint)(sizeof(uint) * 8);uint ThreeQuarters = (uint)((BitsInUnignedInt * 3) / 4);uint OneEighth= (uint)(BitsInUnignedInt / 8);uint HighBits = (uint)(0x7FFFFFFF) <<(BitsInUnignedInt - OneEighth);uint hash = 0;uint test = 0;while (*str) {hash = (hash <<OneEighth) + (*str++);if ((test = hash & HighBits) != 0) {hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));}}return (hash & 0x7FFFFFFF);}/** * 函数名： uint ELF_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的ELF哈希值 */uint ELF_Hash(char * str){uint hash = 0;uint x = 0;while (*str) {hash = (hash <<4) + (*str++);if ((x = hash & 0xF0000000L) != 0) {hash ^= (x >> 24);hash &= ~x;}}return (hash & 0x7FFFFFFF);}/** * 函数名： uint BKDR_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的BKDR哈希值 */uint BKDR_Hash(char * str){uint seed = 131; //31, 131, 1313, 13131, 131313 etc...uint hash = 0;while (*str) {hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}/** * 函数名： uint BKDR_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的BKDR哈希值 */uint DJB_Hash(char * str){uint hash = 5381;while (*str) {hash += (hash <<5) + (*str++);}return (hash & 0x7FFFFFFF);}/** * 函数名： uint BKDR_Hash(char * str); * 功能：获取字符串的RS哈希值 * 参数： *输入：str (char *): 字符串 * 输出：无 * 返回值：字符串的BKDR哈希值 */uint AP_Hash(char * str) {uint hash = 0;int i;for (i = 0; *str; ++i) {if ((i & 1) == 0) {hash ^= ((hash <<7) ^ (*str++) ^ (hash >> 3));}else {hash ^= (~((hash) <<11 ^ (*str++) ^ (hash >> 5)));}}return (hash & 0x7FFFFFFF);}/** * GCC中的字符串Hash函数ext/hash_fun.h * 函数名： size_t __stl_hash_string(const char * __s); * 功能：获取字符串的RS哈希值 * 参数： *输入：__s (const char *): 字符串 * 输出：无 * 返回值：字符串的哈希值 */inline size_t __stl_hash_string(const char * __s){unsigned long __h = 0;for (; *__s; ++__s) {__h = 5 * __h + *__s;}return size_t(__h);}/** * 函数名： void init(); * 功能：初始化node * d数组 * 参数： *输入：无 * 输出：无 * 返回值：无 */void init(){memset(d, 0, sizeof(d));}/** * 函数名： node * getNode(); * 功能：获取一个新的节点的指针 * 参数： *输入：无 * 输出：无 * 返回值：新申请的节点的指针 */node * getNode() {node * pNew = (node *)malloc(sizeof(node));pNew->pNext = NULL;pNew->str = NULL;return pNew;}/** * 函数名： bool insert(char * str, uint hashFunction(char * str)); * 功能：把字符串插入hash容器中 * 参数： *输入： * str (char *): 字符串uint hashFunction(char * str): hash函数 * 输出：无 * 返回值： * false: 插入失败 * true: 插入成功 */bool insert(char * str, uint hashFunction(char * str)) {node * pNew;pNew = getNode();if (NULL == pNew) {return false;}pNew->str = (char *)malloc(strlen(str) + 1);strcpy(pNew->str, str);uint hashValue = getHashValue(str, hashFunction);if (NULL == d[hashValue]) {d[hashValue] = pNew;}else {pNew->pNext = d[hashValue];d[hashValue]->pNext = pNew;}return true;}/** * 函数名：bool query(char * str, uint hashFunction(char * str)); * 功能：hash容器中查找字符串 * 参数： *输入： * str (char *): 字符串uint hashFunction(char * str): hash函数 * 输出：无 * 返回值： * 查找到的指向str的指针。 */char * query(char * str, uint hashFunction(char * str)) {uint hashValue = getHashValue(str, hashFunction);if (NULL == d[hashValue]) {return NULL;}node * pCur = d[hashValue];while (NULL != pCur) {if (strcmp(pCur->str, str) == 0) {return pCur->str;}pCur = pCur->pNext;}return NULL;}int main(){init();freopen("in.txt", "r", stdin);int n, k;char str[1000];scanf("%d%d/n", &n, &k);cout <<n <<" " <<k <<endl;while (n--) {gets(str);insert(str, BKDR_Hash);}while (k--) {gets(str);char * pStr = query(str, BKDR_Hash);if (NULL == pStr) {printf("not found!/n");}else {printf("find the string = %s/n", pStr);}}return 0;}