字符串的经典hash算法

本文涉及的产品
云数据库 RDS MySQL,集群版 2核4GB 100GB
推荐场景:
搭建个人博客
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用版 2核4GB 50GB
简介: http://hi.baidu.com/csdnail/blog/item/77b5771a262b1cd8ac6e75fc.html字符串的经典hash算法2010-06-06 15:101 概述链表查找的时间效率为O(N),二分法为log2N,B+ Tree为log2N,但Hash链表查找的时间效率为O(1)。

字符串的经典hash算法
2010-06-06 15:10
1 概述

链表查找的时间效率为O(N),二分法为log2N,B+ Tree为log2N,但Hash链表查找的时间效率为O(1)。 
设计高效算法往往需要使用Hash链表,常数级的查找速度是任何别的算法无法比拟的,Hash链表的构造和冲突的不同实现方法对效率当然有一定的影响,然而Hash函数是Hash链表最核心的部分,本文尝试分析一些经典软件中使用到的字符串Hash函数在执行效率、离散性、空间利用率等方面的性能问题。

打造最快的Hash表(和Blizzard的对话)

先提一个简单的问题,如果有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?

有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来。

最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法

unsigned long HashString(char *lpszFileName, unsigned long dwHashType)

unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;

while(*key != 0)

   ch = toupper(*key++);

seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 
}
return seed1; 
}

Blizzard的这个算法是非常高效的,被称为"One-Way Hash",举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。

int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)

int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;

if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString)) 
   return nHashPos; 
else 
   return -1; //Error value 
}

看到此,我想大家都在想一个很严重的问题:"如果两个字符串在哈希表中对应的位置相同怎么办?",毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝,我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。

然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能,但用三个不同的哈希算法算出的入口点都一致,那几乎可以肯定是不可能的事了,这个几率是1: 18889465931478580854784,大概是10的 22.3次方分之一,对一个游戏程序来说足够安全了。

现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)

const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;

while (lpTable[nHashPos].bExists)

   if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB) 
    return nHashPos; 
   else 
    nHashPos = (nHashPos + 1) % nTableSize;

   if (nHashPos == nHashStart) 
    break; 
}

return -1; //Error value 
}

1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回
4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回
5. 移到下一个位置,如果已经越界,则表示没有找到,返回
6. 看看是不是又回到了原来的位置,如果是,则返回没找到
7. 回到3

 

/////////////////////////////////////////////////////////

其他的一些哈希函数:

/////////////////////////////////////////////////////////

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 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函数,另外我们将上面的两个函数分别记为MYSQL_Hash1和MYSQL_Hash2。 
2.4 另一个经典字符串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; 

3 测试及结果 
3.1 测试说明 
从上面给出的经典字符串Hash函数中可以看出,有的涉及到字符串大小敏感问题,我们的测试中只考虑字符串大小写敏感的函数,另外在上面的函数中有的函数需要长度参数,有的不需要长度参数,这对函数本身的效率有一定的影响,我们的测试中将对函数稍微作一点修改,全部使用长度参数,并将函数内部出现的计算长度代码删除。 
我们用来作测试用的Hash链表采用经典的拉链法解决冲突,另外我们采用静态分配桶(Hash链表长度)的方法来构造Hash链表,这主要是为了简化我们的实现,并不影响我们的测试结果。 
测试文本采用单词表,测试过程中从一个输入文件中读取全部不重复单词构造一个Hash表,测试内容分别是函数总调用次数、函数总调用时间、最大拉链长度、 平均拉链长度、桶利用率(使用过的桶所占的比率),其中函数总调用次数是指Hash函数被调用的总次数,为了测试出函数执行时间,该值在测试过程中作了一 定的放大,函数总调用时间是指Hash函数总的执行时间,最大拉链长度是指使用拉链法构造链表过程中出现的最大拉链长度,平均拉链长度指拉链的平均长度。 
测试过程中使用的机器配置如下: 
PIII600笔记本,128M内存,windows 2000 server操作系统。 
3.2 测试结果 
以下分别是对两个不同文本文件中的全部不重复单词构造Hash链表的测试结果,测试结果中函数调用次数放大了100倍,相应的函数调用时间也放大了100倍。

 

 


从上表可以看出,这些经典软件虽然构造字符串Hash函数的方法不同,但是它们的效率都是不错的,相互之间差距很小,读者可以参考实际情况从其中借鉴使用。

相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境,其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
相关文章
|
19天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
185 1
|
21天前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
27天前
|
存储 算法 Java
Java数据结构与算法:用于高效地存储和检索字符串数据集
Java数据结构与算法:用于高效地存储和检索字符串数据集
|
29天前
|
算法 Java
Java数据结构与算法:字符串匹配算法之暴力匹配
Java数据结构与算法:字符串匹配算法之暴力匹配
|
29天前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
1月前
|
算法 Java
Java中常用hash算法总结
Java中常用hash算法总结
20 0
|
5天前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
2天前
|
传感器 机器学习/深度学习 算法
基于GA遗传算法的WSN网络节点覆盖优化matlab仿真
本研究应用遗传优化算法于无线传感器网络(WSN),优化节点布局与数量,以最小化节点使用而最大化网络覆盖率。MATLAB2022a环境下,算法通过选择、交叉与变异操作,逐步改进节点配置,最终输出收敛曲线展现覆盖率、节点数及适应度值变化。无线传感器网络覆盖优化问题通过数学建模,结合遗传算法,实现目标区域有效覆盖与网络寿命延长。算法设计中,采用二进制编码表示节点状态,适应度函数考量覆盖率与连通性,通过选择、交叉和变异策略迭代优化,直至满足终止条件。
|
8天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。

热门文章

最新文章