hash基础概念

但在工程实践中，要查找的关键字往往都不是自然数，即使是自然数也有可能是很大的值。因此，只要我们提前把关键字转换为在固定较小范围内的自然数，就可以实现常数时间的查找。那么问题来了，如何实现该转换关系呢？这就是哈希函数所要完成的工作。

哈希函数：又称散列函数，是把一段有限二进制串（字符串，整数等）转换为自然数的一种函数。

哈希值：哈希函数输出的最终结果。

字符串哈希函数：输入是字符串的哈希函数。

注：实际上就是用一个函数将字符串转化为整数，然后尽可能使一个整数对应一个字符串

现在的哈希函数基本上都是满射，多个字符串会对应一个数字，这种情况佳作冲突，为了减小冲突，列举几种方法


这种方法就是用进制转换的观念，一般用128,但这样十分容易超int型的范围，因此要想办法减小范围，可以用一个较大的数去摸，这时又出现了冲突的问题，那可以用两个数同时去摸，这样用两个数表示一个字符串冲突的几率便大大降低

BKDRHash算法

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
 
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
 
    return (hash & 0x7FFFFFFF);//ox7FFFFFFF代表int型最大值
}

&是与运算符，详细看这

关于 BKDRHash算法可以看

最好用unsigned int 类型，这样相当于每次hash操作都取了一次模

APhash算法

// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned int hash = 0;
    int i;
 
    for (i=0; *str; i++)
    {
        if ((i & 1) == 0)
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
        else
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
    }
 
    return (hash & 0x7FFFFFFF);
}

这篇博客讲的很详细