什麼是哈希（Hash）

本來這裏不應該出現這一節的，因爲實際上大家應該都知道什麼是哈希。不過有時候爲了文章的完整性，我這裏就稍微教條性地說明一下吧。ヽ(́◕◞౪◟◕‵)ﾉ

散列（英語：Hashing），通常音譯作哈希，是電腦科學中一種對資料的處理方法，通過某種特定的函數、算法將要檢索的項與用來檢索的索引關聯起來，生成一種便於搜索的數據結構。也譯爲散列。

– From 散列, Wikipedia

實際上通俗的說法就是把某種狀態或者資料給映射到某個值上的操作。

本醬大概就解釋到這裏了，至於哈希的進一步認知包括衝突的產生和解決等，如果米娜桑不瞭解的話還請自行學習咕。థ౪థ

引子——子樹問題

這個不是我在實踐中遇到的問題，而是當年去某不作惡的大廠面試時候遇到的問題，覺得比較經典，所以就拿出來了。ᕙ༼ຈل͜ຈ༽ᕗ

問題描述

給定一棵二叉樹，假設每個節點的數據只有左右子節點，自身並不存儲數據。請找出兩兩完全相等的子樹們。

有興趣的童鞋可以自己先思考一下。₍₍◝(･’ω’･)◟⁾⁾

我的做法

實際上我也不知道自己的做法是不是正確做法，不過既然通過了那一輪面試，想來也不會偏差到哪去喵。ლ（╹ε╹ლ）

做法大概如下：

1. 後序遍歷一遍整棵樹。
2. 對於遍歷到每一個節點，都獲取到左右子節點的哈希值，然後將其拼接重新計算出自身的哈希值，並返回給父親節點。

至於哈希值怎麼算，方法有很多。最簡單的就是設葉子節點一個哈希值，比如是 md5("")，然後每次非葉子節點的哈希值就用 md5(LEFT_HASH + RIGHT_HASH) 來計算。大家也可以自己隨便想一種方法來做就好了。

很多人可能不解了，明明是用 md5，這篇文章是講哈希，有毛線關係。(╯°O°)╯┻━┻

實際上 md5 就是一種哈希算法，而且是非常經典的哈希算法。

典型的哈希算法包括 MD2、MD4、MD5 和 SHA-1 等。當然不侷限於這些，對於數字來說，取模也算是哈希算法，對於字符串狀態轉整數狀態哈希來說還有諸如 BKDR、ELF 等等。

如果大家想多瞭解一些字符串轉數字哈希的算法，可以參考一下 BYVoid 的這篇《各種字符串Hash函數比較》，或者想直接在 Node.js 裏面使用的小夥伴們可以光顧下這個包——bling-hashes。

