散列表(Hashtable) 几个常见的散列(Hash)函数

需要用 C 实现了一个 Hashtable。
散列表也称哈希表(Hash table),可直接根据键(Key)快速查找值的数据结构。
它把键映射到表中一个位置来访问记录,以加快查找的速度。
这个映射函数叫做散列函数,存放记录的表叫做散列表。

常见散列函数构造方法
1、直接寻址法
2、数字分析法
3、平方取中法
4、折叠法
5、随机数法
6、除法余数法(求模)

还有一个比较重要对地方是处理冲突,就是几个键被映射到同一个位置上。
常见处理冲突的方法:
1、开放寻址法;Hi=(H(key) + di) MOD m, i=1,2,…, k(k 1)、
     1)、di=1,2,3,…, m-1,称线性探测再散列;
     2)、di=1^2, -(1^2), 2^2,-(2^2), 3^2, …, ±(k^2),(k 3)、
     3)、di=伪随机数序列,称伪随机探测再散列。 ==
2、再散列法:Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。
3、链表法
4、建立一个公共溢出区

下面列举几个常用对 Hash 函数:
PHP 使用的 Hash函数

unsigned int hash_times33(char * key){
	unsigned int code = 5381;
	int length = strlen(key);
	char * p = key;
	while(0 != *p){
		//与0x7fffffff做与运算是为了防止内存溢出
		code = (int)((code << 5) + code + *p++) & 0x7fffffff;
	}
	return code;
}

MySQL Hash函数

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);
}

暴雪 Hash函数

unsigned long cryptTable[0x500];
void prepare_crypt_table(void){
	unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
	for( index1 = 0; index1 < 0x100; index1++ ){
		for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100){
			unsigned long temp1, temp2;

			seed = (seed * 125 + 3) % 0x2AAAAB;
			temp1 = (seed & 0xFFFF) << 0x10;

			seed = (seed * 125 + 3) % 0x2AAAAB;
			temp2 = (seed & 0xFFFF);

			cryptTable[index2] = ( temp1 | temp2 );
		}
	}
}
prepare_crypt_table();
zpz_hash_size_type zpz_hash_key_blizzard(char * key, int type){
	unsigned char *p  = (unsigned char *)key;
	unsigned long seed1 = 0x7FED7FED;
	unsigned long seed2 = 0xEEEEEEEE;
	int ch;

	while(0 != *p){
		ch = zpz_to_upper(*p++);
		seed1 = cryptTable[(type << 8 ) + ch] ^ (seed1 + seed2);
		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
	}
	return seed1;
}

另有简单但可用对算法:

unsigned int hash(char *key){
	register unsigned int h = 0;
	register unsigned char *p = (unsigned char *)key; 

	while(NULL != p && 0 != *p){
		h = 31 * h + *p++;
	}

	return h;
}

OpenSSL Hash

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<<r)|(ret>>(32-r));
		ret&=0xFFFFFFFFL;
		ret^=v*v;
		c++;
	}
	return((ret>>16)^ret);
}

Post a Comment

Your email is never shared. Required fields are marked *

*
*