Hash算法

数据结构与算法

---

数学原理

$$m=(n-i-1)$$
$$Sum = ∑^n_i p[i] * a ^ m$$

2^32 = 4294967296
2^33 = 8589934592

2^2 = 4
2^3 = 8

2^4 = 16
2^5 = 32

算法分析

暴雪One-Way-Hash

原始需求：由于足迹记录数量庞大，为了优化足迹数据结构，希望足迹改为不在存储用户事件，改为独立数据表存储用户事件及映射Id，新足迹记录写入对应Id。问题是，每次写入时，需要通过用户事件字符串作为条件查表获取Id，Id不存在则插入。

回到数据结构的本质就是去重算法，通过《最优去重算法探索》实验可以肯定一点：从字符串数组中查询目标字符串是否存在，逐个比较字符串是不可取幼稚做法。而通过某种Hash算法获得字符串对应Hash，要将无限可能的字符串组合映射到32位整数，显然也是不现实的。

关于暴雪One-Way-Hash，流传的各种讨论文章惊人地一致，明显是Copy，而且没有说明原理。有两篇博文原创性可读性较高：

十一、从头到尾解析Hash表算法
21Hash算法以及暴雪Hash

关于暴雪One-Way-Hash疑问：
1. 出现2个不同的文件名哈希到3个同样的哈希的概率平均是：1:18889465931478580854784。概率如何计算的？出现怎样处理？
2. 数据实际存储是如何实现的？

//函数prepareCryptTable生成一个长度为0x500（合10进制数：1280）的cryptTable[0x500]
long[] cryptTable = new long[0x500];
void prepareCryptTable()  
{
    //seed = 1048577 = 100000000000000000001
    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 )  //0x100 = 256
        {
            unsigned long temp1, temp2;  
            //0x2AAAAB = 2796203 = 1010101010101010101011
            seed = (seed * 125 + 3) % 0x2AAAAB; 
            temp1 = (seed & 0xFFFF) << 0x10;    //0xFFFF = 65536, 0x10 = 16
            seed = (seed * 125 + 3) % 0x2AAAAB;  
            temp2 = (seed & 0xFFFF);  
            cryptTable[index2] = ( temp1 | temp2 );   
        }
    }   
}

seed = 1048577 = 100000000000000000001
seed * 125 + 3 = 1048577 * 125 + 3 = 131072128 = 111110100000000000010000000
0x2AAAAB = 1010101010101010101011
seed = seed % 0x2AAAAB = seed % 2796203 = seed % 1010101010101010101011 = 2446790
2446790 = 1001010101010111000110
seed &

//2：函数HashString计算字符串lpszFileName的hash值，其中dwHashType 为hash的类型。
unsigned long HashString(const char *lpszkeyName, unsigned long dwHashType )  
{  
    unsigned char *key  = (unsigned char *)lpszkeyName;  
    unsigned long seed1 = 0x7FED7FED;  
    unsigned long seed2 = 0xEEEEEEEE;  
    int ch;  
    while( *key != 0 )  
    {  
        ch = *key++;  
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);  
        seed2 = ch + seed1 + seed2 + (seed2<<5) + 3;  
    }  
    return seed1;  
} 
//然后是构造一个哈希表来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024。
//每一个Hash值通过取模运算 (mod) //对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置有没有被占用，就可以得到最后的结果了，
typedef struct  
{  
         int nHashA;  
         int nHashB;  
         char bExists;  
         ......  
} SOMESTRUCTRUE;  
//3：函数GetHashTablePos在Hash表中查找是否存在目标字符串，有则返回要查找字符串的Hash值，否则，return -1.
int GetHashTablePos( char *lpszString, SOMESTRUCTURE *lpTable )   
{   
    //调用上述函数HashString，返回要查找字符串lpszString的Hash值。  
    int nHash = HashString(lpszString);      int nHashPos = nHash % nTableSize;  
    if ( lpTable[nHashPos].bExists  &&  !strcmp( lpTable[nHashPos].pString, lpszString ) )   
    {         
        return nHashPos;    //返回找到的Hash值  
    }   
    else  
    {  
        return -1;    
    }   
}  

附录

关于整数范围

一个int占用4个字节，1个字节8个bit位，所以可容纳范围为-2^31~+2^31-1 2,147,483,647
直观一点看，如果只考虑unsigned int（无正负之分int），最大值二进制位（32个1），约43亿

11111111111111111111111111111111 = 4294967295 = 0xFFFFFFFF = 2^32 - 1

同理可得：
16位整数中-32768到32767
32位整数中-2147483648到2147 483 647

最高位为符号位 ，请您计算2的15次方以及2的31次方，就可以得到以上结果
16位整数-2^15~2^15-1
32位整数-2^31~2^31-1

同余定理

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m
记作

$$a≡b (mod m)$$
读作 a同余于b模m，或读作a与b对模m同余。
例如 $$26≡2 (mod 12)$$

引申可得：
1 反身性

$$a≡a (mod m)$$
2 对称性 若a≡b(mod m)，则 $$b≡a (mod m)$$
3 传递性 若a≡b (mod m)，b≡c (mod m)，则 $$a≡c (mod m)$$
4 同余式相加 若a≡b (mod m)，c≡d(mod m)，则 $$a + c≡b + d (mod m)$$
5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则 $$ac≡bd (mod m)$$

java char、int、String转换

1、定义char型字符：char r = 'a';
2、通过int强转成int：int k = (int)r;//强转成int型，就是字符所表示的数字值
如何将 String 转换成 char ?
char[] ca="123".toCharArray();

如何将char转换成String?
String s=ca.toString(); //任何类型都可以采用toString()转换为String类型

十六进制学习

July最快Hashtable及String生成hash算法学习

http://blog.csdn.net/v_JULY_v/article/details/6256463