初步的輪廓已經明晰了，說白了就是將每個節點的哈希全算出來，如果是父親節點就用子節點的哈希拼接起來再哈希一遍。σ`∀´)σ

把這些哈希算出來之後放在一個散列表裏面待查。如果一個算出來的哈希跟之前已有的哈希值相等，那麼就是說這個節點跟那個節點爲根節點的子樹有可能完全相等。

注意：有可能完全相等。

注意：只是有可能完全相等。

注意：重要的事情說三遍，只是有可能完全相等。

哈希是存在着一定的衝突概率的，所以說兩個相等的哈希所檢索到的源不一定一樣，所以我們根據這些計算到的哈希建立哈希表，然後把表中同哈希值的子樹再兩兩同時遍歷一遍以檢驗是否相等。

1. 同時遞歸，取兩個子樹的根節點。
2. 後序遍歷，看看每個節點是不是都一樣存在（或者不存在）左子節點以及存在（或者不存在）右子節點。
3. 循環往復一直到兩兩遍歷完整棵樹得到驗證結果。如果半路有一個節點的左右子節點狀態不一樣就可以直接跳出遞歸返回 false。

至此爲止，我們可以看出大概是兩大步——計算各子樹的哈希值和驗證各同哈希子樹的相等性。不過稍微變通一下，我們就可以在計算出哈希值的時候就去跟以前的對比了。

剪枝

實際上上面的做法還有一個優化的方案，不過跟哈希相關性已經基本上很小了。不過還是跟解決衝突有一丟丟的關係的，沒興趣的童鞋也可以直接跳過了。(๑•́ ₃ •̀๑)

由於子樹哈希值是存在一定的衝突概率的，所以兩個同哈希的子樹不一定相同。那麼我們如果能一眼看出這樣的兩棵子樹是不相等的，就可以省略驗證這一個遞歸的步驟了。

這裏有一種最顯而易見的情況我們是可以忽略省略步驟的，那就是深度。

如果兩棵子樹兩兩完全相等，那麼說明這倆基佬的深度（或者說高度）是一樣的，如果連深度都不一樣了還如何愉快搞基——所以說如果有兩個相等哈希值的子樹的深度不一樣的話可以直接略過驗證步驟了。

那麼就可以這麼做：

1. 設所有葉子節點的深度爲 0，然後每往上一層加一。
2. 遇到左右子節點深度不一樣的父節點時，取深度大的那個子節點深度去加一。

以上步驟在遍歷計算哈希的時候順便也做了，這樣就多了一個驗證標記了。

所以差不多就這樣了，淺嘗輒止。( ˘･з･)

引子的小結

就上述的場景來說，哈希非常好地將一個非常複雜的狀態轉化成一個可以檢索的狀態。本來毫無頭緒的一個問題使用了哈希之後就完全變成了一個檢索加驗證的過程了。

報告圖問題

這個問題就是我在大搜車中確實遇到的場景了。大家也不需要知道什麼是報告圖，就當它是一個代號了。

問題描述

要做的事情大概就是說給定一個報告，我們根據報告的各個細節選定各種圖層然後揉成一團疊加在一起形成最後一個結果圖。

其實本來就有個系統在做這件事情的——每來一個報告就生成一張圖，然後存儲好之後給前端使用。

我做的事情是將邏輯遷移到另一套計算密集型任務集中處理系統中去。(´艸`)

其實生成這樣一張圖片的邏輯是 CPU 計算密集型的邏輯，所以比較耗費資源和時間的，那麼我們就能在這上面做點手腳優化一下。

優化方法

首先我們要知道的是，有哪些圖層是固定的，所以其實這算半個排列組合的問題了。

不過我們也知道排列組合的增長性非常快，更何況我這裏有約 100 個圖層選擇，所以可能性非常多，一下子全生成好不可能。

那麼就可以用哈希和懶惰的思想來實現了。(ˇωˇ人)

雖然報告是有無限種可能的，但是把報告轉成圖層數據之後，擁有完全一樣的圖層數據的報告就可以用同一張圖片了，這樣就可以大大節省空間和時間了。

其實大概的步驟非常簡單：

1. 把圖層數據計算成哈希。（比如把所有圖層文件路徑用某種符號拼接，再用 md5 計算一下）
2. 去數據庫查找這個哈希主鍵存不存在。
   • 如果存在則驗證源圖層數據域當前圖層數據是否吻合。
     • 如果不吻合則按某種算法重新計算哈希，繼續步驟 2。
     • 如果吻合則可以直接拿着這個數據返回了，跳出計算。
   • 如果不存在就說明當前數據庫還沒有這個圖層情況的報告圖生成，那麼就執行生成報告圖邏輯。
3. 報告圖生成之後，將其存入數據庫中。
   • 計算出這個報告圖圖層數據的哈希，去數據庫查存不存在。
     • 如果不存在則說明哈希不衝突，能用，直接用這個哈希存進去。
     • 如果存在則說明哈希衝突，那麼按某種算法重新計算哈希，繼續上面的步驟直到不衝突爲止。

