常用哈希方式

一般来说，Hash函数可以简单的划分为如下几类：

一、 加法 Hash，即将输入元素一个个累加起来：

int additiveHash(string key, int prime)
{
    int hash = key.length();
    for (int i = 0; i < key.length(); i ++ )
         hash += key[i]; 
    return hash % prime;
}

二、位运算 Hash，这类型 Hash 函数通过利用各种位运算（常见的是移位 >> << 和异或 ^）来充分的混合输入元素。比如，标准的旋转 Hash 的构造如下：

int rotatingHash(string key, int prime)
{
    int hash = key.length();
    for (int i = 0; i < key.length(); i ++ )
    {
        hash = (hash << 4) ^ (hash >> 28) ^ key[i];
    }
    return hash % prime;
}

先移位，然后再进行各种位运算是这种类型 Hash 函数的主要特点。比如，以上的那段计算 hash 的代码还可以有如下几种变形：
1、 hash = (hash << 27) ^ key[i];
2、

hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);

3、

if((i & 1) == 0) hash ^= (hash << 3);
else hash ^= ~(hash << 5);

4、hash += (hash << 5) + key[i];
5、hash = key[i] + (hash << 16) – hash;
6、hash ^= (hash << 2);

三、乘法 Hash，这种类型的 Hash 函数利用了乘法的不相关性（乘法的这种性质，最有名的莫过于平方取头尾的随机数生成算法，虽然这种算法效果不好）。比如：

int bernstein(string key)
{
    int hash = 0;
    for (int i = 0; i < key.length(); i ++ )
        hash = 33 * hash + key[i];
    return hash;
}

使用这种方式的著名 Hash 函数有很多，例如有一种乘以一个不断改变的数： RSHash：

int RSHash(string str)
{
    int b = 378551;
    int a = 63689;
    int hash = 0;
    for (int i = 0; i < str.length(); i ++ )
    {
        hash = hash * a + str[i];
        a = a * b;
    }
    return (hash & 0x7FFFFFFF);
}

还有很多哈希方式例如除法 Hash、查表 Hash、混合 Hash 等，这些在日常做题一般用不到，就不予赘述了。

以上部分转自：莫水千流