hash table

今天用到哈希表,特地查了一下hash 算法:
========================  P1  ====================
我们知道,哈希表是一个固定大小的数组,数组的每个元素是一个链表(单向或双向)的头指针。如果Key一样,则在一起,如果Key不一样,则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索,它利用Key的“哈希算法”直接定位,查找非常快,各种数据库中的数据结构基本都是它。但带来的问题是,哈希表的尺寸、哈希算法。
哈希表的数组是定长的,如果太大,则浪费,如果太小,体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数,最小的质数尺寸是17。

当然,根据不同的数据量,会有不同的哈希表的大小。对于数据量很时多时少的应用,最好的设计是使用动态可变尺寸的哈希表,那么如果你发现哈希表尺寸太小了,比如其中的元素是哈希表尺寸的2倍时,我们就需要扩大哈希表尺寸,一般是扩大一倍。下面的数库是哈希表变化尺寸时尺寸大小的一个列表。


static int prime_array[] = {
17,             /* 0 */
37,             /* 1 */
79,             /* 2 */
163,            /* 3 */
331,            /* 4 */
673,            /* 5 */
1361,           /* 6 */
2729,           /* 7 */
5471,           /* 8 */
10949,          /* 9 */
21911,          /* 10 */
43853,          /* 11 */
87719,          /* 12 */
175447,         /* 13 */
350899,         /* 14 */
701819,         /* 15 */
1403641,        /* 16 */
2807303,        /* 17 */
5614657,        /* 18 */
11229331,       /* 19 */
22458671,       /* 20 */
44917381,       /* 21 */
89834777,       /* 22 */
179669557,      /* 23 */
359339171,      /* 24 */
718678369,      /* 25 */
1437356741,     /* 26 */
2147483647      /* 27 (largest signed int prime) */
};
#define PRIME_ARRAY_SIZE  (28)

要使用哈希表,就一定要用一个哈希算法,来确定KEY值,这似乎是个很难的事,下面是一个哈希算法:


typedef struct _hTab{
    hLinks* link;    /* 一个链表 */
    int  num;        /* 成员个数 */
    int  size;       /* 表的尺寸 */
} hTab;

static unsigned int
getHashIndex(hTab *tabPtr, const char *key)
{
    unsigned int ha = 0;
    while (*key)
    ha = (ha * 128 + *key++) % tabPtr->size;
    return ha;
}

(其中key是一个字符串,hTab就是一个哈希表结构, tabPtr->size是哈希表数组的大小)

这个算法被实施证明是比较不错的,能够达到分散数据的效果,如果你有更好的算法,欢迎和我交流。

============ P2  ======================
打造最快的Hash表
 
最近在网上看到篇文章,一起拜一拜暴雪

先提一个简单的问题,如果有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?

有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但...也只能如此了。

最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数,这个数称为Hash,当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法


unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
	unsigned char *key = (unsigned char *)lpszFileName;
	unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
	int ch;

	while(*key != 0)
	{
		ch = toupper(*key++);
		seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
	}
	return seed1;
} 

Blizzard的这个算法是非常高效的,被称为"One-Way Hash",举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢,答案是,远远不够,要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题,哈希表是一个大数组,这个数组的容量根据程序的要求来定义,例如1024,每一个Hash值通过取模运算 (mod)对应到数组中的一个位置,这样,只要比较这个字符串的哈希值对应的位置又没有被占用,就可以得到最后的结果了,想想这是什么速度?是的,是最快的O(1),现在仔细看看这个算法吧


int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
	int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
	if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
	return nHashPos;
	else
	return -1; //Error value
} 

看到此,我想大家都在想一个很严重的问题:"如果两个字符串在哈希表中对应的位置相同怎么办?",毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝,我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。

事情到此似乎有了完美的结局,如果是把问题独自交给我解决,此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。

中国有句古话"再一再二不能再三再四",看来Blizzard也深得此话的精髓,如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能,但用三个不同的哈希算法算出的入口点都一致,那几乎可以肯定是不可能的事了,这个几率是1:18889465931478580854784,大概是10的 22.3次方分之一,对一个游戏程序来说足够安全了。

现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:


int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
	const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
	int nHash = HashString(lpszString, HASH_OFFSET);
	int nHashA = HashString(lpszString, HASH_A);
	int nHashB = HashString(lpszString, HASH_B);
	int nHashStart = nHash % nTableSize, nHashPos = nHashStart;

	while (lpTable[nHashPos].bExists)
	{
		if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
		return nHashPos;
		else
		nHashPos = (nHashPos + 1) % nTableSize;

		if (nHashPos == nHashStart)
		break;
	}

	return -1; //Error value
}

1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回
4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回
5. 移到下一个位置,如果已经越界,则表示没有找到,返回
6. 看看是不是又回到了原来的位置,如果是,则返回没找到
7. 回到3

怎么样,很简单的算法吧,但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法.

Leave a Reply

Your email address will not be published.