将任意长度的二进制串映射为固定长度的二进制串，这个映射规则就是 哈希算法 ，而通过原始数据映射之后得到的二进制串就是 哈希值 。
哈希算法简单的说就是一种将任意长度的消息压缩到某一固定长度的摘要的函数。

一、特点

一个可靠的哈希算法，应该满足以下特点：

• 易压缩：对于任意大小的消息，都能计算固定长度的哈希值
• 易计算：即使给定很长的消息，也能快速地计算出哈希值
• 单向性：对于给定的哈希值，要找到原始消息是不可行的，即求哈希值的逆很困难，这是哈希算法安全的基础
• 抗碰撞性：理想的哈希函数是无碰撞的，但在实际算法的设计中很难做到这一点，要尽可能的降低哈希碰撞
• 高灵敏性：对输入数据非常敏感，哪怕原始数据只修改了一点，最后得到的哈希值也大不相同

二、哈希碰撞

实际上，不管是什么哈希算法，我们只能尽量减少碰撞冲突的概率，理论上是没有办法做到完全不冲突的。根据组合数学中的鸽巢原理，哈希值的长度是固定且有限的，而要哈希的数据是无穷的，所以总有一些原始值会有到相同的哈希值。
从理论上来说，哈希值空间 N 越大，碰撞概率 P 越低，两个数据的 碰撞概率大约为 P =1/N。也就是说如果已知一个哈希值，通过毫无规律的穷举方法找到此哈希值的一个原始数据，大概需要 N 次，所以如果哈希值空间很大，即便哈希算法存在冲突，但是在有限的时间和资源下，哈希算法还是很难被破解的。

三、应用

• 安全加密 ：哈希算法是一种 单向密码体制 ，即一个从明文到密文的不可逆映射，只有加密过程，没有解密过程。哈希函数视为一个公开加密函数，哈希值视为加密后的密文，这里可以称哈希值为 消息摘要 （Message Digest）。典型应用 加密密码 ，将用户的密码进行哈希后存储，这样只有用户知道密码，而且哈希值都是相同长度的也利于存储，同时 字典攻击 不可避免，其实安全和攻击是一种博弈关系，不存在绝对的安全。所有的安全措施，也只是增加攻击的成本而已 。
• 唯一标识 ：对数据集（ 数据量大 ）中的每一个元素根据其内容计算出一个哈希值，这个哈希值可作为这个元素在数据集中的唯一标识。比如，要在庞大的图库中，搜索一张图是否存在，我们不能单纯地用图片的的名称来对比，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的状况，这时我们可以取图片的哈希值作为标识查找图片。
• 数据校验 ：用文件（或消息）的哈希值检验文件的完整性和正确性，计算文件的哈希值和收到的哈希值进行对比，如果不一致则说明文件被篡改了。通常用于分段下载较大的文件的检验。
• 负载均衡 ：对客户端 IP 或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号，这样就可以把客户端的请求平均的分配到多个服务器中。
• 数据分片 ：对于海量的数据，可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度，分片方法就是把数据的哈希与机器个数取模即是机器编号。
• 哈希表 ：哈希表是基于哈希函数建立的一种查找表，可以提高查找效率。把哈希值作为元素的存储地址的位置，在查找时只需计算出元素的哈希值就可以知道元素的位置，由此，不需比较便可直接取得所查元素。

• 分布式缓存（存储）：采用 一致性哈希算法 ，把哈希值空间视为一个环，再对数据和机器进行哈希并映射到这个环上，数据哈希往顺时针方向最近的机器哈希就是数据对应存储的机器。对于数据分布不均衡的情况可使用虚拟机器方式，即一个机器映射到环上多个节点。

  四、哈希原理方法

• 加法 ：把输入元素一个一个的加起来构成最后的结果，如 additiveHash
• 位运算 ：通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素，如 rotatingHash
• 乘法 ：利用了乘法的不相关性，直接累乘或者乘以某个数累加等，如 bernstein
• 除法 ：除法和乘法一样，同样具有表面上看起来的不相关性。不过，因为除法太慢，这种方式几乎找不到真正的应用
• 查表 ：预定义一个哈希值表，把元素循环和这些预定义的哈希值进行位运算、加法元素等，如 Universal
• 混合 ：利用了以上各种方式，这样处理的哈希破解更难，它们一般很少在面向查找的哈希函数里面使用, 如 MD5

