常用的字符串 hash 函数

Posted on | In

0 导言

在一些单词查找时需要建立hash表来增加查找效率，当然也可以直接用trie树，但是trie不能保证所有情况比hash表效率高，况且trie相对空间用的多。

在建立hash表时，必然用到hash函数，下面介绍几种常用的字符串hash函数。

BKDR Hash Function

最强大，最易用的字符串哈希函数之一是BKDRHash。

1
2
3
4
5
6
7
8
9
10
11
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
	unsigned int seed = 131;//31 131 1313 13131 131313 etc..
	unsigned int hash = 0;
	while(*str)
	{
		hash = hash * seed + (*str++);
	}
	return (hash & 0x7FFFFFFF);
}

AP Hash Function

另一种常用的字符串哈希函数是APHash。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// AP Hash Function
unsigned int APHash(char *str)
{
	unsigned int 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);
}

MD5

MD5是一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。

1996年后被证实存在弱点，可以被加以破解，对于需要高度安全性的数据，专家一般建议改用其他算法，如SHA-1。2004年，证实MD5算法无法防止碰撞，因此无法适用于安全性认证，如SSL公开密钥认证或是数字签章等用途。

MD5用法如下：

1
2
3
4
#include <openssl/md5.h>

unsigned char *MD5(const unsigned char *d, unsigned long n,
                  unsigned char *md);

SHA-1

安全哈希算法（Secure Hash Algorithm）主要适用于数字签名标准 （Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64位的消息，SHA1会产生一个160位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。

SHA1有如下特性：

  • 不可以从消息摘要中复原信息；
  • 两个不同的消息不会产生同样的消息摘要。
1
#include <openssl/sha.h>

其他

Blizzard hash algorithm
这个算法是非常高效的，被称为One-Way Hash
Blizzard hash algorithm