今天是LeetCode專題的第30篇文章，一起來看一道字符串分組的問題。
題意
這題的題意很簡單，給定一個字符串數組，要求將所有字符串按照構成分組。
舉個例子，比如給定的數組是[eat, ate, tea, tan, nat, bat]。
其中eat，ate，tea這三個單詞用到的字母都是e，t和a各一個。tan和nat用到的都是a，n和t，最後剩下bat，所以分組結果就是：[eat, ate, tea]，[tan, nat]和[bat]。
暴力
我們依然從最簡單的思路開始想起，我們分組的依據是每一個字符串當中用到的字母的情況。所以我們可以把每一個字符串當中所有的元素拆解出來，放到一個dict當中，然後我們用這個dict來作為分組的標準，將dict相同的字符串放在同一組。
比如eat我們把它變成{'e': 1, 'a': 1, 't': 1}，由於一個字母可能出現多個，所以我們也要記錄出現的次數。但有一個問題是，dict是動態數據，在Python當中我們不能用它作為另一個dict的key。這個問題比較簡單的方法是我們寫一個方法將這個dict拼接成字符串，比如'e1a1t1'。我們用這個作為key。但是這又有了一個問題，dict當中的key並不一定是有序的，所以我們需要對dict進行排序，可以看下下圖中的流程。
也就是說我們需要實現一個函數，它的輸入是字符串，輸出是這個字符串構成的元素。
到這裡就簡單了，我們在外層再創建一個dict用來存儲分組後的結果即可，我們很容易就能寫出代碼：
有些小夥伴可能意識到了一個問題，既然我們先轉化成dict之後後面還是要拼接成字符串，我們
為什麼不直接對字符串排序，將排序之後的結果作為key呢？構成元素一樣的字符串，排序之後的結果必然是相同的。比如apple和pplae排序之後都是aelpp，這樣可行嗎？
思路是OK的，但是提交併不能通過。原因也很簡單，三個字可以概括，就是複雜度。這樣做的複雜度非常大，因為字符串的長度並不是固定的，我們對它們一一排序需要大量的開銷。另外我們用排序之後的結果作為key，也會佔用存儲資源。所以這不是一個好方法。
hash
接下來就到了我們的正主出場了，大家從標題當中應該就已經看出來了，這道題和hash算法有關。
講道理，hash算法的名稱如雷貫耳，我們經常聽到，但是很多人並不知道hash算法是幹嘛的，或者我們究竟什麼地方要用到它。大家聽得比較多的可能是hashMap。
其實hash算法的內容很簡單，可以簡單理解成映射。我們的輸入可以是任何內容，可以是一個數字，也可以是個數組或者是一個對象，但是我們的輸出是一個固定若干個字節組成的信息。比如下圖當中對4取模就是一個hash函數，我們可以根據對4取模之後的結果將數歸類到不同的分桶當中。
我們可以按照我們的意願讓一些數據分在同一個分桶當中，我們也可以讓每一條數據hash之後的結果都儘量各不相同，這樣做實現的是信息的壓縮。比如我們將一個大小2MB的實例進行hash，得到了一個32位的字符串。相當於我們用32位的字符串就可以代表原本2MB的內容，這樣我們可以進行高效的查詢或者是其他操作。舉個例子，比如當下的人臉識別模塊，就可以簡單理解成一個hash函數。攝像頭拍攝照片，算法將照片hash成一個id，再去數據庫當中找到這個id對應的個人信息，完成識別過程。
在這道題當中，我們希望設計一個hash函數，它讀入一個字符串，根據字符串當中的內容進行hash，保證構造相同的字符串hash得到的結果一致。我們就通過這個hash之後的結果來進行分桶，從本質上來說，上面這一種做法也可以看成是一種hash方法。但是由於涉及到了排序，稍稍複雜了一些，並且最後返回的是一個字符串，從時間複雜度和空間複雜度上來看，都還有優化的空間，下面我們就來看一個比較常用的hash算法。
在這個算法當中，我們會選擇一個質數作為hash因子，這樣發生hash碰撞的概率會比較低。通過質數的冪來構造hash結果，我們來看代碼：
這裡的ord是取ascii碼的運算，即將英文字母轉成數字。我們
用某一個質數不同的冪來表示不同的字母，再乘上字母出現的次數作為係數。最後將每個字母hash的值累加起來就得到了整個字符串的hash值，構造相同的字符串的係數和冪都是一樣的，那麼最後求和的結果顯然也會相等，這個結論沒有問題。但是反過來，hash值相等的字符串真的一樣嗎？其實我們想一下是可以想到反例的，比如說如果我們單個的字符a，它的hash值的結果是1 * 23 ^ 0 = 1，單個b的hash值也很好算，是23。請問23個a的hash值是多少？算一下就知道，也是23。因為雖然我們用的冪不同，但是它們的底數是一樣的，我們可以用前面的係數來彌補指數的差。這種不同的對象hash結果一樣的情況叫做hash碰撞，這種是不符合我們預期的。但是可以肯定的是，大多數情況下hash碰撞幾乎是不可避免的。因為我們hash的目的就是為了用一個簡單的數字或者字符串代替原本複雜龐大的數據，就好像拍照一樣，兩個不同的人，也可能拍出來看起來很像。
我們在這個過程當中存在大量的信息壓縮或者信息丟失，比如說我們用10個bit的數字代表了原本2000個bit的數據。不管我們用什麼樣的策略，10個bit能表達的數據就是有限的。根據鴿籠原理，只要我們hash的數據足夠多，總有兩個不一樣的數據hash的結果碰撞。
不過通過設計合適的因子和算法，可以降低或者控制出現碰撞的概率。比如這題當中，我們
選擇越大的素數越不容易出現碰撞，因為選擇的素數越大，構成碰撞需要重複的字符就越多，這種可能性也就越低。最後，我們來看完整代碼：
代碼裡有一個細節，我們剛才寫的是v * pow(23, k)，為什麼到這裡我們換了一種寫法？
因為Python當中pow函數返回的是浮點數，精度會有丟失，這樣會導致hash碰撞的概率大大增加，所以我們換了不適用pow函數的方法。
總結
從難度上來說今天的題目並不難，即使是不知道hash算法的人也能想到解法。但是我們的目的並不是切題，而是從切題當中獲得成長，並且hash算法是一個非常重要也是非常基礎的算法，在很多應用和場景當中都有應用。因此我們瞭解一下hash算法的原理，對於我們日後的成長非常有幫助。
今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。