五、MD5 算法实现

MD5 将数据按每个 512 位为一组进行分组，依次对每个分组处理从而得到一个长度为 128 位的结果。

1、填充

1. 在数据后面按位填充一个 1 和无数个 0，直到数据位长满足 N *512+448（N>=0）。
2. 在这个结果后面附加一个 64 位的填充前信息长度，如果填充前信息长度超过 64 位，则取低 64 位。
   经过这两步的处理，信息的位长为N*512+448+64=(N+1）*512，即长度恰好是 512 的整数倍。

2、初始化变量

MD5 有四个 32 位的被称作链接变量的整数参数，这是个参数我们定义为 A、B、C、D 其取值为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。但考虑到大小端的问题我们将其赋值为：

A=0x67452301
B=0xefcdab89
C=0x98badcfe
D=0x10325476

同时 MD5 算法规定了四个非线性操作函数：

F(X,Y,Z) =(X&Y)|((~X)&Z)
G(X,Y,Z) =(X&Z)|(Y&(~Z))
H(X,Y,Z) =X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))

这些函数是这样设计的：如果 X、Y 和 Z 的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。
利用上面的四种操作，生成四个重要的计算函数。这四个计算函数为：

FF(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + F(b, c, d) + M[j] + Ti) << s)
GG(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + G(b, c, d) + M[j] + Ti) << s)
HH(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + H(b, c, d) + M[j] + Ti) << s)
II(a, b, c, d, M[j], s, Ti)表示 a = b + ((a + I(b, c, d) + M[j] + Ti) << s)

其中 M[j]表示数据的第 j 个子分组（从 0 到 15），<< 表示循环左移 s，Ti 是 4294967296*abs(sin(i))的整数部分，i 取值从 1 到 64，单位是弧度。

3、处理分组数据

初始化变量 a,b,c,d=A,B,C,D，记 pF[]={FF,GG,HH,II}，M[]为 16 个子分组，MOVE[]={7,5,4,6}，T[i]=4294967296*abs(sin(i))
每一分组的算法流程如下：

for(i=0;i<4;i++){
    for(j=0;j<4;j++){
        for(k=0;k<4;k++){
            pF[i](a, b, c, d, M[4*i+j], MOVE[i]+5*k,T[4(4*i+j)+k])
            pF[i](d, a, b, c, M[4*i+j], MOVE[i]+5*k,T[4(4*i+j)+k])
            pF[i](c, d, a, b, M[4*i+j], MOVE[i]+5*k,T[4(4*i+j)+k])
            pF[i](b, c, d, a, M[4*i+j], MOVE[i]+5*k,T[4(4*i+j)+k])
        }
    }
}

循环完成后，将 A，B，C，D 分别加上 a，b，c，d，然后继续处理下一个分组
实际的算法实现需要先计算 64 个 Ti 作为常量，去掉循环从而提高处理速度

4、输出

最后的输出是 A、B、C 和 D 的级联（128 位——输出大小）。

六、常见摘要算法对比

七、哈希函数源码

基本哈希函数：

public class HashAlgorithms {

    /**
     * 加法hash
     */
    public static int additiveHash(String key, int prime) {
        int hash, i;
        for (hash = key.length(), i = 0; i < key.length(); i++)
            hash += key.charAt(i);
        return (hash % prime);
    }

    /**
     * 旋转hash
     */
    public static int rotatingHash(String key, int prime) {
        int hash, i;
        for (hash = key.length(), i = 0; i < key.length(); ++i)
            hash = (hash << 4) ^ (hash >> 28) ^ key.charAt(i);
        return (hash % prime);
    }

    static int M_MASK = 0x8765fed1;

    /**
     * 一次一个hash
     */
    public static int oneByOneHash(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        // return (hash & M_MASK);
        return hash;
    }

    /**
     * Bernstein's hash
     */
    public static int bernstein(String key) {
        int hash = 0;
        int i;
        for (i = 0; i < key.length(); ++i)
            hash = 33 * hash + key.charAt(i);
        return hash;
    }

