簡介：說到散列，一般對應(yīng)于散列表（哈希表）和散列函數(shù)。 我們今天不談哈希表，僅談下散列函數(shù)。

說到散列，一般對應(yīng)于散列表（哈希表）和散列函數(shù)。
我們今天不談哈希表，僅談下散列函數(shù)。

定義

引一段百度百科關(guān)于散列函數(shù)的定義。

Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。
這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。

簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

關(guān)于散列函數(shù)的定義有很多表述，大同小異，理解其概念和內(nèi)涵即可。

性質(zhì)

查看維基百科和百度百科，兩者關(guān)于散列的性質(zhì)都提到了幾點：

1、確定性

如果兩個散列值是不相同的，那么這兩個散列值的原始輸入也是不相同的；

2、沖突（碰撞）

散列函數(shù)的輸入和輸出不是唯一對應(yīng)關(guān)系的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同；

3、不可逆性

最后一個是關(guān)于是否可逆的，兩者表述有所出入：

維基百科中，很明確地提出“散列函數(shù)必須具有不可逆性”，而百度百科的表述則模棱兩可，相比之下，后者顯得太不嚴(yán)謹(jǐn)了。
筆者比較傾向于維基百科提到的不可逆性。

4、混淆性

在“散列函數(shù)的性質(zhì)”一節(jié)，維基百科還提到一點：

輸入一些數(shù)據(jù)計算出散列值，然后部分改變輸入值，一個具有強混淆特性的散列函數(shù)會產(chǎn)生一個完全不同的散列值。

該表述中有兩個詞：“強混淆”, “完全不同”。就是什么含義呢？

先來了解一個概念：雪崩效應(yīng)
其精髓在于“嚴(yán)格雪崩準(zhǔn)則”：當(dāng)任何一個輸入位被反轉(zhuǎn)時，輸出中的每一位均有50%的概率發(fā)生變化。

再了解一個概念：Hamming distance。
有的譯作“海明距離”，有的則是“漢明距離”。名字不重要，重要的內(nèi)涵。

兩個碼字的對應(yīng)比特取值不同的比特數(shù)稱為這兩個碼字的海明距離。舉例如下：10101和00110從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。

對應(yīng)于散列，如果“部分改變輸入值”, 前后兩個兩個散列的海明距離為散列長度的一半（也就是有一半的bit不相同），則為“50%的概率發(fā)生變化”。
這樣的散列函數(shù)，就是“具有強混淆特性的散列函數(shù)”。

散列函數(shù)舉例

常見的散列函數(shù)有MD5和SHA家族等加密散列函數(shù)，CRC也該也算是散列。
兩者都有用于數(shù)據(jù)校驗，而前者還用于數(shù)字簽名，訪問認(rèn)證等安全領(lǐng)域。
不過我們今天不對加密散列做太多展開，主要講講下面兩個散列：

BKDRHash

這個散列函數(shù)大家應(yīng)該見過，可能有的讀者不知道它的名字而已。
JDK中String的hashCode()就是這個散列函數(shù)實現(xiàn)的：

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;}

定義一個類，如果讓IDE自動生成hashCode()函數(shù)的話，其實現(xiàn)也是類似的：

public static class Foo{int a;double b;String c;@Overridepublic int hashCode() {int result;long temp;result = a;temp = Double.doubleToLongBits(b);result = 31 * result + (int) (temp ^ (temp >>> 32));result = 31 * result + (c != null ? c.hashCode() : 0);return result;}}

為什么總是跟“31”過不去呢？為什么要這樣迭代地求積和求和呢？
這篇文章講到了其中一些原理：哈希表之bkdrhash算法解析及擴展
而知乎上也有很多大神做了分析：hash算法的數(shù)學(xué)原理是什么，如何保證盡可能少的碰撞
從第二個鏈接給出的評分對比可以看出，BKDRHash雖然實現(xiàn)簡單，但是很有效（沖突率低）。

低沖突，使得BKDRHash不僅僅用于哈希表，還用于索引對象。
這樣的用法，最常見的還是MD5，有的網(wǎng)站可能會用文件的MD5作為檢索文件的key,
像DiskLruCache也是用MD5作為key, 不過通常不是對文件本身計算MD5，而是對url做MD5（例如OkHttp, Glide）。
MD5生成的消息摘要有128bit, 如果要標(biāo)識的對象不多，沖突率會很低；
當(dāng)沖突率遠(yuǎn)遠(yuǎn)低于硬件損壞的概率，那么可以認(rèn)為用MD5作為key是可靠的。
對于網(wǎng)站，如果要存儲海量文件，不建議用MD5作為key。
順便提一下，UUID其實也是128bit的精度，只是其為了方便閱讀多加了幾個分割線而已。

