ELFhash - 优秀的字符串哈希算法

Hash应用中，字符串是最为常见的关键字，应用非常普通，现在的程序设计语言中基本上都提供了字符串hash表的支持。字符串hash函数非常多，常见的主要有Simple_hash, RS_hash, JS_hash, PJW_hash, ELF_hash, BKDR_hash, SDBM_hash, DJB_hash, AP_hash, CRC_hash等。它们的C语言实现见后面附录代码: hash.h, hash.c。那么这么些字符串hash函数，谁好熟非呢？评估hash函数优劣的基准主要有以下两个指标：

(1) 散列分布性

即桶的使用率backet_usage = (已使用桶数) / (总的桶数)，这个比例越高，说明分布性良好，是好的hash设计。

(2) 平均桶长

即avg_backet_len，所有已使用桶的平均长度。理想状态下这个值应该=1，越小说明冲突发生地越少，是好的hash设计。

hash函数计算一般都非常简洁，因此在耗费计算时间复杂性方面判别甚微，这里不作对比。

评估方案设计是这样的：

(1) 以200M的视频文件作为输入源，以4KB的块为大小计算MD5值，并以此作为hash关键字;

(2) 分别应用上面提到的各种字符串hash函数，进行hash散列模拟；

(3) 统计结果，用散列分布性和平均桶长两个指标进行评估分析。

测试程序见附录代码hashtest.c，测试结果如下表所示。从这个结果我们也可以看出，这些字符串hash函数真是不相仲伯，难以决出高低，所以实际应用中可以根据喜好选择。当然，最好实际测试一下，毕竟应用特点不大相同。其他几组测试结果也类似，这里不再给出。

unsigned int ELFhash(char *str)
{
	unsigned int hash=0;
	unsigned int x=0;
	while(*str)
	{
		hash=(hash<<4)+*str;     //1
		if((x=hash & 0xf0000000)!=0)         //2
		{
			hash^=(x>>24);   //影响5-8位，杂糅一次   3
			hash&=~x;   //清空高四位    4
		}
		str++;   //5
	}
	return (hash & 0x7fffffff);    //6 
}

/*#include"iostream"
#include"cstdio"
#include"cstring"

using namespace std;

unsigned int a=0x80;

int main()
{
	printf("%d\n",a>>1);   //无符号数实行逻辑右移 
	return 0;
} */

#include"iostream"
#include"cstdio"
#include"cstring"

using namespace std;

unsigned int ELFhash(char *str)
{
	unsigned int hash=0;
	unsigned int x=0;
	while(*str)
	{
		hash=(hash<<4)+*str;
		if((x=hash & 0xf0000000)!=0)
		{
			hash^=(x>>24);   //影响5-8位，杂糅一次 
			hash&=~x;   //清空高四位 
		}
		str++;
	}
	return (hash & 0x7fffffff); 
}

int main()
{
	char data[100];
	memset(data,0,sizeof(data));
	scanf("%s",data);
	printf("%d\n",ELFhash(data));
	return 0;
} 

sprintf(data,"%0x",&now_data);