    /**
     * Universal Hashing
     */
    public static int universal(char[] key, int mask, int[] tab) {
        int hash = key.length, i, len = key.length;
        for (i = 0; i < (len << 3); i += 8) {
            char k = key[i >> 3];
            if ((k & 0x01) == 0)
                hash ^= tab[i + 0];
            if ((k & 0x02) == 0)
                hash ^= tab[i + 1];
            if ((k & 0x04) == 0)
                hash ^= tab[i + 2];
            if ((k & 0x08) == 0)
                hash ^= tab[i + 3];
            if ((k & 0x10) == 0)
                hash ^= tab[i + 4];
            if ((k & 0x20) == 0)
                hash ^= tab[i + 5];
            if ((k & 0x40) == 0)
                hash ^= tab[i + 6];
            if ((k & 0x80) == 0)
                hash ^= tab[i + 7];
        }
        return (hash & mask);
    }

    /**
     * Zobrist Hashing
     */
    public static int zobrist(char[] key, int mask, int[][] tab) {
        int hash, i;
        for (hash = key.length, i = 0; i < key.length; ++i)
            hash ^= tab[i][key[i]];
        return (hash & mask);
    }

    static int M_SHIFT = 0;

    /**
     * 32位的FNV算法
     */
    public static int FNVHash(byte[] data) {
        int hash = (int) 2166136261L;
        for (byte b : data)
            hash = (hash * 16777619) ^ b;
        if (M_SHIFT == 0)
            return hash;
        return (hash ^ (hash >> M_SHIFT)) & M_MASK;
    }

    /**
     * 改进的32位FNV算法1
     */
    public static int FNVHash1(byte[] data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (byte b : data)
            hash = (hash ^ b) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }

    /**
     * 改进的32位FNV算法1
     */
    public static int FNVHash1(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++)
            hash = (hash ^ data.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return hash;
    }

    /**
     * Thomas Wang的算法，整数hash
     */
    public static int intHash(int key) {
        key += ~(key << 15);
        key ^= (key >>> 10);
        key += (key << 3);
        key ^= (key >>> 6);
        key += ~(key << 11);
        key ^= (key >>> 16);
        return key;
    }

    /**
     * RS算法hash
     */
    public static 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.charAt(i);
            a = a * b;
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * JS算法
     */
    public static int JSHash(String str) {
        int hash = 1315423911;

        for (int i = 0; i < str.length(); i++) {
            hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * PJW算法
     */
    public static int PJWHash(String str) {
        int BitsInUnsignedInt = 32;
        int ThreeQuarters = (BitsInUnsignedInt * 3) / 4;
        int OneEighth = BitsInUnsignedInt / 8;
        int HighBits = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
        int hash = 0;
        int test = 0;

        for (int i = 0; i < str.length(); i++) {
            hash = (hash << OneEighth) + str.charAt(i);

            if ((test = hash & HighBits) != 0) {
                hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
            }
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * ELF算法
     */
    public static int ELFHash(String str) {
        int hash = 0;
        int x = 0;

        for (int i = 0; i < str.length(); i++) {
            hash = (hash << 4) + str.charAt(i);
            if ((x = (int) (hash & 0xF0000000L)) != 0) {
                hash ^= (x >> 24);
                hash &= ~x;
            }
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * BKDR算法
     */
    public static int BKDRHash(String str) {
        int seed = 131; // 31 131 1313 13131 131313 etc..
        int hash = 0;

        for (int i = 0; i < str.length(); i++) {
            hash = (hash * seed) + str.charAt(i);
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * SDBM算法
     */
    public static int SDBMHash(String str) {
        int hash = 0;

        for (int i = 0; i < str.length(); i++) {
            hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * DJB算法
     */
    public static int DJBHash(String str) {
        int hash = 5381;

        for (int i = 0; i < str.length(); i++) {
            hash = ((hash << 5) + hash) + str.charAt(i);
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * DEK算法
     */
    public static int DEKHash(String str) {
        int hash = str.length();

        for (int i = 0; i < str.length(); i++) {
            hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
        }

        return (hash & 0x7FFFFFFF);
    }

    /**
     * AP算法
     */
    public static int APHash(String str) {
        int hash = 0;

        for (int i = 0; i < str.length(); i++) {
            hash ^= ((i & 1) == 0) ? ((hash << 7) ^ str.charAt(i) ^ (hash >> 3))
                    : (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
        }

        // return (hash & 0x7FFFFFFF);
        return hash;
    }

}

MD5 C++ 源码 ：
MD5.hpp

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
typedef struct{
    unsigned int count[2];
    unsigned int state[4];
    unsigned char buffer[64];
}MD5_CTX;

#define F(x,y,z) ((x&y)|(~x&z))
#define G(x,y,z) ((x&z)|(y&~z))
#define H(x,y,z) (x^y^z)
#define I(x,y,z) (y^(x|~z))
#define ROTATE_LEFT(x,n) ((x<<n)|(x>>(32-n)))
#define FF(a,b,c,d,x,s,ac) { a+=F(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define GG(a,b,c,d,x,s,ac) { a+=G(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define HH(a,b,c,d,x,s,ac) { a+=H(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}
#define II(a,b,c,d,x,s,ac) { a+=I(b,c,d)+x+ac; a=ROTATE_LEFT(a,s); a+=b;}

void MD5Init(MD5_CTX *context);
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen);
void MD5Final(MD5_CTX *context, unsigned char digest[16]);
void MD5Transform(unsigned int state[4], unsigned char block[64]);
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len);
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len);

MD5.cpp

#include "Md5.hpp"
unsigned char PADDING[] = {
    0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
void MD5Init(MD5_CTX *context){
    context->count[0]=0;
    context->count[1]=0;
    context->state[0]=0x67452301;//链接变量，注意与大端字节序的区别，内存中是小端字节序
    context->state[1]=0xEFCDAB89;
    context->state[2]=0x98BADCFE;
    context->state[3]=0x10325476;
}

void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen){
    unsigned int i=0,index=0,partlen=0;
    index=(context->count[0]>>3)&0x3F;//模64字节的余数，第一次调用为0
    partlen=64-index;//第一次partlen为64
    //预留最前面的64位存放数据长度
    context->count[0]+=inputlen<<3;//文本总的位数,低32位
    if(context->count[0]<(inputlen<<3)) context->count[1]++;
    context->count[1]+=inputlen>>29;//先左移3,求出位数,再右移32位，求出左32位
    
    if(inputlen>=partlen){
        memcpy(&context->buffer[index], input, partlen);
        MD5Transform(context->state, context->buffer);
        //512位为1组
        for(i=partlen;i+64<=inputlen;i+=64) MD5Transform(context->state,&input[i]);
        index=0;
    }
    else i=0;
    memcpy(&context->buffer[index], &input[i], inputlen-i);//最后剩下的一部分
}

//32位md5
void MD5Final(MD5_CTX *context, unsigned char digest[16]){
    unsigned int index=0,padlen=0;
    unsigned char bits[8];
    index=(context->count[0]>>3)&0x3F;//模64字节的余数
    padlen=(index<56)?(56-index):(120-index);//需要填充的长度，注意长度占8字节
    MD5Encode(bits,context->count,8);
    MD5Update(context,PADDING,padlen);
    MD5Update(context,bits,8);//这里调用时,index=0
    MD5Encode(digest,context->state,16);
}

void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len){
    unsigned int i = 0, j = 0;//len是char的长度
    while (j<len){
        output[j]=input[i] & 0xFF;
        output[j+1]=(input[i]>>8)&0xFF;
        output[j+2]=(input[i]>>16)&0xFF;
        output[j+3]=(input[i]>>24)&0xFF;
        i++;
        j += 4;
    }
}

void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len){
    unsigned int i = 0, j = 0;
    while (j < len){
        output[i] = (input[j]) |
        (input[j + 1] << 8) |
        (input[j + 2] << 16) |
        (input[j + 3] << 24);
        i++;
        j += 4;
    }
}

void MD5Transform(unsigned int state[4], unsigned char block[64]){
    unsigned int a = state[0];
    unsigned int b = state[1];
    unsigned int c = state[2];
    unsigned int d = state[3];
    unsigned int x[16];
    
    MD5Decode(x, block, 64);
    FF(a, b, c, d, x[0], 7, 0xd76aa478);//32位运算
    FF(d, a, b, c, x[1], 12, 0xe8c7b756);
    FF(c, d, a, b, x[2], 17, 0x242070db);
    FF(b, c, d, a, x[3], 22, 0xc1bdceee);
    FF(a, b, c, d, x[4], 7, 0xf57c0faf);
    FF(d, a, b, c, x[5], 12, 0x4787c62a);
    FF(c, d, a, b, x[6], 17, 0xa8304613);
    FF(b, c, d, a, x[7], 22, 0xfd469501);
    FF(a, b, c, d, x[8], 7, 0x698098d8);
    FF(d, a, b, c, x[9], 12, 0x8b44f7af);
    FF(c, d, a, b, x[10], 17, 0xffff5bb1);
    FF(b, c, d, a, x[11], 22, 0x895cd7be);
    FF(a, b, c, d, x[12], 7, 0x6b901122);
    FF(d, a, b, c, x[13], 12, 0xfd987193);
    FF(c, d, a, b, x[14], 17, 0xa679438e);
    FF(b, c, d, a, x[15], 22, 0x49b40821);
    
    
    GG(a, b, c, d, x[1], 5, 0xf61e2562);
    GG(d, a, b, c, x[6], 9, 0xc040b340);
    GG(c, d, a, b, x[11], 14, 0x265e5a51);
    GG(b, c, d, a, x[0], 20, 0xe9b6c7aa);
    GG(a, b, c, d, x[5], 5, 0xd62f105d);
    GG(d, a, b, c, x[10], 9, 0x2441453);
    GG(c, d, a, b, x[15], 14, 0xd8a1e681);
    GG(b, c, d, a, x[4], 20, 0xe7d3fbc8);
    GG(a, b, c, d, x[9], 5, 0x21e1cde6);
    GG(d, a, b, c, x[14], 9, 0xc33707d6);
    GG(c, d, a, b, x[3], 14, 0xf4d50d87);
    GG(b, c, d, a, x[8], 20, 0x455a14ed);
    GG(a, b, c, d, x[13], 5, 0xa9e3e905);
    GG(d, a, b, c, x[2], 9, 0xfcefa3f8);
    GG(c, d, a, b, x[7], 14, 0x676f02d9);
    GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);
    
    
    HH(a, b, c, d, x[5], 4, 0xfffa3942);
    HH(d, a, b, c, x[8], 11, 0x8771f681);
    HH(c, d, a, b, x[11], 16, 0x6d9d6122);
    HH(b, c, d, a, x[14], 23, 0xfde5380c);
    HH(a, b, c, d, x[1], 4, 0xa4beea44);
    HH(d, a, b, c, x[4], 11, 0x4bdecfa9);
    HH(c, d, a, b, x[7], 16, 0xf6bb4b60);
    HH(b, c, d, a, x[10], 23, 0xbebfbc70);
    HH(a, b, c, d, x[13], 4, 0x289b7ec6);
    HH(d, a, b, c, x[0], 11, 0xeaa127fa);
    HH(c, d, a, b, x[3], 16, 0xd4ef3085);
    HH(b, c, d, a, x[6], 23, 0x4881d05);
    HH(a, b, c, d, x[9], 4, 0xd9d4d039);
    HH(d, a, b, c, x[12], 11, 0xe6db99e5);
    HH(c, d, a, b, x[15], 16, 0x1fa27cf8);
    HH(b, c, d, a, x[2], 23, 0xc4ac5665);
    
    
    II(a, b, c, d, x[0], 6, 0xf4292244);
    II(d, a, b, c, x[7], 10, 0x432aff97);
    II(c, d, a, b, x[14], 15, 0xab9423a7);
    II(b, c, d, a, x[5], 21, 0xfc93a039);
    II(a, b, c, d, x[12], 6, 0x655b59c3);
    II(d, a, b, c, x[3], 10, 0x8f0ccc92);
    II(c, d, a, b, x[10], 15, 0xffeff47d);
    II(b, c, d, a, x[1], 21, 0x85845dd1);
    II(a, b, c, d, x[8], 6, 0x6fa87e4f);
    II(d, a, b, c, x[15], 10, 0xfe2ce6e0);
    II(c, d, a, b, x[6], 15, 0xa3014314);
    II(b, c, d, a, x[13], 21, 0x4e0811a1);
    II(a, b, c, d, x[4], 6, 0xf7537e82);
    II(d, a, b, c, x[11], 10, 0xbd3af235);
    II(c, d, a, b, x[2], 15, 0x2ad7d2bb);
    II(b, c, d, a, x[9], 21, 0xeb86d391);
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
}