扯遠(yuǎn)了, 回歸正題~
之所以看到BKDRHash用來索引對象，主要是看到這篇文章（筆者沒有研究過Volley源碼）：
Android Volley 源碼解析（二），探究緩存機制
里面提到Volley緩存的key的設(shè)計：

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; }

由于JDK的hashCode()返回值是int型，這個函數(shù)可以說是64bit精度的。
不能說它是散列函數(shù)，因為其返回值長度并不固定，按照定義，不能稱之為散列函數(shù)，雖然思想很接近。
其等價寫法如下：

public static String getFilenameForKey(String key) {byte[] bytes = key.getBytes();int h1 = 0, h2 = 0;int len = bytes.length;int firstHalfLength = len / 2;for (int i = 0; i < firstHalfLength; i++) {byte ch = bytes[i];h1 = 31 * h1 + ch;}for (int i = firstHalfLength; i < len; i++) {byte ch = bytes[i];h2 = 31 * h2 + ch;}long hash = (((long) h1 << 32) & 0xFFFFFFFF00000000L) | ((long) h2 & 0xFFFFFFFFL);return Long.toHexString(hash);}

效果大約等價于64bit精度的BKDRHash。
64bit的BKDRHash如下：

public static long 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 hash;}

筆者編了程序比較其二者的沖突率，前者比后者要高一些（篇幅限制，不貼測試代碼了，有興趣的讀者可自行測試）。

32bit的散列，無論哪一種，只要數(shù)據(jù)集（隨機數(shù)據(jù)）上10^6, 基本上每次跑都會有沖突。
64bit的散列，只要性能不是太差，如果數(shù)據(jù)的長度是比較長的（比方說20個字節(jié)的隨機數(shù)組），即使千萬級別的數(shù)據(jù)集也很難出現(xiàn)沖突（筆者沒有試過上億的，機器撐不住）。

筆者曾經(jīng)也是BKDRHash的擁躉，并在項目中使用了一段時間（作為緩存的key）。
直到看到上面那篇知乎的討論，的一個回答：

看了知乎心里一驚，回頭修改了下測試用例，構(gòu)造隨機數(shù)據(jù)時用不定長的數(shù)據(jù)，比方說1-30個隨機字節(jié)，
測試于上面寫的64bitBKDRHash, 其結(jié)果是：
數(shù)據(jù)集上5萬就可以看到?jīng)_突了。

之前是知道BKDRHash的混淆性不足的（比方說最后一個字節(jié)的值加1，hash值也只是加1而已，如果未溢出的話）；
但是由于其實現(xiàn)簡單，以及前面那個不合理的測試結(jié)果，就用來做緩存的key了，畢竟Volley也這么干了。
實際上也沒有太大的問題，因為用的地方輸入通常比較長，而且要緩存的文件也不是很多（幾百上千的級別），所以應(yīng)該不會有沖突。
但是心里面還是不踏實，最終還是很快換了另一個散列函數(shù)。

MurmurHash

初次看到這個散列函數(shù)，也是被它的名字雷到了。
不過也有覺得這個名字很“萌”的：

不過有道是“人不可貌相”，算法也不可以名字來評判，還是要看其效果。
如截圖所示，很多大名鼎鼎的開源組件都用到這個散列，那其究竟是何方神圣呢？讓我們來一探究竟。
先看源碼：https://sites.google.com/site/murmurhash/
源碼是用C++寫的：

uint64_t MurmurHash64A ( const void * key, int len, unsigned int seed ) {const uint64_t m = 0xc6a4a7935bd1e995;const int r = 47;uint64_t h = seed ^ (len * m);const uint64_t * data = (const uint64_t *)key;const uint64_t * end = data + (len/8);while(data != end){uint64_t k = *data++;k *= m; k ^= k >> r; k *= m; h ^= k;h *= m; }const unsigned char * data2 = (const unsigned char*)data;switch(len & 7){case 7: h ^= uint64_t(data2[6]) << 48;case 6: h ^= uint64_t(data2[5]) << 40;case 5: h ^= uint64_t(data2[4]) << 32;case 4: h ^= uint64_t(data2[3]) << 24;case 3: h ^= uint64_t(data2[2]) << 16;case 2: h ^= uint64_t(data2[1]) << 8;case 1: h ^= uint64_t(data2[0]);h *= m;};h ^= h >> r;h *= m;h ^= h >> r;return h; }

