散列,哈希和杂凑

#散列,哈希和杂凑| 来源: 网络整理| 查看: 265

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

定义百度百科的定义

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等等。

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

Hash函数数据1 数据2 数据3 数据4 数据1得分数据2得分数据3得分数据4得分平均分 BKDRHash 2 0 4774 481 96.55 100 90.95 82.05 92.64 APHash 2 3 4754 493 96.55 88.46 100 51.28 86.28 DJBHash 2 2 4975 474 96.55 92.31 0 100 83.43 JSHash 1 4 4761 506 100 84.62 96.83 17.95 81.94 RSHash 1 0 4861 505 100 100 51.58 20.51 75.96 SDBMHash 3 2 4849 504 93.1 92.31 57.01 23.08 72.41 PJWHash 30 26 4878 513 0 0 43.89 0 21.95 ELFHash 30 26 4878 513 0 0 43.89 0 21.95

散列函数情况表[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]

【本文地址】

散列,哈希和杂凑

散列,哈希和杂凑

今日新闻

推荐新闻