說到散列，一般對應于散清單（哈希表）和散列函數。
我們今天不談哈希表，僅談下散列函數。
定義
引一段百度百科關于散列函數的定義。
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入，通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。
這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來确定唯一的輸入值。
簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數。
關于散列函數的定義有很多表述，大同小異，了解其概念和内涵即可。
性質
檢視
維基百科和
百度百科，兩者關于散列的性質都提到了幾點：
1、确定性
如果兩個散列值是不相同的，那麼這兩個散列值的原始輸入也是不相同的；
2、沖突（碰撞）
散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同；
3、不可逆性
最後一個是關于是否可逆的，兩者表述有所出入：
維基百科-散列函數
百度百科-散列函數
維基百科中，很明确地提出“散列函數必須具有不可逆性”，而百度百科的表述則模棱兩可，相比之下，後者顯得太不嚴謹了。
筆者比較傾向于維基百科提到的不可逆性。
4、混淆性
在“散列函數的性質”一節，維基百科還提到一點：
輸入一些資料計算出散列值，然後部分改變輸入值，一個具有強混淆特性的散列函數會産生一個完全不同的散列值。
該表述中有兩個詞：“強混淆”, “完全不同”。就是什麼含義呢？
先來了解一個概念：
雪崩效應其精髓在于“嚴格雪崩準則”：當任何一個輸入位被反轉時，輸出中的每一位均有50%的機率發生變化。
再了解一個概念：
Hamming distance。
有的譯作“海明距離”，有的則是“漢明距離”。名字不重要，重要的内涵。
兩個碼字的對應比特取值不同的比特數稱為這兩個碼字的海明距離。舉例如下：10101和00110從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。
對應于散列，如果“部分改變輸入值”, 前後兩個兩個散列的海明距離為散列長度的一半（也就是有一半的bit不相同），則為“50%的機率發生變化”。
這樣的散列函數，就是“具有強混淆特性的散列函數”。
散列函數舉例
常見的散列函數有
MD5 SHA家族等加密散列函數，
CRC也該也算是散列。
兩者都有用于資料校驗，而前者還用于數字簽名，通路認證等安全領域。
不過我們今天不對加密散列做太多展開，主要講講下面兩個散列：
BKDRHash
這個散列函數大家應該見過，可能有的讀者不知道它的名字而已。
JDK中String的hashCode()就是這個散列函數實作的：
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()函數的話，其實作也是類似的：
public static class Foo{
int a;
double b;
String c;
@Override
public 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算法的數學原理是什麼，如何保證盡可能少的碰撞從第二個連結給出的評分對比可以看出，BKDRHash雖然實作簡單，但是很有效（沖突率低）。
低沖突，使得BKDRHash不僅僅用于哈希表，還用于索引對象。
這樣的用法，最常見的還是MD5，有的網站可能會用檔案的MD5作為檢索檔案的key,
像
DiskLruCache也是用MD5作為key, 不過通常不是對檔案本身計算MD5，而是對url做MD5（例如OkHttp, Glide）。
MD5生成的消息摘要有128bit, 如果要辨別的對象不多，沖突率會很低；
當沖突率遠遠低于硬體損壞的機率，那麼可以認為用MD5作為key是可靠的。
對于網站，如果要存儲海量檔案，不建議用MD5作為key。
順便提一下，UUID其實也是128bit的精度，隻是其為了友善閱讀多加了幾個分割線而已。
扯遠了, 回歸正題~
之是以看到BKDRHash用來索引對象，主要是看到這篇文章（筆者沒有研究過Volley源碼）：
Android Volley 源碼解析（二），探究緩存機制裡面提到Volley緩存的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;
}
由于JDK的hashCode()傳回值是int型，這個函數可以說是64bit精度的。
不能說它是散列函數，因為其傳回值長度并不固定，按照定義，不能稱之為散列函數，雖然思想很接近。
其等價寫法如下：
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的散列，無論哪一種，隻要資料集（随機資料）上10^6, 基本上每次跑都會有沖突。
64bit的散列，隻要性能不是太差，如果資料的長度是比較長的（比方說20個位元組的随機數組），即使千萬級别的資料集也很難出現沖突（筆者沒有試過上億的，機器撐不住）。
筆者曾經也是BKDRHash的擁趸，并在項目中使用了一段時間（作為緩存的key）。
知道看到上面那篇知乎的讨論，的一個回答：
看了知乎心裡一驚，回頭修改了下測試用例，構造随機資料時用不定長的資料，比方說1-30個随機位元組，
測試于上面寫的64bitBKDRHash, 其結果是：
資料集上5萬就可以看到沖突了。
之前是知道BKDRHash的混淆性不足的（比方說最後一個位元組的值加1，hash值也隻是加1而已，如果未溢出的話）；
但是由于其實作簡單，以及前面那個不合理的測試結果，就用來做緩存的key了，畢竟Volley也這麼幹了。
實際上也沒有太大的問題，因為用的地方輸入通常比較長，而且要緩存的檔案也不是很多（幾百上千的級别），是以應該不會有沖突。
但是心裡面還是不踏實，最終還是很快換了另一個散列函數。
MurmurHash
初次看到這個散列函數，也是被它的名字雷到了。
不過也有覺得這個名字很“萌”的：
不過有道是“人不可貌相”，算法也不可以名字來評判，還是要看其效果。
如截圖所示，很多大名鼎鼎的開源元件都用到這個散列，那其究竟是何方神聖呢？讓我們來一探究竟。
先看源碼：
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;
}
總的來說也不是很複雜，BKDHHash相比，都是一遍循環的事。
而且C++可以将int64的指針指向char數組，可以一次算8個位元組，對于長度較長的數組，運算更快。
而對于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;
}
以上實作參考：
https://github.com/tnm/murmurhash-java https://github.com/tamtam180/MurmurHash-For-Java/做了一下測試，随機數組，個數10^7，長度1-30， 結果如下：
| 散列函數 | 沖突個數 | 運算時間(毫秒） |
|---|---|---|
| 1673 | 1121 | |
| CRC64 | 1331 | |
| 1119 |
該測試把另一個64bit的hash, CRC64摻和進來了。
很神奇的是，CRC64和BKDRHash的沖突率是一樣的（測了很多次，都是一樣），可能是都存在溢出問題的原因。
至于運算時間，差别不大。
如果把随機數組的長度調整為1-50，則前者(BKDRHash & CRC64)的沖突率會相對降低，而後者的運算效率會稍勝于前者。
我想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算出的散列值比較“均勻”，這個特點很重要。
比如如果用于哈希表，
布隆過濾器等, 元素就會均勻分布。
生日悖論
最後了解一下沖突機率的估算：
生日悖論講的是給定一群人，其中有至少有兩個人生日相同的機率。
以一年365天算，23人（及以上），有兩人生日相同的機率大約50%；而如果到了60人以上，則機率已經大于99%了。
同樣的，給定一組随機數，也可以算出有相同數值（沖突）的機率。
根據維基百科
生日攻擊中的描述，其沖突分布如下表：
如果随機數是32位，那麼可能性有約43億種，但是隻要數量達到50000個，其沖突機率就有25%。
我們常看到MD5作為檔案索引，SHA，MD5用于檔案校驗，就是因為其沖突機率很低，想要篡改檔案還保持Hash不變，極其困難。
不過困難不意味着不可能，例如，Google建議不要使用SHA-1加密了,
參見：
為什麼Google急着殺死加密算法SHA-1扯遠了，回到前面說的緩存key，64bit的MurmurHash, 當緩存數量在10^4這個級别時，
有兩個緩存的key沖突的機率是10^-12（萬億份之一）的量級，應該是比較可靠的。
如果覺得還不夠，可以用128bit的MurmurHash，僅做索引的話，應該比MD5要更合适（運算快，低碰撞，高混淆）
結語
散列廣泛應用于計算機的各個領域，了解散列函數的一些性質，對于解決工程問題或有幫助，
故而有了這篇“漫談”，希望對讀者有所啟發。
有了解不正确的地方，請指正。