如果大家想知道“按某種算法重新生成哈希”裏面“某種算法”的話可以看看下面的瞎狗眼的說明了。(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

其實很簡單，把圖層數據的這個字符串加某個固定字符當小尾巴，如果哈希還是衝突則繼續加這個小尾巴，直到計算出來的哈希不衝突爲止。

比如我就用了這字符當小尾巴——🀣（麻將牌中的蘭）。(♛‿♛)

報告圖的小結

在這種場景中，我把哈希拿來作檢索某種報告圖是否已經生成的用途。如果沒有生成則生成一張，如果已經生成則直接拿已有的報告圖去用。

至少比原來的來一張報告就生成一張圖片來得快，並且省空間——相當於作冗餘處理了。

事實上在很多的網盤系統中也有作冗餘處理的。你以爲你有多少多少 T 的空間，實際上相同的文件最終在網盤系統裏面只存一份（不過排除備份的那些），而我相信做這些冗餘判斷的原理就是哈希了，SHA-1 也好 MD5 也好，反正就是這樣。

上面網盤的冗餘處理原理也只是我的猜測，我沒在那些廠子裏面工作過所以不能說就是就是這樣子的。歡迎指正。｡ﾟヽ(ﾟ´Д`)ﾉﾟ｡

唯一主鍵問題

這是我來這邊工作後的另一個小插曲了，遇到一個主鍵生成的小需求。

問題描述

有一個數據要插入到數據庫，所以要給它生成一個主鍵，但是需求比較奇葩，可能是歷史遺留問題吧。(눈‸눈)

• 非自增。
• 是一個全是數字的字符串。
• 不同類型的這個表的數據用不同的前綴，比如 10、11、12 等。
• 位數在十幾位左右（不過在我這裏就固定了）。

解決方案

如果是 前綴 + 隨機數 的衝突概率會比較大的，所以還是用哈希來搞。

非常簡單。首先前綴是固定的，我們就不管了，然後我根據這次進來的數據拼接成字符串（數據不會完全一樣的），加上一點隨機鹽，然後用字符串哈希計算一遍，加上前導零，加上當前時間戳的後幾位拼接起來，最後接上前綴就好了。

這個 generate 函數看起來就像這樣子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var bling = require("bling-hashes");
function generate(type, bodyParamStr) {
    var basePrefix;
    switch(type) {
        case 'foo': basePrefix = '10'; break;
        case 'bar': basePrefix = '11'; break;
        default: base_prefix = '00';
    }

    var date = moment();
    var hash = bling.bkdr(bodyParamStr + date.valueOf()).pad(10);
    hash = date.millisecond().pad(3) + hash;

    return basePrefix + hash;
};

注意：這裏的 bling 就是上面提到過的那個 bling-hashes，採用了 BKDR 算法來計算哈希。以及 Number.prototype.pad 函數是我邪惡得使用了 SugarJs 裏面的函數，就是加上前導零的意思。如果受“千萬不要修改原型鏈”影響較深地童鞋別學我哦。bodyParamStr 是前端傳過來的 Raw Form Data，它看起來像 "data1=1&data2=2&..."。

最後得到的這個字符串是我們所要的主鍵了。｡:.ﾟヽ(*´∀`)ﾉﾟ.:｡

不過要注意的是，這個主鍵仍然又衝突的可能性，所以一旦衝突了（無論是自己檢測到的還是插入數據庫的時候疼了）就需要再生產一遍。就目前來說再生成的時候毫秒時間戳後三位會不一樣，所以問題不大，允許存在的誤差——畢竟不是那種分分鐘集千萬條的數據，肯定在 int 範圍內。如果到時候真出問題了再改進。

主鍵的小結

這裏的哈希是用在生成基本上沒有碰撞的主鍵身上，感覺效果也是非常不錯的——前提是你也有這種奇葩需求。

真·小結

本文大致介紹了哈希的幾種用途，有可能是大家熟知的用途，也有可能是巧用，總之就是說了爲什麼我要用哈希。

在編程中，無論是實際用途還是自己玩玩的題目，多動動腦子就會出來一些“奇技淫巧”。哈希也好，別的東西也罷，反正都是爲了解決問題的——千萬別因爲實際開發中通常性的“並沒有什麼卵用”而去忽視它們，雖然哈希已經是夠常用的了。(๑•ૅω•´๑)