注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

回首望星辰

See you in the next world

 
 
 

日志

 
 

哈希表的应用(Blizzard的hash)  

2009-11-11 13:51:36|  分类: 软件开发 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

在网上看到这篇文章,个人认为这种做法不能提高查找的效率,三次哈希的方法不见得高效,侧重点应是不可逆。另外,使用“线性探测开放寻址法”(也就是文中的“顺延”)的效率也比不上“独立链表寻址法”。这篇文章被转载过很多次,这是一篇总结的比较好的。

一个简单的问题:有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但...也只能如此了。

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

以下的函数生成一个长度为0x500(合10进制数:1280)的cryptTable[0x500]

void prepareCryptTable()

{

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

       }

   }

}

 

以下函数计算lpszFileName 字符串的hash值,其中dwHashType 为hash的类型,在下面GetHashTablePos函数里面调用本函数,其可以取的值为0、1、2;该函数返回lpszFileName 字符串的hash值;

unsigned long HashString( char *lpszFileName, unsigned long dwHashType )

{

    unsigned char *key  = (unsigned char *)lpszFileName;

unsigned long seed1 = 0x7FED7FED;

unsigned long 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"( A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。

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

typedef struct

{

    int nHashA;

    int nHashB;

    char bExists;

   ......

} SOMESTRUCTRUE;

一种可能的结构体定义?

lpszString 为要在hash表中查找的字符串;lpTable 为存储字符串hash值的hash表

int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )

{

    int nHash = HashString(lpszString);

    int nHashPos = nHash % nTableSize;

    if ( lpTable[nHashPos].bExists  &&  !strcmp( lpTable[nHashPos].pString, lpszString ) )

    {

        return nHashPos;

    }

    else

    {

        return -1; 

    }

}

看到此,我想大家都在想一个很严重的问题:“如果两个字符串在哈希表中对应的位置相同怎么办?”,毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用“链表”,感谢大学里学的数据结构教会了这个百试百灵的法宝,我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。事情到此似乎有了完美的结局,如果是把问题独自交给我解决,此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。

MPQ使用文件名哈希表来跟踪内部的所有文件。但是这个表的格式与正常的哈希表有一些不同。首先,它没有使用哈希作为下标,把实际的文件名存储在表中用于验证,实际上它根本就没有存储文件名。而是使用了3种不同的哈希:一个用于哈希表的下标,两个用于验证。这两个验证哈希替代了实际文件名。

当然了,这样仍然会出现2个不同的文件名哈希到3个同样的哈希。但是这种情况发生的概率平均是1:18889465931478580854784,这个概率对于任何人来说应该都是足够小的。现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:

lpszString 为要在hash表中查找的字符串;lpTable 为存储字符串hash值的hash表;nTableSize 为hash表的长度;

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;

    int  nHashPos = nHashStart;

    while ( lpTable[nHashPos].bExists )

{

/*如果仅仅是判断在该表中时候存在这个字符串,就比较这两个hash值就可以了,不用对

*结构体中的字符串进行比较。这样会加快运行的速度?减少hash表占用的空间?这种

*方法一般应用在什么场合?*/

        if (   lpTable[nHashPos].nHashA == nHashA

&&  lpTable[nHashPos].nHashB == nHashB )

{

  return nHashPos;

}

         else

{

              nHashPos = (nHashPos + 1) % nTableSize;

}

          if (nHashPos == nHashStart)

              break;

    }

     return -1;

}

1.     计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)

2. 察看哈希表中的这个位置

3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回

4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回

5. 移到下一个位置,如果已经移到了表的末尾,则反绕到表的开始位置起继续查询 

6. 看看是不是又回到了原来的位置,如果是,则返回没找到

7. 回到3

 

补充1:其他比较简单一些的hash函数:

/*key为一个字符串,nTableLength为哈希表的长度

*该函数得到的hash值分布比较均匀*/

unsigned long getHashIndex( const char *key, int nTableLength )

{

    unsigned long nHash = 0;

  

    while (*key)

    {

        nHash = (nHash<<5) + nHash + *key++;

    }

       

    return ( nHash % nTableLength );

}

补充2:

哈希表的数组是定长的,如果太大,则浪费,如果太小,体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数。当然,根据不同的数据量,会有不同的哈希表的大小。对于数据量时多时少的应用,最好的设计是使用动态可变尺寸的哈希表,那么如果你发现哈希表尺寸太小了,比如其中的元素是哈希表尺寸的2倍时,我们就需要扩大哈希表尺寸,一般是扩大一倍。下面是哈希表尺寸大小的可能取值:

17,            37,          79,          163,           331, 

673,           1361,        2729,       471,          10949,       

21911,         43853,      87719,      175447,       350899,

701819,        1403641,   2807303,    5614657,     11229331,  

22458671,     44917381,  89834777,  179669557,   359339171, 

718678369,    1437356741,  2147483647

 

以下为该程序的源代码,在linux下测试通过:

 

#include <stdio.h>

/*crytTable[]里面保存的是HashString函数里面将会用到的一些数据,在prepareCryptTable

 *函数里面初始化*/

unsigned long cryptTable[0x500];

 /***********************************************************

  *以下的函数生成一个长度为0x500(合10进制数:1280)的cryptTable[0x500]

  *

  *

  ***********************************************************/

void prepareCryptTable()

{

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

       }

   }

}

/***********************************************************

 *以下函数计算lpszFileName 字符串的hash值,其中dwHashType 为hash的类型,

 *在下面GetHashTablePos函数里面调用本函数,其可以取的值为0、1、2;该函数

 *返回lpszFileName 字符串的hash值;

 ***********************************************************/

unsigned long HashString( char *lpszFileName, unsigned long dwHashType )

{

    unsigned char *key  = (unsigned char *)lpszFileName;

unsigned long seed1 = 0x7FED7FED;

unsigned long 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;

}

 /***********************************************************

  *在main中测试argv[1]的三个hash值:

  *  ./hash  "arr\units.dat"

  *  ./hash  "unit\neutral\acritter.grp"

  ***********************************************************/

int main( int argc, char **argv )

{

    unsigned long ulHashValue;

    int i = 0;

    if ( argc != 2 )

    {

        printf("please input two arguments\n");

        return -1;

    }

     /*初始化数组:crytTable[0x500]*/

     prepareCryptTable();

     /*打印数组crytTable[0x500]里面的值*/

     for ( ; i < 0x500; i++ )

     {

         if ( i % 10 == 0 )

         {

             printf("\n");

         }

         printf("%-12X", cryptTable[i] );

     }

     ulHashValue = HashString( argv[1], 0 );

     printf("\n----%X ----\n", ulHashValue );

     ulHashValue = HashString( argv[1], 1 );

     printf("----%X ----\n", ulHashValue );

     ulHashValue = HashString( argv[1], 2 );

     printf("----%X ----\n", ulHashValue );

     return 0;

}

  评论这张
 
阅读(1675)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017