哈希算法（一）

本文介绍基本的哈希算法。

哈希是大家比较常见一个词语，在编程中也经常用到，但是大多数人都是知其然而不知其所以然，再加上这几天想写一个一致性哈希算法，突然想想对哈希也不是很清楚，所以，抽点时间总结下Hash知识。本文参考了很多博文，感谢大家的无私分享。

基本概念

Hash，一般翻译做“散列”，也有直接音译为“哈希”的。那么哈希函数的是什么样的？大概就是 value = hash(key)，我们希望key和value之间是唯一的映射关系。

大家使用的最多的就是哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构，通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做哈希函数或散列函数。

实际中的Hash主要有两种应用：加密和压缩。

在加密方面，Hash哈希是把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值，最广泛应用的Hash算法有MD4、MD5、SHA1。

在压缩方面，Hash哈希是指把一个大范围映射到一个小范围，往往是为了节省空间，使得数据容易保存。

Hash的特点

主要原理就是把大范围映射到小范围，因此输入范围必须和小范围相当或者比它更小，否则增加冲突。

Hash函数逼近单向函数，所以可以用来对数据进行加密。

单项函数：如果某个函数在给定输入的时候，很容易计算出其结果来；而当给定结果的时候，很难计算出输入来。

不同的应用对Hash函数有着不同的要求：用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

Hash算法

Hash的产生方式大体可以分为三种基本方法：加法、乘法和移位。

加法哈希是通过遍历数据中的元素然后每次对某个初始值进行加操作，其中加的值和这个数据的一个元素相关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/********************************
 *加法哈希
 *@key   输入字符串
 *@prime 素数
 ********************************/
int additiveHash(string key, int prime)
{
    int hash, i;
    for(hash = key.length(), i = 0; i < key.length(); ++i)
    { 
        hash += int(key.at(i));
    }
    return (hash%prime);
}

乘法哈希是通过遍历数据中的元素然后每次对初始值进行乘法操作，其中乘的值无需和数据有关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/********************************
 *乘法哈希
 *@key   输入字符串
 *@prime 素数
 ********************************/
int bernstein(string key)
{
    int hash, i;
    for(hash = 0, i = 0; i < key.length(); ++i)
    {
        hash = 33*hash + int(key.at(i));
    }
    return hash;
}

/********************************
 *32位FNV算法(乘法)
 *@key   输入字符串
 *@prime 素数
 ********************************/
int M_SHIFT = 0;
int M_MASK = 0x8765fed1;
int FNVHash(string key)
{
    int hash = (int)2166136261L;
    for(int i = 0; i < key.length(); ++i)
    {
        hash = (hash * 16777619)^int(key.at(i));
    }
    if(M_SHIFT == 0)
        return hash;
    return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}

在JAVA中，哈希函数使用的就是乘法哈希：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * JAVA自己带的算法
 */
public static int java(String str) {
    int h = 0;
    int off = 0;
    int len = str.length();
    for (int i = 0; i < len; i++)
    {
        h = 31 * h + str.charAt(off++);
    }
    return h;
}

移位哈希是通过遍历数据中的元素然后每次对初始值进行移位操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/********************************
 *旋转哈希（移位）
 *@key   输入字符串
 *@prime 素数
 ********************************/
int rotatingHash(string key, int prime)
{
    int hash, i;
    for(hash = key.length(), i = 0; i < key.length(); ++i)
    {
        hash = (hash << 4)^(hash >> 28)^int(key.at(i));
    }
    return (hash%prime);
}

实际情况下，很多哈希函数都是包含加法、乘法和移位操作来实现的，例如MD5。

问题

为什么prime的取值是素数？ 有科学依据么？ 有待验证

有人是这样说的取素数，可以降低碰撞的概率。但是并没有很好的说明原因，如果哪位有想法希望能留下您的想法，分享给大家。