散列表(一)- 散列表及常用字符串哈希函数
散列表
散列表又称哈希表(hash table),是普通数组概念的推广。它将数据的关键字信息通过哈希函数映射到数组的索引上,然后将数据存储在数组对应的索引上,这样访问数据时就可以按照数组的方式来访问,可以加快访问速度。
将关键字映射到数组索引的函数就叫做哈希函数。
常用字符串哈希函数
下面我们对一些常用的字符串哈希函数进行介绍,它们都是计算机科学家研究出来的,映射后的地址比较平均,冲突较少。函数都以科学家名字或项目名称命名:
1. SKDR Hash
BKDRHash 是 Kernighan 和 Dennis 在《The C programming language》中提出的。
#define UNSIGNED_INT_MAX (0x7fffffff)
//BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 31; //31,131, 1313, 13131,..
unsigned hashVal = 0;
while (*str)
hashVal = hashVal * seed + (*str++);
return (hashVal & UNSIGNED_INT_MAX);
}
2. AP Hash
Arash Partow 提出了这个算法。
//Arash Partow, AP Hash function
unsigned int APHash(char *str)
{
unsigned int hashVal = 0;
for (int i = 0; *str != '\0'; i++)
{
if ((i & 1) == 0) //偶数
hashVal ^= ((hashVal << 7) ^ (*str++) ^ (hashVal >> 3));
else //奇数
hashVal ^= (~((hashVal << 11) ^ (*str++) ^ (hashVal >> 5)));
}
return (hashVal & UNSIGNED_INT_MAX);
}
3. DJB Hash
Daniel J. Bernstein 在 comp.lang.c 邮件列表中发表的。
//Daniel J. Bernstein, DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hashVal = 5381;
while (*str)
hashVal += (hashVal << 5) + (*str++);
return (hashVal & UNSIGNED_INT_MAX);
}
4. JS Hash
Justin Sobel 提出的基于位的函数函数。
//Justin Sobel, JS Hash function
unsigned int JSHash(char *str)
{
unsigned int hashVal = 1315423911;
while (*str)
hashVal ^= ((hashVal << 5) + (*str++) + (hashVal >> 2));
return (hashVal & UNSIGNED_INT_MAX);
}
5. RS Hash
Robert Sedgwicks 提出的这个哈希函数。
//Robert Sedgwicks, RS Hash function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hashVal = 0;
while (*str)
{
hashVal = hashVal * a + (*str++);
a *= b;
}
return (hashVal & UNSIGNED_INT_MAX);
}
6. SDBM Hash
SDBM项目使用的哈希函数。
//SDBM Hash function
unsigned int SDBMHash(char *str)
{
unsigned int hashVal = 0;
while (*str)
hashVal = (*str++) + (hashVal << 6) + (hashVal << 16) - hashVal;
return (hashVal & UNSIGNED_INT_MAX);
}
7. PJW Hash
Peter J. Weinberger在其编译器著作中提出的。
//Peter J.Weinberger PJWHash Hash function
unsigned int PJWHash(char *str)
{
unsigned charBit = 8;
unsigned int bitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * charBit);
unsigned int threeQuarter = (unsigned int)((bitsInUnsignedInt * 3) / 4);
unsigned int oneEighth = (unsigned int)(bitsInUnsignedInt / 8);
unsigned int highBits = (unsigned int)(0xFFFFFFFF) << (bitsInUnsignedInt - oneEighth);
unsigned int hashVal = 0;
unsigned int test = 0;
while (*str)
{
hashVal = (hashVal << oneEighth) + (*str++);
if ((test = hashVal & highBits) != 0)
hashVal = ((hashVal ^ (test >> threeQuarter)) & (~highBits));
}
return (hashVal & UNSIGNED_INT_MAX);
}
8. ELF Hash
Unix系统上面广泛使用的哈希函数。
//UnixSystem, ELF Hash function
unsigned int ELFHash(char *str)
{
unsigned int hashVal = 0;
unsigned int x = 0;
while (*str)
{
hashVal = (hashVal << 4) + (*str++);
if ((x = hashVal & 0xF0000000L) != 0)
{
hashVal ^= (x >> 24);
hashVal &= ~x;
}
}
return (hashVal & UNSIGNED_INT_MAX);
}
9. DEK Hash
高德纳(Donald E. Knuth)在《计算机程序设计的艺术》中提出的哈希函数。
unsigned int DEKHash(char *str)
{
unsigned int hashVal = strlen(str);
while (*str)
hashVal = (hashVal << 5) ^ (hashVal >> 27) ^ (*str++);
return (hashVal & UNSIGNED_INT_MAX);
}
10. BP Hash
//BP Hash function
unsigned int BPHash(char *str)
{
unsigned int hashVal = strlen(str);
while (*str)
hashVal = (hashVal << 7) ^ (*str++);
return (hashVal & UNSIGNED_INT_MAX);
}
11. FNV Hash
FNVHash 算法全名为 Fowler-Noll-Vo 算法,是以三位发明人 Glenn Fowler,Landon Curt Noll,Phong Vo 的名字来命名的。
//FNV Hash function, FNV-1
unsigned int FNVHash(char *str)
{
int fnvprime = 0x811C9DC5;
unsigned int hashVal = 0;
while (*str)
{
hashVal *= fnvprime;
hashVal ^= *str++;
/*FNV-1a
hashVal ^= *str++;
hashVal *= fnvprime;
*/
}
return (hashVal & UNSIGNED_INT_MAX);
}
各哈希函数比较
哈希函数可能有其应用范围,这里我们只比较常用英文字符串的哈希效果。可以通过哈希函数计算的效率及计算后的最大冲突数来比较各哈希函数的优劣。样本有两个,一个是 linux 系统中的 words 文件,里面包含 45403 个单词,ubuntu 或 fedora 系统可以从 /usr/share/dict 中获取,其它可以从 https://users.cs.duke.edu/~ola/ap/linuxwords 中获取,另一个取自 https://gist.github.com/WChargin/8927565 里面包含 99171 个英文单词。
对两个样本采用各个哈希函数分别进行了 3000 次哈希后总耗时除以 3000 得到每次哈希两个样本共 (99171 + 45403 =) 144574 个单词的平均耗时,如下表:
哈希函数 | BKDRHash | APHash | DJBHash | JSHash | RSHash | SDBMHash | PJWHash | ELFHash | DEKHash | BPHash | FNVHash |
---|---|---|---|---|---|---|---|---|---|---|---|
耗时 (单位:毫秒) |
5.91 | 6.65 | 5.39 | 5.70 | 6.27 | 5.91 | 7.69 | 7.25 | 6.25 | 6.26 | 6.26 |
把哈希表大小分别设为100, 1000, 10000,对两个样本进行哈希后取其最大冲突数。
样本1 (45403 个单词):
哈希表大小 | 100 | 1000 | 10000 |
---|---|---|---|
BKDRHash | 503 | 67 | 13 |
APHash | 525 | 69 | 15 |
DJBHash | 500 | 66 | 15 |
JSHash | 493 | 67 | 17 |
RSHash | 503 | 70 | 15 |
SDBMHash | 506 | 68 | 16 |
PJWHash | 1919 | 419 | 102 |
ELFHash | 1919 | 419 | 102 |
DEKHash | 697 | 109 | 24 |
BPHash | 3079 | 1621 | 1505 |
FNVHash | 490 | 69 | 15 |
样本2 (99171 个单词):
哈希表大小 | 100 | 1000 | 10000 |
---|---|---|---|
BKDRHash | 1076 | 136 | 24 |
APHash | 1054 | 129 | 25 |
DJBHash | 1084 | 134 | 26 |
JSHash | 1073 | 135 | 24 |
RSHash | 1066 | 135 | 24 |
SDBMHash | 1077 | 134 | 23 |
PJWHash | 4135 | 890 | 200 |
ELFHash | 4135 | 890 | 200 |
DEKHash | 1401 | 204 | 37 |
BPHash | 7417 | 3233 | 2668 |
FNVHash | 1068 | 131 | 24 |
从表一可以看到哈希效率最快的有 DJBHash, BKDRHash, SDBMHash,最慢的有 PJWHash 和 ELFHash,从表二和表三可以看到,哈希效果最差的是 BPHash,其次是 PJWHash 和 ELFHash,其它效果差别不大。
- 版权声明: