说到散列，一般都会想到散列函数和哈希表。
下面我就"瞎扯"一下散列函数，哈希表之后再扯；

定义

百度百科的定义

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

维基百科的定义

杂凑，旧译哈希，是电脑科学中一种对数据的处理方法，通过某种特定的函数/演算法将要检索的项与用来检索的索引关联起来，生成一种便于搜寻的数据结构。旧译哈希。
它也常用作一种资讯安全的实作方法，由一串数据中经过杂凑演算法计算出来的数据指纹，经常用来识别档案与数据是否有被窜改，以保证档案与数据确实是由原创者所提供。

特性

从百度百科和维基百科的定义中可以产出一下几点

1. 确定性

如果两个散列值不相同，那么散列之前的原始数据也不同；

2. 碰撞

两个散列之前的数据不同，但是散列计算之后有可能得到相同的散列值；

3. 不可逆

得到散列值之后，无法通过散列值推导出散列之前的原始值；

4. 混淆性

大致就是说：原始数据A计算得到散列值A，然后原始数据A的部分部分内容后计算得到散列值B，那么散列值A和散列值B差异很大。

在混淆性上其实是需要实现两个概念：雪崩效应 和 海明距离

对于雪崩效应，精髓在严格雪崩准则（Strict Avalanche Criterion，SAC）:当任何一个输入位被反转时，输出中的每一位均有50%的概率发生变化。

海明距离：在信息编码中，两个合法代码对应位上编码不同的位数称为码距。
举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。

对于散列来讲，在散列之前的原始值改变量部分内容之后，得到的两个散列值的海明距离为散列长度的一半以上时，则说明达到了50%的概率发生了变化。说明这样的散列函数具有 “ 强混淆特效的散列函数 ” ；

常见散列函数

常见的散列函数有MD5和SHA家族加密散列函数，CRC也应该算，还有神奇的MurmurHash，CityHash，SpookyHash等等。

我们列举来对比下一般散列函数的情况

散列函数情况表^[1]

BKDRHash

虽然有可能不知道这个名字，但是写Java的人肯定见过了的。
JDK中String的hashCode()函数实现就是BKDRHash 散列函数；

    //  实现的方式其实求和，公式如下：散列值 =  s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
    public int hashCode() {
        int h = hash;
        final int len = length();
        if (h == 0 && len > 0) {
            for (int i = 0; i < len; i++) {
                h = 31 * h + charAt(i);
            }
            hash = h;
        }
        return h;
    }

当然这个注释是我自己添加了，为了方便理解这段代码；
然后为什么这里出一个 “31”，知乎中有牛人已经详细解释了：hash算法的数学原理是什么，如何保证尽可能少的碰撞？

通过上面的 散列函数情况表 可以看出，BKDRHash虽然实现简单，但是很有效，碰撞性低，这也是的BKDRHash不仅仅用于哈希表，还用于索引对象。
比如 Android Volley 在使用缓存的时候就用了该种散啦，当然为了跟进一步的降低碰撞性，它对URL进行前后两段进行散列再进行字符串组合，这个也能很好的降低了key的重复性，思路可以借鉴；

// Volly缓存使用的key算法
private String getFilenameForKey(String key) {
       int firstHalfLength = key.length() / 2;
       String localFilename = String.valueOf(key.substring(0, firstHalfLength).hashCode());
       localFilename += String.valueOf(key.substring(firstHalfLength).hashCode());
       return localFilename;
}

当然作为索引对象的时候MD5可能用的更多，比如 DiskLruCache,OKHttp,Glide等，不过这里不做展开了。

严格来讲JDK中String类实现的hashCode()方法不是严格意义上的散列函数，因为它输出的是一个整型（int）数据，而不是一个长度固定的字符串，所以严格意义上不算是散列函数，而且精度也只有32位；
可以升级为64位的，类似如下

  public static String BKDRHash(byte[] bytes) {
        long seed = 1313; // 31 131 1313 13131 131313 etc..
        long hash = 0;
        int len = bytes.length;
        for (int i = 0; i < len; i++) {
            hash = (hash * seed) + bytes[i];
        }
        return Long.toHexString(hash & 0xFFFFFFFFFFFFFFFFL);
    }

可以参考下java各种基本类型的精度：Java 基本数据类型

