緣起

寫這篇文章，源于這么一個問題：假設目前有一千萬個URL訪問記錄，請統計最熱門的10個查詢串。(見此文)。見到這個問題的第一想法使用hash解決，沒考慮hash沖突解決的問題(其實就沒想比較URL，不比較URL無法判斷沖突與否)。后來意識到hash解法在內存受限情況下存在致命缺陷，才有寫這個blog的想法。

散列/散列函數

Hash，一般翻譯做“散列”，也音譯為哈希，就是把任意長度的輸入（又叫做預映射，?pre-image），通過散列算法(散列函數)，變換成固定(或不定)長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。散列函數（或散列算法，Hash?Function）是一種從任何一種數據中創建小的數字“指紋”的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。

作為特征值的散列

散列函數是一種從任何一種數據中創建小的數字“指紋”的方法。密碼學上的?Hash?又被稱為"消息摘要(message?digest)"。簡言之，“指紋”、“信息摘要”本質就是數據的特征值，即散列函數可用于提取數據的特征值。在模式識別中，由于處理原始數據比較困難，經常通過提取數據的多維特征值來簡化數據處理。

最佳的特征值是能完全表征數據的特征值，實際當中很難找到，不管是一維還是多維的特征值。完美散列就是希望能夠找到能唯一表征原始數據的散列函數。

散列函數有一個基本特性：輸出不同，原始數據必然不同；輸出相同，原始數據可能不同。將無限定義域映射成有限值域必然存在沖突。加密散列函數是很不錯的散列函數，其輸出是一個很大的整數，值域很大，故沖突較少。

因為散列值無法唯一表征原始數據，故沖突判斷只能通過比較原始數據方能得知。作為特征值的哈希值非常適合用于判斷原始數據是否不同，比如文件、圖片等。

MPQ散列函數

MPQ使用文件名哈希表來跟蹤內部的所有文件。算法使用了3種不同的哈希：一個用于哈希表的下標，兩個用于驗證。這兩個驗證哈希替代了實際文件名。其本質就是使用3個哈希值來表征文件，當然，mpq無法解決散列沖突問題：即相同的3個哈希值對應兩個不用的文件。

容忍沖突的散列(什么場合沖突可容忍？)

原始問題：?假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。），請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

問題1：將記錄規模擴大1000倍，即幾十億的記錄，內存幾十G。

問題2：將記錄規模擴大1000倍，即幾十億的記錄，內存幾G。即在內存受限的情況下，如何處理數據。(內存讀寫比硬盤快100倍以上，隨機讀寫估計在1w倍以上，直接以磁盤空間代替內存空間的做法就不用提了)

對于問題1，想過一個算法：元數據存于內存+URL存磁盤。元數據：URL哈希值、訪問計數，文件偏移量；所有的URL均存在磁盤中。這個算法有個前提：忽略沖突，將URL哈希值作為URL的唯一表征。元數據量不大((8+8+8)*1G=24G)可全部在內存中存放，處理很快；比較URL哈希值遠比直接比較URL快；URL采用追加方式寫入磁盤，效率也不是問題。但是忽略沖突卻是一個致命的缺陷。

當然可以采取一些措施來減少哈希沖突，如采用128為哈希值，采用多維特征值(URL長度，雙哈希值(可直接使用中間哈希值和最終哈希值))，但這些都無法保證無沖突，即不可能采用有限的特征來表示無限的URL空間！

分布式方案mapreduce

元問題：如果不能直接使用內存來處理所有的數據，那么問題1和2就退化成同樣的問題：如何在內存受限的情況下處理大規模的數據？

這樣的問題有通用解法：map-reduce。即先對數據分類(獨立的類別)，再分別處理，最終歸并結果。

1)?將原始記錄通過hash分別記錄到不同的N個文件(同一個URL只出現在一個文件中)；

2)?分別對N個文件做統計處理，排序輸出；

3)?采用最小堆挑出最熱門的m個記錄。

經過這么分類之后，這個算法本質上是可并行處理的，很容易在分布式集群中實現。“分而治之”的辦法真的很實用(怎么分很重要)。Mapraduce的思想也很通用。

參考文獻：

從頭到尾徹底解析Hash 表算法

wiki散列

wiki散列函數