收集几个hash算法

Java HashMap

 
static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 

h是已经hash过的值, 这里再次hash, 原因是计算索引的方法如下:

 
 
static int indexFor(int h, int length) {
        return h & (length-1);
    }
 

length是2^n, 则h & ( length - 1) 相当于 h % length, length - 1 高位全部是0, 那么h的相应的高位不参与计算, 容易产生碰撞(两个不同的h值, 只要低位相同就映射到同一个bucket). hash函数将高位的bits反映到最终的hash值中, 减少潜在的碰撞.

Java String hashCode

 
public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;
 
        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}
 

经典方法.

Scintilla

 
static unsigned int HashString(const char *s, size_t len) {
    unsigned int ret = 0;
    while (len--) {
        ret <<= 4;
        ret ^= *s;
        s++; 
    }
    return ret;
}
 

有点缺陷, 实际上结果只和字符串的最后8个字符相关. 下面几个字符串的输出是一样的:

 
    cout << HashString("afjiwjeofoeodededede", strlen("afjiwjeofoeodededede"));
    cout << endl;
    cout << HashString("afjikeisfoeodededede", strlen("afjikeisfoeodededede"));
    cout << endl;
    cout << HashString("a3di&fisfoeodededede", strlen("a3di&fisfoeodededede"));
 

idTech

 
ID_INLINE int idStr::Hash( const char *string ) {
    int i, hash = 0;
    for ( i = 0; *string != '\0'; i++ ) {
        hash += ( *string++ ) * ( i + 119 );
    }
    return hash;
}
 

DOOM3 BFG Edition字符串hash. 每个字符的值及其所在的位置参与hash.

MySQL

void hash_password(ulong *resultconst char *passworduint password_len)
{
    register ulong nr=1345345333Ladd=7nr2=0x12345671L;
    ulong tmp;
    const char *password_endpassword password_len;

    for (; password password_endpassword++)
    {
        if (*password == ' ' || *password == '\t')
            continue;                                 /* skip space in password */

        tmp= (ulong) (uchar) *password;
        nr^= (((nr 63)+add)*tmp)+ (nr << 8);
        nr2+=(nr2 << 8) ^ nr;
        add+=tmp;
    }

    result[0]=nr & (((ulong1L << 31) -1L); /* Don't use sign bit (str2int) */;
    result[1]=nr2 & (((ulong1L << 31) -1L);
}

MySQL里面包含了不少hash算法, 上面是一个例子. mysys目录下包含了几个经典HASH的实现例如md5, sha1.

整个hash过程中每一趟, 三个因子 nr , nr2 , add 都在不断变化. 这里字符的位置没有显式的参与hash, 但是很明显, 每一趟这几个因子都在变化, 所以字符位置间接参与了hash. 而且, 通过add, 每一个字符在参与hash的时候都受到他之前的字符的影响.

这个和二战时德国的加密机器Enigma原理相似. Enigma有一个26个字母的键盘, 每个键连接一一个小灯泡. 每次按键, 对应的就会亮一个灯, 旁边的人记录下亮的那个灯, 记录的结果就是加密的序列. 接受者按照这个序列输入键盘, 再次记录的结果就是原始文本. 按键通过电线和连接转轴连接到灯泡, 转轴是一个圆盘, 排列着26个电极, 转轴连接这按键和灯泡, 这样的话通根据转轴的配置, 就可以替换字符, 例如输入A, 结果输出T, 或者输入T, 输出A. 这是一种最原始的加密方法.

Enigma的巧妙之处在于, 每次按一个键, 这些转轴都会转动, 意味着一句话的第一个字符是A, 对应T,如果后面再出现A, 会对应不同的字符. 假如你连续的输入A, 每次得到的结果都不相同. 每次输入, 第一个转轴会移动一个位置, 下一次输出的结果就会不一样, 继续按键, 第一个转轴继续转动, 当转到一圈的时候, 第二个转轴开始转动, 以此类推. 根据Enigma的配置, 不停的输入A, 需要17576次才能看出替换模式.

在这个hash算法里

nr^= (((nr 63)+add)*tmp)+ (nr << 8);

相当于字符替换, 显然同一个字符出现在不同的位置替换的结果都不一样, 影响字符替换的因子包括 nr, add. 这两个因子每一趟都会变化.