此外，因为精度的限制，无论是32位还是64位，都难以避免的会出现自然溢出之类的情况，而且混淆也是不足(例如2111和2112的散列值也相差1），然后导致散列碰撞；
这个时候需要举个栗子：Aa 和 BB 作为字符串时的散列值就相同，均为2112，这情况在短字符串和回文中出现的频率很高；
碰撞栗子： 为什么Java中的String.hashCode()有很多冲突？

所以需要一个更加优秀的散列函数MurmurHash

MurmurHash^[2]

MurmurHash算法由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。
2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。
目前最新的版本是MurmurHash3，它能够产生出32-bit或128-bit哈希值。
我们可以先来看看他的源码，源码是c++写的：https://sites.google.com/site/murmurhash/
当然还得用Java再实现一遍

public static long hash64(final byte[] data) {
        if (data == null || data.length == 0) {
            return 0L;
        }
        final int len = data.length;
        final long m = 0xc6a4a7935bd1e995L;
        final long seed = 0xe17a1465;
        final int r = 47;

        long h = seed ^ (len * m);
        int remain = len & 7;
        int size = len - remain;

        for (int i = 0; i < size; i += 8) {
            long k = ((long) data[i] << 56) +
                    ((long) (data[i + 1] & 0xFF) << 48) +
                    ((long) (data[i + 2] & 0xFF) << 40) +
                    ((long) (data[i + 3] & 0xFF) << 32) +
                    ((long) (data[i + 4] & 0xFF) << 24) +
                    ((data[i + 5] & 0xFF) << 16) +
                    ((data[i + 6] & 0xFF) << 8) +
                    ((data[i + 7] & 0xFF));
            k *= m;
            k ^= k >>> r;
            k *= m;
            h ^= k;
            h *= m;
        }

        switch (remain) {
            case 7: h ^= (long)(data[size + 6] & 0xFF) << 48;
            case 6: h ^= (long)(data[size + 5] & 0xFF) << 40;
            case 5: h ^= (long)(data[size + 4] & 0xFF) << 32;
            case 4: h ^= (long)(data[size + 3] & 0xFF) << 24;
            case 3: h ^= (data[size + 2] & 0xFF) << 16;
            case 2: h ^= (data[size + 1] & 0xFF) << 8;
            case 1: h ^= (data[size] & 0xFF);
                h *= m;
        }

        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;

        return h;
    }

github上也有更完整版本的各个版本实现：https://github.com/tamtam180/MurmurHash-For-Java/

有人做过测试，在各种情况下下的运算结果

散列函数情况表^[3]
通过测试可以看到，MurmurHash的碰撞明显比BKDRHash的碰撞要低不少。
同时我们也可以看看MurmurHash的混淆情况；
可以编写一个计算码距的函数来计算下海明距离；

 private static int getHammingDistance(long a, long b) {
       int count = 0;
       long mask = 1L;
       while (mask != 0) {
           if ((a & mask) != (b & mask)) {
               count += 1;
           }
           mask <<= 1;
       }
       return count;
   }

构造随机数组，每次改变其中一个bit，计算MurmurHash，码距在31-32之间。
对于64bit的散列，正好在50%左右，说明该散列函数具备雪崩效应。
此外MurmurHash的均衡性也非常好，这里不做展开，可以参考：一致性哈希负载均衡算法的探讨

CityHash 和 SpookyHash

2011年，发布了两个散列函数，相对于MurmurHash ，它们都进行了改善，这主要应归功于更高的指令级并行机制。
Google发布了CityHash（由Geoff Pike 和Jyrki Alakuijala编写），有64位，128位以及256位的几个变种。
Bob Jenkins 发布了他自己的一个新散列函数SpookyHash（这样命名是因为它是在万圣节发布的），给出128位输出。
它们都拥有2倍于MurmurHash的速度，但他们都没有32位版本，并且CityHash的速度取决于CRC32 指令，目前为SSE 4.2（Intel Nehalem及以后版本）。

结论

到底选用按个散列函数才能“最好”呢？

• 在32位系统上，自然选择MurmurHash3
• 在64位系统上，随意选择CityHash和SpookyHash

当然除了以上介绍的集中散列函数，还有很多其他的新生散列函数在被创造出来，会有越来越好的性能，等等我们的去发掘；

目前散列方法情况

手尾

MD5: MD5算法如何被破解
SHA-1: 为什么Google急着杀死加密算法SHA-1
因为以上MD5和SHA-1存在的问题，所以建议不要在网络传输中使用；

引用

1. https://blog.csdn.net/wanglx_/article/details/40300363 ↩

2. https://sites.google.com/site/murmurhash/ ↩

3. https://blog.csdn.net/huangyueranbbc/article/details/84393060 ↩