總的來說也不是很復(fù)雜，BKDHHash相比，都是一遍循環(huán)的事。
而且C++可以將int64的指針指向char數(shù)組，可以一次算8個字節(jié)，對于長度較長的數(shù)組，運算更快。
而對于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+7] << 56) +((long) (data[i + 6] & 0xFF) << 48) +((long) (data[i + 5] & 0xFF) << 40) +((long) (data[i + 4] & 0xFF) << 32) +((long) (data[i + 3] & 0xFF) << 24) +((data[i + 2] & 0xFF) << 16) +((data[i + 1] & 0xFF) << 8) +((data[i] & 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;}

以上實現(xiàn)參考：
https://github.com/tnm/murmurhash-java
https://github.com/tamtam180/MurmurHash-For-Java/

做了一下測試，隨機數(shù)組，個數(shù)10^7，長度1-30， 結(jié)果如下：

散列函數(shù)沖突個數(shù)運算時間(毫秒）

BKDRHash	1673	1121
CRC64	1673	1331
MurmurHash	0	1119

該測試把另一個64bit的hash, CRC64摻和進來了。
很神奇的是，CRC64和BKDRHash的沖突率是一樣的（測了很多次，都是一樣），可能是都存在溢出問題的原因。
至于運算時間，差別不大。
如果把隨機數(shù)組的長度調(diào)整為1-50，則前者(BKDRHash & CRC64)的沖突率會相對降低，而后者的運算效率會稍勝于前者。

我想MurmurHash之所以應(yīng)用廣泛，應(yīng)該不僅僅是因為其沖突率低，還有一個很重要的特性：
前面提到的“強混淆性”。
編寫一個計算碼距的函數(shù)如下：

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;}

構(gòu)造隨機數(shù)組，每次改變其中一個bit，計算MurmurHash，碼距在31-32之間。
對于64bit的散列，正好在50%左右，說明該散列函數(shù)具備雪崩效應(yīng)。
或者從另一個角度看，MurmurHash算出的散列值比較“均勻”，這個特點很重要。
比如如果用于哈希表，布隆過濾器等, 元素就會均勻分布。

生日悖論

最后了解一下沖突概率的估算： 生日悖論 。
生日悖論講的是給定一群人，其中有至少有兩個人生日相同的概率。
以一年365天算，23人（及以上），有兩人生日相同的概率大約50%；而如果到了60人以上，則概率已經(jīng)大于99%了。
同樣的，給定一組隨機數(shù)，也可以算出有相同數(shù)值（沖突）的概率。
根據(jù)維基百科生日攻擊中的描述，其沖突分布如下表：

如果隨機數(shù)是32位，那么可能性有約43億種，但是只要數(shù)量達到50000個，其沖突概率就有25%。
我們常看到MD5作為文件索引，SHA，MD5用于文件校驗，就是因為其沖突概率很低，想要篡改文件還保持Hash不變，極其困難。
不過困難不意味著不可能，例如，Google建議不要使用SHA-1加密了,
參見：為什么Google急著殺死加密算法SHA-1 。

扯遠(yuǎn)了，回到前面說的緩存key，64bit的MurmurHash, 當(dāng)緩存數(shù)量在10^4這個級別時，
有兩個緩存的key沖突的概率是10^-12（萬億份之一）的量級，應(yīng)該是比較可靠的。
如果覺得還不夠，可以用128bit的MurmurHash，僅做索引的話，應(yīng)該比MD5要更合適（運算快，低碰撞，高混淆）

結(jié)語

散列廣泛應(yīng)用于計算機的各個領(lǐng)域，了解散列函數(shù)的一些性質(zhì)，對于解決工程問題或有幫助，
故而有了這篇“漫談”，希望對讀者有所啟發(fā)。

原文鏈接：https://developer.aliyun.com/article/769240?

版權(quán)聲明：本文中所有內(nèi)容均屬于阿里云開發(fā)者社區(qū)所有，任何媒體、網(wǎng)站或個人未經(jīng)阿里云開發(fā)者社區(qū)協(xié)議授權(quán)不得轉(zhuǎn)載、鏈接、轉(zhuǎn)貼或以其他方式復(fù)制發(fā)布/發(fā)表。申請授權(quán)請郵件developerteam@list.alibaba-inc.com，已獲得阿里云開發(fā)者社區(qū)協(xié)議授權(quán)的媒體、網(wǎng)站，在轉(zhuǎn)載使用時必須注明"稿件來源：阿里云開發(fā)者社區(qū)，原文作者姓名"，違者本社區(qū)將依法追究責(zé)任。 如果您發(fā)現(xiàn)本社區(qū)中有涉嫌抄襲的內(nèi)容，歡迎發(fā)送郵件至：developer2020@service.aliyun.com 進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，本社區(qū)將立刻刪除涉嫌侵權(quán)內(nèi)容。

總結(jié)

以上是生活随笔為你收集整理的漫谈散列函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。