几种Hash算法的实现

哈希被广泛使用在很多领域,如数据存储,加密,计算机视觉(几何哈希),此处就简单整理下几个常见的Hash函数的实现,有空陆续补充吧。

BKDR Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名
// 是一种简单快捷的hash算法。
// 也是Java目前采用的字符串的Hash算法(累乘因子为31)。
// 此哈希函数用的最多
template<class T>
size_t BKDRHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
// 可将乘法分解为位运算及加减法可以提高效率
// 如将上式表达为:hash = hash << 7 + hash << 1 + hash + ch;
}
return hash;
}

其中累乘因子也可以为131、1313、13131,比如下述代码就使用了33。

1
2
3
4
5
6
7
unsigned int times33(char *str)
{
unsigned int val = 0;
while (*str)
val = (val << 5) + val + (*str++);
return val;
}

此算法也会有如下变种,如:

1
2
3
4
5
6
7
unsigned int timesnum(char *str, int num)
{
unsigned int val = 0;
while (*str)
val = val * num + (*str++);
return val;
}

SDBM Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 本算法是由于在开源项目SDBM(一种简单的数据库引擎)中被应用而得名
// 它与BKDRHash思想一致,只是种子不同而已。
template<class T>
size_t SDBMHash(const T *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}

AP Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Arash Partow发明的一种hash算法
// 比较优秀的一种哈希算法
unsigned int APhash(char *str)
{
unsigned int val = 0;
int i = 0;
for (i = 0; *str; i++)
if ((i & 1) == 0)
val ^= ((val << 7)^(*str++)^(val>>3));
else
val ^= (~((val << 11)^(*str++)^(val>>5)));
return (val & 0x7FFFFFFF);
}

FNV Hash Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Unix system系统中使用的一种著名hash算法,后来微软也在其hash_map中实现。
template<class T>
size_t FNVHash(const T* str)
{
if(!*str)
return 0;
register size_t hash = 2166136261;
while (size_t ch = (size_t)*str++)
{
hash *= 16777619;
hash ^= ch;
}
return hash;
}

其实关于为什么要用异或,我搜索了下原因,见Why is XOR the default way to combine hashes?

MySQL中出现的字符串哈希函数

1
2
3
4
5
6
7
8
9
unsigned int MySQLhash(char *str)
{
register unsigned int nr = 1, nr2 = 4;
while(*str) {
nr ^= (((nr & 63) + nr2)*((unsigned int)*str++)) + (nr << 8);
nr2 += 3;
}
return (unsigned int)nr;
}

参考链接:
spiderq
各种哈希函数冲突率分析