四字节HASH变换算法      
           by nEINEI/2007-08-30

查表、匹配是做引擎设计时经常使用的手段，表格驱动也是为了程序的扩展性,例如， 

void fun_add();
void fun_sub();
typedef void (*PFUN)();
typedef   _DispatchFun
{
	   LPCTSTR   name;
	   PFUN      fun;
}DIspatchFun,*PDispatchFun;
DispatchFun    g_DisFunTable[] = 
{ 
	{"add",fun_add};
	{"sub",fun_sub};
	...
	...
	...
	{"0",0};
};

如果要新增的功能，加入g_DisFunTable即可。 一个 for  循环解决了一切问题,后期只需
维护g_DisFunTable结构即可，不需要修改程序代码。
比如：

void AnalyzeFun(LPCTSTR  pName)
{
         for(int i = 0; g_ DisFunTable[i].name; i++)
         {
                    if(0 == strncmp(pName,g_DisFunTable[i].name,strlen(pName) )          
                    {
                           g_DisFunTable[i].fun();
                    }
         }
 }
 
但当问题规模很大，表格项也很多时，效率就是成了首要问题,我们需要一步定位到该调
用在哪个fun上，而不是循环比较。

说起查找，hash当然是最快办法的了,以空间换时间的办法。

比如我要找串“aacc”,候选的字符串集合为
{“cc11”，"dd22","ff33","gg44"，“aacc”} 。顺序查找最慢，要第5次才能匹配到，但如果事先
对每个字符的前两个字节做hash，映射到一个数组上str_hash[0xffff] = ｛false｝;则查找aacc时，
一步就可以知道是否匹配成功。只需：

'a'对应十六进制0x61

if (!str_hash[0x6161]) 
    return false;


显然二个字节的HASH数组要分配 BYTE [ 2 ^ 16]  =  64K 这样的空间大小，对于现在的机
器这点空间是不算什么的，但两字节HASH不足的地方是冲突大了些，解决HASH冲突的手段大
家都知道，这里不提了。

高效使我们自然想到了三字节HASH，记得以前搞网络检测引擎时，用到就是三字节HASH，算一
下占用的内存 BYTE [2 ^ 24] = 16MB,这个就需要谨慎了，如果不是为了在大规模库上面做匹
配，做三字节HASH就是值得考虑的事情，因为占用了比较大的内存空间。

那么有没有取值范围更大，高速且占内存少的HASH算法呢？

从最简单的入手研究，比如我要在一个字符串集合里快速定位其中“abcd”
如 “abca”“abcb”，“abcc”，“abcd”

取两字节，三字节HASH都没有，全部冲突。
如果用四字节HASH，要占BYTE[2 ^ 32] = 4GB内存，这显然是不可接受的情况了。

想个什么办法呢？其实只要将“abcd”一类的字符转换成某种唯一标志即可。

取两字节HASH，
可以看作是前两个字符相乘的结果，"ab" -->  0x6162 ,所以一步定位到BYTE [0X6162]  
的数据。既然我们不想耗费那么大的内存，就没必要用相乘的结果做标识。变换一下，我
们取四个字节相加做HASH。则分别是：

"abca" --- >   BYTE [0x187]    
"abcb" --- >   BYTE [0x188] 
"abcc" --- >   BYTE [0x189] 
"abcd" --- >   BYTE [0x200] 

这样定义 BYTE Hash[512]  就足够了，
但等等，字符相乘做HASH是唯一的，但相加却不是，冲突非常大。
如“abcd ” 和"bbbd" 就是一样的HASH值 。 这样靠0x200 是区分不开他们两个的。

其原因就是a、b、c…….z 字符之间ASC值顺序相差1。这样同一个值就可以有多种不同字符的组合
形式。解决这一问题就是对新字符重新进行编码，我这里采用的办法是递增差值。

因为做4字节HASH，所以基值1，递增基础为4。 看一下是怎样的序列。
a = 1  b = 5  c = 10  d = 16 ，依次类推到 z = 401

这样 H(“abcd”) = 32 ，H(“bbbd”) =  31 。但这样仍不能解决向“abcd”和“dcba”“dcab”等等的
hash冲突的问题。这里引入“势”的概念，类似于电场中的“电势”这一概念。

这里规定：字符大小差值依次递增的正向势，如“abcd“，否则依次递减的为反向势如“dcba”。
势值U的计算方法为： 

a，b 加1，
a，X1 ，c 加2 ，（其中X1不等于b）
a，	X1,X2，d加4 （其中X1不等于b,X2不等于c）
U（abcd）= 7；U（adcb）= 2 ，同理U(dcba) = -7 ，U（bcda）= 3

这样新的计算方法为 ：
h = H（s）+ U（s） ；H（s）为正常计算的值，U（s）为势值起修正作用。因势值上下限为+- 7 ，
故递增基值需要改为7。

h(abcd) = H(abcd) + U(abcd) = 50 + 7 = 57 
h(dcba) = H(dcba) + U(dcba) = 50 + (-7) = 43
a = 1  b = 8  c = 16   d = 25  … z = 476 这样就很好的转换了四字节HASH.

要注意的是这样的变换后仍然存在冲突，因为我们并没有改变hash后的取值空间范围。那么无论怎样加，减
都在这个固定的取值范围内。

但我们以非常小的内存占用BYTE[1024 *2] ，完成四字节HASH
变换的目的。对于四字节变换中最大的字符组合为”zzzz”

h（zzzz） = H(zzzz) + U(zzzz) = 1904 + 0 = 1904 ,其实分配1905个空间就够了。
重申一下这个变换算法的用途，适合字符集不是很大但又要求效率的情况，同时满足了
四节子HASH（要占4G内存，通过转换我们仅用2k）这样的策略。

以上都是一家之言，如变换算法有问题，敬望大家指正。