暴雪公司Hash算法匹配字符串

暴雪公司Hash算法匹配字符串

1  暴雪公司简介

       暴雪娱乐公司是一家著名视频游戏制作和发行公司，1991年2月8日由加利福尼亚大学洛杉矶分校的三位毕业生Michael Morhaime、Allen Adham、Frank Pearce，以Silicon&Synapse为名创立；1994年品牌正式更名为“Blizzard”。

暴雪公司推出过多款经典系列作品：魔兽争霸、星际争霸、暗黑破坏神系列，守望先锋，炉石传说，魔兽世界。魔兽争霸及星际争霸均被多项著名电子竞技比赛列为主要比赛项目，在电脑游戏界享有高评价。

问题：如果有一个庞大的字符串数组，给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎样做？

2  常规思维的解决方法

有一个简单的方法：遍历字符串数组，用单独的字符串和字符串数组中的每个字符串比较，直到找到为止。

上面的解决方法只要是学过程序设计人员肯定会想到的，但是这样效率会有多低，把这样的程序交给用户，客户用起来会是什么感受。

3  暴雪的算法

最合适的算法自然是使用 HashTable（哈希表），利用两个字符串计算出的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"。

       把所有字符串数组中的字符串都构建到一个哈希表里，哈希表是一个大数组，这个数组的容量根据程序的要求来定义成逐个比较字符串的Hash值，假设哈希表数组的大小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
}

       有一个问题，不同的字符串在哈希表中的位置相同，一个数组容量是有限的，相同的位置产生了冲突，这种可能性很大。 可以用拉链法解决冲突，这种方法能很好的解决冲突问题。

暴风的程序员使用的方法则是更精妙的方法，基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。 中国有句古话“再一再二不能再三再四”，看来暴风也深得此话的精髓，假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。 现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用“顺延”的方式来解决问题。

实现算法：

int GetHashTablePos(char*lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
    constint 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、看看是不是又回到了原来的位置，假如是，则返回没找到。

 

 

 

 

参考链接

http://blog.csdn.net/shanzhizi/article/details/7736526